Python -二叉树 创建与遍历算法(很详细）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Python -二叉树 创建与遍历算法(很详细），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5239字，纯文字阅读大概需要8分钟。
内容图文
树表示由边连接的节点。它是一个非线性的数据结构。它具有以下特性。
- 一个节点被标记为根节点。
- 除根节点之外的每个节点都与一个父节点关联。
- 每个节点可以有一个arbiatry编号的chid节点。
我们使用前面讨论的os节点概念在python中创建了一个树数据结构。我们将一个节点指定为根节点，然后将更多的节点添加为子节点。下面是创建根节点的程序。
创建树
创建根
我们只需要创建一个节点类并向节点添加赋值。这就变成了只有根节点的树。
1
class
Node:
2
3
def
__init__
(self, data):
4 self.left = None #左节点 5 self.right = None #右节点 6 self.data = data #值 7 8def PrintTree(self):
9print(self.data)
1011 root = Node(10) #创建节点1213 root.PrintTree()
当执行上述代码时，将产生以下结果-
10
插入到树中
要插入到树中，我们使用上面创建的相同节点类，并向其添加一个插入类。insert类将节点的值与父节点的值进行比较，并决定将其添加为左节点或右节点。最后，PrintTree类用于打印树。
1
class
Node:
2
def
__init__
(self, data):
3 self.left = None
4 self.right = None
5 self.data = data
6 7def insert(self, data):
8# 将新值与父节点进行比较 9if self.data: # 非空10if data < self.data: #新值较小，放左边11if self.left is None: #若空，则新建插入节点12 self.left = Node(data)
13else: #否则，递归往下查找14 self.left.insert(data)
15elif data > self.data: #新值较大，放右边16if self.right is None: #若空，则新建插入节点17 self.right = Node(data)
18else: #否则，递归往下查找19 self.right.insert(data)
20else:
21 self.data = data
2223# 打印这棵树，中序遍历24def PrintTree(self):
25if self.left:
26 self.left.PrintTree()
27print( self.data),
28if self.right:
29 self.right.PrintTree()
3031# 使用insert方法添加节点32 root = Node(12)
33 root.insert(6)
34 root.insert(14)
35 root.insert(3)
3637 root.PrintTree()
当执行上述代码时，将产生以下结果-
3 6 12 14
遍历树
可以通过决定访问每个节点的序列来遍历树。我们可以清楚地看到，我们可以从一个节点开始，然后首先访问左子树，然后访问右子树。或者我们也可以先访问右子树然后访问左子树。因此，这些树遍历方法有不同的名称。我们将在实现树遍历算法的章节中详细研究它们。
Python树遍历算法
遍历是一个访问树的所有节点的过程，也可以打印它们的值。因为，所有节点都是通过边(链接)连接的，所以我们总是从根(头)节点开始。也就是说，我们不能随机访问树中的节点。我们走过一棵树有三种方法
- 先序遍历
- 中序遍历
- 后序遍历
顺序遍历
在这个遍历方法中，首先访问左子树，然后访问根，然后访问右子树。我们应该始终记住，每个节点都可以表示子树本身。
在下面的python程序中，我们使用Node类为根节点以及左右节点创建位置占位符。然后我们创建一个insert函数来向树中添加数据。最后，通过创建一个空列表并首先添加左节点，然后添加根节点或父节点来实现order遍历逻辑。最后添加左节点来完成order遍历。
1
class
Node:
2
3
def
__init__
(self, data):
4
5 self.left = None
6 self.right = None
7 self.data = data
8# Insert Node 9def insert(self, data):
1011if self.data:
12if data < self.data:
13if self.left is None:
14 self.left = Node(data)
15else:
16 self.left.insert(data)
17elif data > self.data:
18if self.right is None:
19 self.right = Node(data)
20else:
21 self.right.insert(data)
22else:
23 self.data = data
2425# Print the Tree26def PrintTree(self):
27if self.left:
28 self.left.PrintTree()
29print( self.data),
30if self.right:
31 self.right.PrintTree()
3233# 中序遍历34# Left -> Root -> Right35def inorderTraversal(self, root):
36 res = []
37if root:
38 res = self.inorderTraversal(root.left)
39 res.append(root.data)
40 res = res + self.inorderTraversal(root.right)
41return res
4243 root = Node(27)
44 root.insert(14)
45 root.insert(35)
46 root.insert(10)
47 root.insert(19)
48 root.insert(31)
49 root.insert(42)
50print(root.inorderTraversal(root))
当执行上述代码时，将产生以下结果-
[10、14、19、27、31、35、42]
预购遍历
在这种遍历方法中，首先访问根节点，然后访问左子树，最后访问右子树。
在下面的python程序中，我们使用Node类为根节点以及左右节点创建位置占位符。然后我们创建一个insert函数来向树中添加数据。最后，通过创建一个空列表并首先添加根节点，然后添加左节点来实现预排序遍历逻辑。最后添加正确的节点来完成预定遍历。请注意，此过程对每个子树重复，直到所有t
1
class
Node:
2
3
def
__init__
(self, data):
4
5 self.left = None
6 self.right = None
7 self.data = data
8# Insert Node 9def insert(self, data):
1011if self.data:
12if data < self.data:
13if self.left is None:
14 self.left = Node(data)
15else:
16 self.left.insert(data)
17elif data > self.data:
18if self.right is None:
19 self.right = Node(data)
20else:
21 self.right.insert(data)
22else:
23 self.data = data
2425# Print the Tree26def PrintTree(self):
27if self.left:
28 self.left.PrintTree()
29print( self.data),
30if self.right:
31 self.right.PrintTree()
3233# 先序遍历34# Root -> Left ->Right35def PreorderTraversal(self, root):
36 res = []
37if root:
38 res.append(root.data)
39 res = res + self.PreorderTraversal(root.left)
40 res = res + self.PreorderTraversal(root.right)
41return res
4243 root = Node(27)
44 root.insert(14)
45 root.insert(35)
46 root.insert(10)
47 root.insert(19)
48 root.insert(31)
49 root.insert(42)
50print(root.PreorderTraversal(root))
当执行上述代码时，将产生以下结果-
[27, 14, 10, 19, 35, 31, 42]
后序遍历
在这个遍历方法中，根节点最后访问，因此得名。首先遍历左子树，然后遍历右子树，最后遍历根节点。
在下面的python程序中，我们使用Node类为根节点以及左右节点创建位置占位符。然后我们创建一个insert函数来向树中添加数据。最后，通过创建一个空列表并先添加左节点后添加右节点来实现后序遍历逻辑。最后添加根节点或父节点来完成后序遍历。请注意，此过程将对每个子树重复，直到遍历所有节点。
1
class
Node:
2
3
def
__init__
(self, data):
4
5 self.left = None
6 self.right = None
7 self.data = data
8# Insert Node 9def insert(self, data):
1011if self.data:
12if data < self.data:
13if self.left is None:
14 self.left = Node(data)
15else:
16 self.left.insert(data)
17elif data > self.data:
18if self.right is None:
19 self.right = Node(data)
20else:
21 self.right.insert(data)
22else:
23 self.data = data
2425# Print the Tree26def PrintTree(self):
27if self.left:
28 self.left.PrintTree()
29print( self.data),
30if self.right:
31 self.right.PrintTree()
3233# 后序遍历34# Left ->Right -> Root35def PostorderTraversal(self, root):
36 res = []
37if root:
38 res = self.PostorderTraversal(root.left)
39 res = res + self.PostorderTraversal(root.right)
40 res.append(root.data)
41return res
4243 root = Node(27)
44 root.insert(14)
45 root.insert(35)
46 root.insert(10)
47 root.insert(19)
48 root.insert(31)
49 root.insert(42)
50print(root.PostorderTraversal(root))
当执行上述代码时，将产生以下结果-
[10、19、14、31、42、35、27]
原文：https://www.cnblogs.com/sxf1061700625/p/11319617.html
内容总结
以上是互联网集市为您收集整理的Python -二叉树 创建与遍历算法(很详细）全部内容，希望文章能够帮你解决Python -二叉树 创建与遍历算法(很详细）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。