python 树遍历算法

遍历是访问树的所有节点的过程，也可以打印它们的值。因为所有节点都通过边（链接）连接，所以我们始终从根（头）节点开始。也就是说，我们不能随机访问树中的一个节点。我们用三种方式来遍历一棵树

• 按顺序遍历
• 预购遍历
• 后序遍历

按顺序遍历

在这种遍历方法中，首先访问左侧子树，然后访问根，然后访问右侧子树。我们应该永远记住每个节点本身可能代表一个子树。

在下面的python程序中，我们使用node类为根节点以及左右节点创建占位符。然后我们创建一个插入函数来将数据添加到树中。最后，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))

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

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

预购遍历

在这种遍历方法中，首先访问根节点，然后访问左边的子树，最后访问右边的子树。

在下面的python程序中，我们使用node类为根节点以及左右节点创建占位符。然后我们创建一个插入函数来将数据添加到树中。最后，pre- order遍历逻辑通过创建一个空列表并首先添加根节点，然后添加左节点来实现。最后添加正确的节点以完成预订遍历。请注意，对于每个子树重复此过程，直到遍历所有节点。

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))

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

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

后序遍历

在这个遍历方法中，最后访问根节点，因此名称。首先我们遍历左子树，然后遍历右子树，最后遍历根节点。

在下面的python程序中，我们使用node类为根节点以及左右节点创建占位符。然后我们创建一个插入函数来将数据添加到树中。最后，通过创建一个空列表并首先添加左节点，然后添加右节点来实现post- order遍历逻辑。最后，根或父节点被添加以完成后序遍历。请注意，对于每个子树重复此过程，直到遍历所有节点。

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))

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

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