Python Tree遍历
Python - Tree Tree遍历详细操作教程
遍历是访问树的所有节点并且也可以打印其值的过程。因为所有节点都是通过边（链接）连接的，所以我们总是从根（头）节点开始。也就是说，我们不能随机访问树中的节点。我们使用三种方式遍历树-
有序遍历
前序遍历
后序遍历
有序遍历
在这种遍历方法中，首先访问左子树，然后访问根，然后再访问右子树。我们应该永远记住，每个节点都可能代表一个子树本身。
在下面的python程序中，我们使用Node类为根节点以及左右节点创建占位符。然后，我们创建一个插入函数以将数据添加到树中。最后，通过创建一个空列表并首先添加左节点，然后再添加根节点或父节点来实现有序遍历逻辑。最后，添加左节点以完成顺序遍历。请注意，对每个子树重复此过程，直到遍历所有节点为止。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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类为根节点以及左右节点创建占位符。然后，我们创建一个插入函数以将数据添加到树中。最后，通过创建一个空列表并先添加根节点，然后再添加左节点来实现预遍历逻辑。最后，添加右节点以完成预遍历。请注意，对每个子树都重复此过程，直到遍历所有节点为止。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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类为根节点以及左右节点创建占位符。然后，我们创建一个插入函数以将数据添加到树中。最后，通过创建一个空列表并先添加左节点，再添加右节点来实现后遍历逻辑。最后，添加根节点或父节点以完成后顺序遍历。请注意，对每个子树都重复此过程，直到遍历所有节点为止。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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]
