二叉树的定义
二叉树是一种特殊的树，它具有以下特点：
- （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')