二叉树

1. 二叉树的概念

　　二叉树是n个有限元素的集合，该集合或为空、或由一个根节点及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。二叉树又分为满二叉树和完全二叉树

　　满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树

　　完全二叉树：完全二叉树是由满二叉树引出的。满二叉树要求每一层的节点数都达到最大值，完全二叉树仅要求除最后一层外的节点数达到最大值，也就是说最后一层可以不满。我们可以把满二叉树看错特殊的完全二叉树。

2. 二叉树的遍历

 　代码实现：　

# 构建节点类
class BiTreeNode:
    def __init__(self, item):
        self.item = item
        self.leftChild = None
        self.rightChild = None

# 创建树节点
a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')

# 模拟树
e.leftChild = a
e.rightChild = g
a.rightChild = c
c.leftChild = b
c.rightChild = d
g.rightChild = f
# 根节点
root = e

from collections import deque
# 遍历树类
class ForInBiTree:
    # 前序遍历：以根节点为中点分为左右两边，从根节点出发先遍历左边在遍历右边，从上左右原则
    def pre_order(self, root):
        # 判断是否是一个空树
        if root:
            print(root.item, end=',')           # 先遍历根节点
            self.pre_order(root.leftChild)      # 递归传入左节点为参数，即往左边走
            self.pre_order(root.rightChild)     # 递归传入右节点为参数，没有左子树，在往右走

    # 中序遍历：以根节点为中心点，先遍历左边在到根节点再遍历左边，先左上右原则
    def cen_order(self, root):
        if root:
            self.cen_order(root.leftChild)      # 递归传入左节点为参数，即往左边走
            print(root.item, end=',')           # 没有左子树则遍历自己
            self.cen_order(root.rightChild)     # 在往右进行遍历

    # 后序遍历：以根节点为中心点，先遍历左边再遍历右边再根节点，从左右上原则
    def later_order(self, root):
        if root:
            self.later_order(root.leftChild)    # 先找左边的子节点
            self.later_order(root.rightChild)   # 在找优点的子节点
            print(root.item, end=',')           # 没有则输出当前根节点

    # 层次遍历：从根节点开始，从上往下开始遍历
    def level_order(self, root):
        # 利用队列的先进先出原则
        queue = deque()
        queue.append(root)      # 根节点进入队列
        while len(queue) > 0:   # 当队列中存在元素则说明还有子节点
            node = queue.popleft()      # 当前根节点指向出队列的节点
            print(node.item, end=',')
            # 按照从左往右的顺序加入队列
            if node.leftChild:
                queue.append(node.leftChild)
            if node.rightChild:
                queue.append(node.rightChild)

forInBiTree = ForInBiTree()
# 前序遍历结果：E,A,C,B,D,G,F
forInBiTree.pre_order(root)
# 中序遍历结果：A,B,C,D,E,G,F
forInBiTree.cen_order(root)
# 后序遍历结果：B,D,C,A,F,G,E
forInBiTree.later_order(root)
# 层次遍历结果：E,A,G,C,F,B,D
forInBiTree.level_order(root)