二叉树及其遍历

二叉树

二叉树是一种数据结构，描述的是一个节点下至多有两个节点的树状结构。
我们来随便画一个二叉树。

image.png

上图中，蓝色D为根节点，其余皆为子节点。

构造节点

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

我们创建一个名叫Node的类，来表示树的每个节点。
left和right属性分别存储左右子节点。如果这个节点没有子节点了，那么left和right都为None。

构造树

class Tree(object):
    def __init__(self):
        pass

    def create_sample(self):
        """
        定义一个示例树结构
        :return:
        """
        A = Node('A')
        C = Node('C')
        F = Node('F')
        B = Node('B', A, C)
        G = Node('G', F)
        E = Node('E', None, G)
        D = Node('D', B, E)

        return D

我们创建了一个名为Tree的类，用以表示树，其中create_sample方法是为了实现刚刚我们画的树图，用以做测试用。

二叉树的遍历

二叉树常见的遍历有4中，分别是层序遍历 ，先序遍历，中序遍历，后序遍历。
接下来，我们分别用python3将其实现。

1. 层序遍历

先看一下代码，然后再解释其思想。

class Tree(object):
    def __init__(self):
        pass

    def create_sample(self):
        """
        定义一个示例树结构
        :return:
        """
        A = Node('A')
        C = Node('C')
        F = Node('F')
        B = Node('B', A, C)
        G = Node('G', F)
        E = Node('E', None, G)
        D = Node('D', B, E)

        return D

    def layer_traverse(self, root_node):
        if not root_node.left and not root_node.right:
            return

        queue = []
        queue.append(root_node)

        layer_traverse_nodes = []

        while queue:
            current_node = queue.pop(0)
            layer_traverse_nodes.append(current_node)

            if current_node.left:
                queue.append(current_node.left)

            if current_node.right:
                queue.append(current_node.right)

        return layer_traverse_nodes


if __name__ == '__main__':
    tree = Tree().create_sample()

    layer_traverse_nodes = Tree().layer_traverse(tree)

    for n in layer_traverse_nodes:
        print(n.value)

我把层序遍历的方法写到了Tree的方法中了，为了调用方便和将其进行抽象封装。
首先，我调用了create_sample方法，生成了我们在一开始画出来的树。
然后将这个树传入到layer_traverse方法中，与其说它是树，不如说它是树的根节点。
进入到layer_traverse方法后，先进行边界判断，看看跟节点有没有子节点，如果没有就直接return了。
然后，创建名为queue的list，用于存储每一层的节点。并将根节点放入queue。
接着又创建了layer_traverse_nodes空列表，它的作用是存储排好序的节点。
然后开始遍历queue，直到queue为空为止。
先将根节点从queue中弹出，并将其存入layer_traverse_nodes，然后再判断当前节点有没有子节点，如果有则将子节点存入queue。
这样，当下一轮遍历时，queue中就又有了节点，相当于是做了递归操作。

2. 先序遍历

    def pre_order_traverse(self, root_node):
        if root_node == None:
            return

        self.pre_order_traverse_result.append(root_node)

        if root_node.left:
            self.pre_order_traverse(root_node.left)

        if root_node.right:
            self.pre_order_traverse(root_node.right)

        return self.pre_order_traverse_result

3. 中序遍历

    def in_order_traverse(self, root_node):
        if root_node == None:
            return

        if root_node.left:
            self.in_order_traverse(root_node.left)

        self.in_order_traverse_result.append(root_node)

        if root_node.right:
            self.in_order_traverse(root_node.right)

        return self.in_order_traverse_result

4. 后序遍历

 def post_order_traverse(self, root_node):
        if root_node == None:
            return

        if root_node.left:
            self.post_order_traverse(root_node.left)

        if root_node.right:
            self.post_order_traverse(root_node.right)

        self.post_order_traverse_result.append(root_node)

        return self.post_order_traverse_result

总结

这二叉树的这四种遍历大体分为两类，递归（先、中、后序遍历）和循环（层序遍历）。
这里层序较特殊，借助了队列来存储每一层的子节点，然后再从队列中pop出来。