无

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程序中，使用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程序中，使用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))

移动端设备除iPad Pro外，其它移动设备仅能阅读基础的文本文字。
建议使用PC或笔记本电脑，浏览器使用Chrome或FireFox进行浏览，以开启左侧互动实验区来提升学习效率，推荐使用的分辨率为1920x1080或更高。
我们坚信最好的学习是参与其中这一理念，并致力成为中文互联网上体验更好的学练一体的IT技术学习交流平台。

您可加QQ群：575806994，一起学习交流技术,反馈网站使用中遇到问题。
内容、课程、广告等相关合作请扫描右侧二维码添加好友。

《动手学数据结构与算法-Python实现》

Python实现算法:树遍历

按顺序遍历

前序遍历

后序遍历