Python二叉树的三种遍历方式

二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

遍历二叉树的方法主要分 3 种:先序遍历、中序遍历和后序遍历:
  • 先序遍历指最先遍历节点本身,再遍历节点的左子树,最后遍历右子树的遍历方法;
  • 中序遍历指最先遍历节点的左子树,再遍历节点本身,最后遍历右子树的遍历方法;
  • 后序遍历指最先遍历节点的左子树,再遍历右子树,最后遍历节点本身的一种遍历方法。

在图 1 中,L 是左子树,R 是右子树,D 当前节点。如果用这三个字母来表示 3 种遍历顺序,那么先序遍历是 DLR,中序遍历是 LDR,后序遍历是 LRD。
左右子树和根节点
图 1:左右子树和根节点

我们可以看出,在遍历的过程中,无论使用哪种顺序,都是先遍历左子树,再遍历右子树。所以,遍历顺序的先、中、后,实际上是指当前节点在整个遍历顺序中的位置。三种遍历的代码大同小异,注意语句的排列顺序即可。

下面首先是以列表下标表示的二叉树的遍历代码:
def preorder(i): #先序遍历
    if tree[i] == 0:
        return
    print(tree[i])
    preorder(2*i)
    preorder(2*i+1)
def inorder(i): #中序遍历
    if tree[i] == 0:
        return
    inorder(2*i)
    print(tree[i])
    inorder(2*i+1)
def postorder(i): #后序遍历
    if tree[i] == 0:
        return
    postorder(2*i)
    postorder(2*i+1)
    print(tree[i])

其次,是以存储的左右孩子地址来表示的二叉树,它的遍历函数写在类的内部:
class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None
class BST:
    def __init__(self, tlist):
        self.root = TreeNode(tlist[0])
        for i in tlist[1:]:
            self.insert(i)
    def preorder(self,node): #先序遍历
        if node is None:
            return
        print(node.val)
        self.preorder(node.left)
        self.preorder(node.right)
    def inorder(self,node): #中序遍历
        if node is None:
            return
        self.inorder(node.left)
        print(node.val)
        self.inorder(node.right)
    def postorder(self,node): #后序遍历
        if node is None:
            return
        self.postorder(node.left)
        self.postorder(node.right)
        print(node.val)

二叉树遍历的知识点介绍到这里就结束了。