1 概念

二叉树是一种树，只不过每个节点最多左右两个子节点（度小于等于2）。

完美二叉树(Perfect Binary Tree)

又叫满二叉树，翻译害人，叶节点都在同一层。

完全二叉树(Complete Binary Tree)

从上到下，从左到右依次填空的二叉树。

完满二叉树(Full Binary Tree)

每个内部节点都有两个子节点，生二胎就完满。

2 构造二叉树

构造方法一

先构造节点，二叉树有个根节点root即可，其它节点直接或间接挂在根上。

class Node():
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class BinTree():
    def __init__(self, root=None):
        self.root = root

可以先初始化节点，节点里包含着相互关系，选一个作为根节点，一棵树就构造完毕。

构造方法二

构造一种从上往下，从左到右添加节点的方法。树默认有一个-1根节点。

class Node():
    def __init__(self, data=-1, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class BinTree():
    def __init__(self):
        self.root = Node()
        self.queue = []                 # 用于组织添加节点队列，第1个始终是还没有两个子节点

    def add(self, node):
        if not isinstance(node, Node):
            node = Node(node)

        if self.root.data == -1:
            self.root = node
            self.queue.append(self.root)
        else:
            last_node = self.queue[0]
            if not last_node.left:      # 未初始化，这里需要改进区分
                last_node.left = node
                self.queue.append(last_node.left)
            else:
                last_node.right = node
                self.queue.append(last_node.right)
                self.queue.pop(0)       # 左右子节点都有了，弹出

个人不太喜欢这种方法，节点是否为空、是否初始化容易混淆，可能适合于完全二叉树。

3 遍历

3.1 深度优先

前序遍历

也就是“根-左-右”的顺序，可以使用递归。

    def preorder_trav(self, subtree):
        if subtree is not None:
            print(subtree.data)                 # 根
            self.preorder_trav(subtree.left)    # 左
            self.preorder_trav(subtree.right)   # 右

可以使用堆栈，出栈时存入任务列表。

    def preorder_trav(self, subtree):
        lst = []
        stack = [subtree]
        while stack:
            node = stack.pop()
            lst.append(node)
            if node.right:
                stack.append(node.right)    
            if node.left:
                stack.append(node.left)

        for node in lst:                    # 顺序处理
            print(node.data)

既然是列表，那么出栈时直接处理也一样。这是因为二叉树本身就是从根节点出发的，可以体会下。

    def preorder_trav(self, subtree):
        stack = [subtree]
        while stack:
            node = stack.pop()
            print(node.data)                # 根
            if node.right:
                stack.append(node.right)    # 右
            if node.left:
                stack.append(node.left)     # 左

后序遍历

也就是“左-右-根”的顺序，使用递归。

    def postorder_trav(self, subtree):
        if subtree is not None:
            self.postorder_trav(subtree.left)
            self.postorder_trav(subtree.right)
            print(subtree.data)

使用堆栈的话，因为二叉树的根在上面，所以无法像前序遍历那样，节点刚出栈就处理，而必须开辟一个任务堆栈。

    def postorder_trav(self, subtree):
        lst = []                            # 最终任务堆栈
        stack = [subtree]                   # 展开用的堆栈
        while stack:
            node = stack.pop()
            lst.append(node)                # 根节点压进任务堆栈
            if node.left:
                stack.append(node.left)     # 把左子树先压进展开堆栈，这样在任务堆栈里就是先左节点
            if node.right:
                stack.append(node.right)    # 再压右子树
            
        while lst:
            node = lst.pop()
            print(node.data)

上面的代码，只需要把左右换一下、把任务从lst顺序取出，就变成前序遍历了。

中序遍历

递归的最简单。

    def midorder_trav(self, subtree):
        if subtree is not None:
            self.midorder_trav(subtree.left)
            print(subtree.data)
            self.midorder_trav(subtree.right)

堆栈形式：

    def midorder_trav(self, subtree):
        stack = []
        node = subtree
        while node or stack:
            while node:             # 把左节点都压进栈
                stack.append(node)
                node = node.left
            node = stack.pop()      # 出栈，一个没有左节点的节点
            print(node.data)
            node = node.right       # 如果该节点有右节点，那么刚好是 空 - 中 - 右；
                                    # 否则，该节点自己是左节点，接下来弹出该节点的父节点（中），然后右

3.2 广度优先

层次遍历

可以使用队列，从根节点开始，出队的时候处理节点，同时将其子节点（也就是下一层）逐个进队。这里使用了双端队列deque来实现队列。

from collections import deque
# ...
    def level_trav(self, subtree):
        queue = deque([subtree])
        while queue:
            node = queue.popleft()
            print(node.data)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

也可以直接使用列表list，每处理完一层，同时将下一层的节点存进列表。

    def level_trav(self, subtree):
        lst = [subtree]
        while lst:
            new_lst = []
            for node in lst:
                print(node.data)
                if node.left:
                    new_lst.append(node.left)
                if node.right:
                    new_lst.append(node.right)
            lst = new_lst

4 其它操作

叶子

随便遍历一下即可。

    def leaves(self, subtree):
        leaves = []
        stack = [subtree]
        while stack:
            node = stack.pop()
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            if not node.left and not node.right:
                leaves.append(node)
        return leaves

试试递归。

    def leaves(self, subtree):
        if not subtree.left and not subtree.right:
            return [subtree]
        elif subtree.left and not subtree.right:
            return self.leaves(subtree.left)
        elif subtree.right and not subtree.left:
            return self.leaves(subtree.right)
        else:
            return self.leaves(subtree.left) + self.leaves(subtree.right)

高度

递归。

    def height(self, subtree):
        if not subtree:
            return 0
        if not subtree.left and not subtree.right:
            return 1
        elif subtree.left and not subtree.right:
            return self.height(subtree.left) + 1
        elif subtree.right and not subtree.left:
            return self.height(subtree.right) + 1
        else:
            return max(self.height(subtree.left), self.height(subtree.right)) + 1

非递归，遍历时压入深度信息。

    def height(self, subtree):
        height = 1 if subtree else 0
        max_height = height
        stack = [(subtree, height)]
        while stack:
            node, height = stack.pop()
            if node.left:
                stack.append((node.left, height + 1))
            if node.right:
                stack.append((node.right, height + 1))
            if height > max_height:
                max_height = height
        return max_height

左右翻转

递归。

    def reverse(self, subtree):
        if subtree:
            subtree.left, subtree.right = subtree.right, subtree.left
            self.reverse(subtree.left)
            self.reverse(subtree.right)

非递归，类似层序遍历。

    def reverse(self, subtree):
        stack = [subtree]
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

5 思考

如果二叉树的根在左边，从左子树展开，那当然就可以类似于前序遍历那样了，不过我没见过这样的二叉树结构，估计是这样？可以研究下：

class Node():
    def __init__(self, data, root=None, right=None):
        self.data = data
        self.root = root
        self.right = right

class BinTree():
    def __init__(self, left=None):
        self.left = left

基础练习——二叉树及其遍历