二叉树的定义

二叉树是一种特殊的树，它具有以下特点：

（1）树中每个节点最多只能有两棵树，即每个节点的度最多为2。
（2）二叉树的子树有左右之分，即左子树与右子树，次序不能颠倒。
（3）二叉树即使只有一个子树时，也要区分是左子树还是右子树。

满二叉树

满二叉树作为一种特殊的二叉树，它是指：所有的分支节点都存在左子树与右子树，并且所有的叶子节点都在同一层上。其特点有：

（1）叶子节点只能出现在最下面一层
（2）非叶子节点度一定是2
（3）在同样深度的二叉树中，满二叉树的节点个数最多，节点个数为：，其中 h 为树的深度。

满二叉树图例：

完全二叉树

若设二叉树的深度为 h ，除第 h 层外，其它各层 (1～h−1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。其具有以下特点：

（1）叶子节点可以出现在最后一层或倒数第二层。
（2）最后一层的叶子节点一定集中在左部连续位置。
（3）完全二叉树严格按层序编号。（可利用数组或列表进行实现，满二叉树同）
（4）若一个节点为叶子节点，那么编号比其大的节点均为叶子节点。

完全二叉树图例：

二叉树性质

（1）在非空二叉树的 i层上，至多有 2i−1 个节点 (i≥1)(i≥1) 。
（2）在深度为 h 的二叉树上最多有 2h−1 个节点（k≥1)（k≥1) 。
（3）对于任何一棵非空的二叉树,如果叶节点个数为，度数为 2 的节点个数为，则有:
完全二叉树性质
（1）具有 n 个的结点的完全二叉树的深度为。.
（2）如果有一颗有 n 个节点的完全二叉树的节点按层次序编号，对任一层的节点 i，（1≥i≥n）有：
- （2.1）如果 i=1 ，则节点是二叉树的根，无双亲，如果 i>1 ，则其双亲节点为 ⌊i/2⌋ 。
- （2.2）如果 2i>n 那么节点i没有左孩子，否则其左孩子为 2i。
- （2.3）如果 2i+1>n 那么节点没有右孩子，否则右孩子为 2i+1 。
二叉树遍历
前序遍历

思想：先访问根节点，再先序遍历左子树，然后再先序遍历右子树。总的来说是根—左—右
上图先序遍历结果为：1,2,4,8,9,5,3,6,7

中序遍历

思想：先中序访问左子树，然后访问根，最后中序访问右子树。总的来说是左—根—右
上图中序遍历结果为：8,4,9,2,5,1,6,3,7

后序遍历

思想：先后序访问左子树，然后后序访问右子树，最后访问根。总的来说是左—右—根
上图后序遍历结果为：8,9,4,5,2,6,7,3,1

代码实现

class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树


def preTraverse(root):
    '''
    前序遍历
    '''
    if root == None: # 叶子节点没有孩子节点，所以遍历叶子节点的时候，它的左右子树都为空
        return
    print(root.value)
    preTraverse(root.left)
    preTraverse(root.right)


def midTraverse(root):
    '''
    中序遍历
    '''
    if root == None:
        return
    midTraverse(root.left)
    print(root.value)
    midTraverse(root.right)


def afterTraverse(root):
    '''
    后序遍历
    '''
    if root == None:
        return
    afterTraverse(root.left)
    afterTraverse(root.right)
    print(root.value)


if __name__ == '__main__':
    root = Node(1, left=Node(2, left=Node(4, left=Node(8), right=Node(9)), right=Node(5)),
                right=Node(3, left=Node(6), right=Node(7)))
    print('前序遍历：')
    preTraverse(root)
    print('\n')
    print('中序遍历：')
    midTraverse(root)
    print('\n')
    print('后序遍历：')
    afterTraverse(root)
    print('\n')

二叉树的遍历