Python二叉树的三种深度优先遍历

Python二叉树的三种深度优先遍历

一、广度优先遍历和深度优先遍历

对二叉树进行遍历(traversal)是指依次对树中每个节点进行访问，在遍历的过程中实现需要的业务。

对树的遍历方式有广度优先遍历和深度优先遍历两种方式。广度优先一般用队列的方式，对树从上到下逐层遍历，每一层从左到右依次遍历。深度优先一般用递归的方式，遍历时会先尽可能深地遍历，直到叶节点。

在实现完全二叉树时，向完全二叉树中添加数据就是使用广度优先遍历，通过广度优先遍历找到第一个空位，将节点加到此位置。

参考：https://blog.csdn.net/weixin_43790276/article/details/104033490

对于一颗二叉树，深度优先遍历(Depth First Search)是沿着树的深度遍历树的节点，尽可能深地搜索树的分支。本文的重点是深度优先遍历的三种方式。

深度优先遍历有三种方式。这三种遍历方式分别叫做先序遍历(preorder)、中序遍历(inorder)和后序遍历(postorder)，这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。

1. 先序遍历，也叫先根遍历。在先序遍历中，先访问树的根节点，然后递归使用先序遍历访问左子树，最后再递归使用先序遍历访问右子树。遍历顺序为：根节点 -> 左子树 -> 右子树。

2. 中序遍历，也叫中根遍历。在中序遍历中，先递归使用中序遍历访问左子树，然后访问树的根节点，最后再递归使用中序遍历访问右子树。遍历顺序为：左子树 -> 根节点 -> 右子树。

3. 后序遍历，也叫后根遍历。在后序遍历中，先递归使用后序遍历访问左子树，然后递归使用后序遍历访问右子树，最后再访问树的根节点。遍历顺序为：左子树 -> 右子树 -> 根节点。

在这三种遍历方式中，有两点需要注意，一是左右都是说子树，而不是子节点，所以遍历时不能理解成子节点。二是要递归地用相同的遍历方式处理子树，如先序遍历中，要遍历完整个左子树后，才开始遍历右子树，且不管左子树还是右子树，都是先序遍历。

不难发现，先、中、后都是针对访问根节点的先中后来说的，三种遍历方式的另一个名称就是因此而得。

二、实现一棵二叉树

要对二叉树进行遍历，需要先创建一棵二叉树，这里直接使用之前实现完全二叉树的代码，代码如下。

# coding=utf-8
class Node(object):
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.left_child = None
        self.right_child = None


class TreeQueue(object):
    def __init__(self):
        self.__members = list()

    def is_empty(self):
        return not len(self.__members)

    def enter(self, data):
        self.__members.insert(0, data)

    def outer(self):
        if self.is_empty():
            return
        return self.__members.pop()


class PerfectBinaryTree(object):

    def __init__(self):
        self.__root = None

    def is_empty(self):
        return not self.__root

    def append(self, data):
        node = Node(data)
        if self.is_empty():
            self.__root = node
            return
        queue = TreeQueue()
        queue.enter(self.__root)
        while not queue.is_empty():
            cur = queue.outer()
            if cur.left_child is None:
                cur.left_child = node
                node.parent = cur
                return
            queue.enter(cur.left_child)
            if cur.right_child is None:
                cur.right_child = node
                node.parent = cur
                return
            queue.enter(cur.right_child)

    def show(self):
        if self.is_empty():
            print('空二叉树')
            return
        queue = TreeQueue()
        queue.enter(self.__root)
        while not queue.is_empty():
            cur = queue.outer()
            print(cur.data, end=' ')
            if cur.left_child is not None:
                queue.enter(cur.left_child)
            if cur.right_child is not None:
                queue.enter(cur.right_child)
        print()

    def get_root(self):
        return self.__root

代码里使用队列的方式实现了广度优先遍历，也叫层次遍历。

在二叉树深度优先遍历的三种方式中，都要使用递归的方式，而触发递归都是从根节点开始的，所以增加一个获取根节点的方法 get_root() ，供遍历时使用。

三、先序遍历

以上图为例，用先序遍历的方式对这棵树进行遍历，先访问根节点 A ，然后对左子树先序遍历，左子树的根节点是节点 B，再对 B 的左子树先序遍历，B 的左子树的根节点是节点 D，再对 D 的左子树先序遍历，D 的左子树的根节点是节点 H。H 没有子树了，D 的左子树遍历完了，对 D 的右子树先序遍历，D 的右子树的根节点是节点 I，D 的右子树也遍历完了。这时 B 的左子树也遍历完了，对 B 的右子树先序遍历，B 的右子树的根节点是节点 E，再对 E 的左子树先序遍历，E 的左子树的根节点是节点 J，E 的左子树遍历完了，E 没有右子树，所以 B 的右子树也遍历完了。看整棵树，根节点 A 的左子树遍历完了，再对 A 的右子树先序遍历，A 的右子树的根节点是节点 C ，再对 C 的左子树先序遍历，C 的左子树的根节点是节点 F，C 的左子树遍历完了，对 C 的右子树先序遍历，C 的右子树的根节点是节点 G ，到这里，整棵树就遍历完了。

先序遍历的结果是：A B D H I E J C F G 。

这个过程很长，我把全部步骤写了下来，这就是整个递归的过程，可以看到具体的每一个步骤，嫌烦可以跳过。

接下来用代码实现：

# 先根遍历（先序遍历）
def preorder_traversal(root):
    if root is None:
        return
    print(root.data, end=' ')
    preorder_traversal(root.left_child)
    preorder_traversal(root.right_child)

代码很简单，就是先处理(打印)根节点，然后递归处理左子树，最后再递归处理右子树。

四、中序遍历

有了先序遍历的逐步记录，中序遍历就不再赘述了。

对于上图中的二叉树，中序遍历的结果是：H D I B J E A F C G 。

代码如下：

# 中根遍历（中序遍历）
def inorder_traversal(root):
    if root is None:
        return
    inorder_traversal(root.left_child)
    print(root.data, end=' ')
    inorder_traversal(root.right_child)

代码也很简单，先递归处理(打印)左子树，然后处理根节点，最后再递归处理右子树。

五、后序遍历

同理，将根节点的处理放到最后，就是后序遍历了，这里也不再赘述过程。

还是上图中的二叉树，后序遍历的结果是：H I D J E B F G C A

代码如下：

# 后根遍历（后序遍历）
def postorder_traversal(root):
    if root is None:
        return
    postorder_traversal(root.left_child)
    postorder_traversal(root.right_child)
    print(root.data, end=' ')

代码还是很简单，先递归处理(打印)左子树，然后递归处理右子树，最后再处理根节点。

在这三种遍历方式中，理解了递归的思想，这三个函数就非常好理解了。

下面将层次遍历和三种深度优先遍历的运行结果放到一起进行比较。

if __name__ == '__main__':
    tree = PerfectBinaryTree()
    for alpha in ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']:
        tree.append(alpha)
    print('层次遍历： ', end='')
    tree.show()
    print('先序遍历： ', end='')
    preorder_traversal(tree.get_root())
    print()
    print('中序遍历： ', end='')
    inorder_traversal(tree.get_root())
    print()
    print('后序遍历： ', end='')
    postorder_traversal(tree.get_root())
    print()

运行结果：

层次遍历： A B C D E F G H I J 
先序遍历： A B D H I E J C F G 
中序遍历： H D I B J E A F C G 
后序遍历： H I D J E B F G C A