Python算法设计：树节点遍历（顺序、前序、后序）

遍历就是访问树的每个节点的过程，也可以打印它们的值。由于所有节点都通过边（链接）连接，因此始终从根（头）节点开始。也就是说，我们不能随机访问树中的节点。以下是三种遍历树的方法 -

• 顺序遍历
• 前序遍历
• 后序遍历

顺序遍历

在这种遍历方法中，左子树访问就是右子树。我们应该永远记住，每个节点本身都可以代表一个子树。

在以下Python程序中，类Node用于为根节点以及左右节点创建占位符。然后创建一个 insert() 函数将数据添加到树中。最后，通过创建一个空列表，先添加根节点或父节点，再添加左节点，实现Inorder遍历逻辑。最后添加左节点即可完成Inorder遍历。请注意，对每个子树重复此过程，直到遍历完所有节点。

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Inorder traversal
# Left -> Root -> Right
    def inorderTraversal(self, root):
        res = []
        if root:
            res = self.inorderTraversal(root.left)
            res.append(root.data)
            res = res + self.inorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))

Python

完成上面的示例代码，得到如下结果 -

[10, 14, 19, 27, 31, 35, 42]

Shell

前序遍历

在这种遍历方法中，根节点在左边，那么访问的子节点就是最后的子树在右边

在以下Python程序中，类Node用于为根节点以及左右节点创建占位符。然后创建一个 insert() 函数将数据添加到树中。最后通过创建一个空链表，先添加根节点，再添加左节点，实现前序遍历的遍历逻辑。最后添加正确的节点即可完成前序遍历。请注意，对每个子树重复此过程，直到遍历完所有节点。

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Preorder traversal
# Root -> Left ->Right
    def PreorderTraversal(self, root):
        res = []
        if root:
            res.append(root.data)
            res = res + self.PreorderTraversal(root.left)
            res = res + self.PreorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

Python

当执行上述代码时，会产生以下结果 -

[27, 14, 10, 19, 35, 31, 42]

Shell

后序遍历

在该遍历方法中，访问的是最后一个根节点。首先遍历左子树，然后遍历右子树，最后遍历根节点。

在以下Python程序中，类Node用于为根节点以及左右节点创建占位符。然后创建一个 insert() 函数将数据添加到树中。最后，通过创建一个空列表并添加左节点，然后添加右节点来实现后序遍历逻辑。最后添加根节点或父节点即可完成后序遍历。请注意，对每个子树重复此过程，直到遍历完所有节点。参考以下代码实现 -

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Postorder traversal
# Left ->Right -> Root
    def PostorderTraversal(self, root):
        res = []
        if root:
            res = self.PostorderTraversal(root.left)
            res = res + self.PostorderTraversal(root.right)
            res.append(root.data)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

Python

上面的代码执行时，会产生以下结果 -

[10, 19, 14, 31, 42, 35, 27]