Python|二叉树的简单介绍

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

二叉树是一种常见的数据结构类型，我们经常会遇见二叉树类型的题目，但是我们很多人对二叉树还是不是很清楚下面我们就来简单介绍一下二叉树。

解决方案

二叉树是一种简单的树形结构，其每个节点的分支节点数有0,1或2个。如下图T1,T2和T3是三棵二叉树。显然二叉树是一种递归的结构。

不包含任何节点的二叉树为空树，只有一个节点的二叉树称为单点树，一个节点的子节点的个数称为该节点的度。如果每个分支节点的度都为2，则称之为满二叉树。如果一棵二叉树，除最后一层外，其它层的节点都是满的，而最后一层节点在最左边连续排列，空位都在右边，这样的二叉树叫做完全二叉树。二叉树有三种遍历方式

前序遍历：按根节点、左子树、右子树的顺序遍历。 中序遍历：按左子树、根节点、右子树的顺序遍历。 后序遍历：按左子树、右子树、根节点的顺序遍历。

遍历二叉树代码示例：

class BinTNode:
 def __init__(self,dat,left=None,right=None):
 self.data=dat
 self.left=left
 self.right=right
 def preorder(t,proc):
    if t is None:
    return
    proc(t.data)
    preorder(t.left,proc)
    preorder(t.right,proc)

结语

二叉树是一种特殊的树型结构，它的特点是每个结点至多有两棵子树，且二叉树的子树有左右之分，其次序不能任意颠倒。