二叉树种类和遍历

二叉树种类

二叉树种类定义没有一个标准化，所以不同文档可能有不同解释。

1. rooted binary tree

• 存在根节点，并且每个节点都有2个子节点。

2. full binary tree

• 每个节点只有0个或者2个子节点。

3. complete binary tree

• 除去最后一级，其他级都是full状态(0个或者2个子节点)，且最后一级的节点都在左侧子树上。

4. perfect binary tree

• 内节点都有两个子节点，且所有子叶都处于同一级别。

5. infinite complete binary tree

• every node has two children (and so the set of levels is countably infinite). The set of all nodes is countably infinite, but the set of all infinite paths from the root is uncountable, having the cardinality of the continuum
• 我的理解就是无穷尽的rooted binray tree

6. balanced binary tree

• 左右子树高度差不超过1
• 且左右子树各自均为平衡二叉树

7. degenerate tree

• 每个节点只包含一个子节点。

遍历方式

前序遍历(深度优先)

* 指先访问根，然后访问子树的遍历方式。 * 顺序 `F, B, A, D, C, E, G, I, H.`

堆栈代码实现:

class BinTree(object):
    def __init__(self,root):
        # 所有的点都是子节点，也是父节点的叶子。
        self.root = root
        self.left = None
        self.right = None

    def preorder(self, root):
        if root is None:
            return

        stack = []
        node = root
        while node or stack:
            while node:
                # 打印出根节点
                print(node.root)
                # 然后将根节点放入stack中
                stack.append(node)
                # 重新定义node为左节点
                node = node.left
            # 一个个从栈中弹出，其实是压入栈中的根节点
            node = stack.pop()
            # 打印跟的右侧子节点
            node = node.right

#以下遍历方式通用。           
root = BinTree('F')
root.left = BinTree('B')
root.right = BinTree('G')
root.left.left = BinTree('A')
root.left.right = BinTree('D')
root.left.right.left = BinTree('C')
root.left.right.right = BinTree('E')
root.right.right = BinTree('I')
root.right.right.left = BinTree('H')
# 选择执行对应的遍历方法。
root.preorder(root)

解释：
从最顶层的根进入，然后打印出这个根，并且压入栈，然后获取这个根的左节点，依次循环，直到左节点无法获取到，然后出栈，这边出栈出来的为最后压入的根(也就是底层的左节点)，然后开始遍历其右边的子树，右边子树也是从左边开始，也是压入栈，依次循环。

中序遍历(深度优先)

* 指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式。 * 顺序 `A, B, C, D, E, F, G, H, I.`

堆栈代码实现:

class BinTree(object):
    def __init__(self,root):
        self.root = root
        self.left = None
        self.right = None
        
    def midorder(self,root):
    if root is None:
        return
    stack = []
    node = root
    while node or stack:
        while node:
            # 根压入栈
            stack.append(node)
            # 赋予左节点
            node = node.left
        # 挨个弹出，从最底层的左节点弹出
        node = stack.pop()
        # 打印左节点
        print(node.root)
        # 节点赋予右节点，开始遍历右边部分，也是从最底层开始。
        node = node.right

解释：因为是左右中的方式，所以root是最迟打印的，则先把左边的都依次压栈，然后压入最后一个，开始逐步弹出，弹出就打印一个，然后遍历弹出的右子树，也是一样的方法，依次循环，直到全部退出，打印出最顶层的root。

后序遍历(深度优先)

* 指先访问子树，然后访问根的遍历方式。子树先左后右在根节点。 * 顺序 `A, C, E, D, B, H, I, G, F.`

堆栈代码实现：

class BinTree(object):
    def __init__(self,root):
        self.root = root
        self.left = None
        self.right = None
        
    def backorder(self, root):
        if root is None:
            return
        mystack1 = []
        # mystack2中存放的是后序遍历的节点数据。
        mystack2 = []
        node = root
        # mystack1压入顶层根
        mystack1.append(node)
        while mystack1:
            node = mystack1.pop()
            # 判断是否有左或者右节点，这边控制的是下一次循环压栈到stack2的顺序。
            if node.left:
                mystack1.append(node.left)
            if node.right:
                mystack1.append(node.right)
            # 将该数的根放入stack2中，
            mystack2.append(node)
        while mystack2:
            # 此时mystack2中已经存满了节点，挨个pop()出来的顺序就是后序遍历的次序。
            print(mystack2.pop().root)
            

解释：因为顺序为从最左节点开始，且需要判断是否存在根的左右子节点，且不是连续，所以需要用到两个栈。mystack1放入的是当前遍历的节点，然后往mystack2中压入，这个行为之前还对节点进行左右判断，先往stack1中压入左边的节点，然后压入右边的节点，轮到下次循环的时候，后放入stack1中的(右子树)被先pop出来，然后被插入到stack2中，此时stack2中存放的顺序，根节点，然后右节点，接着左节点，依次循环，直到把stack2给压满。最后一个while执行的时候，按照左右根的顺序打印出来，就实现了。

层级遍历(广度优先)

* 广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。 * 顺序 `F, B, G, A, D, I, C, E, H.`

队列代码实现：

class BinTree(object):
    def __init__(self,root):
        self.root = root
        self.left = None
        self.right = None
        
    def levelorder(self, root):
        if root is None:
            return
        myqueue = []
        node = root
        myqueue.append(node)
        while myqueue:
            # pop弹出第一个元素，这个是队列。
            node = myqueue.pop(0)
            print(node.root)
            # 左右插入的顺序也是弹出的顺序。所以能保证平级打印输出。
            if node.left:
                myqueue.append(node.left)
            if node.right:
                myqueue.append(node.right)

解释：通过队列方式实现，比较简单，抓到元素append进去，一左一右方式放入，弹出的时候弹出第一个元素，并且打印。

refer

https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/
https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees
https://blog.yangx.site/2016/07/22/Python-binary-tree-traverse/
https://zh.wikipedia.org/zh-hant/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86