教你如何使用Python实现二叉树结构及三种遍历
短信预约 -IT技能 免费直播动态提醒
一：代码实现
class TreeNode:
"""节点类"""
def __init__(self, mid, left=None, right=None):
self.mid = mid
self.left = left
self.right = right
# 树类
class Tree:
"""树类"""
def __init__(self, root=None):
self.root = root
def add(self, item):
# 将要添加的数据封装成一个node结点
node = TreeNode(item)
if not self.root:
self.root = node
return
queue = [self.root]
while queue:
cur = queue.pop(0)
if not cur.left:
cur.left = node
return
else:
queue.append(cur.left)
if not cur.right:
cur.right = node
return
else:
queue.append(cur.right)
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
二：遍历
在上述树类代码基础上加遍历函数，基于递归实现。
先序遍历：
先序遍历结果是：0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6
# 先序遍历
def preorder(self, root, result=[]):
if not root:
return
result.append(root.mid)
self.preorder(root.left, result)
self.preorder(root.right, result)
return result
print("先序遍历")
print(tree.preorder(tree.root))
"""
先序遍历
[0, 1, 3, 4, 2, 5, 6]
"""
中序遍历：
中序遍历结果是：3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6
# 中序遍历
def inorder(self, root, result=[]):
if not root:
return result
self.inorder(root.left, result)
result.append(root.mid)
self.inorder(root.right, result)
return result
print("中序遍历")
print(tree.inorder(tree.root))
"""
中序遍历
3, 1, 4, 0, 5, 2, 6]
"""
后续遍历
后序遍历结果是：3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0
# 后序遍历
def postorder(self, root, result=[]):
if not root:
return result
self.postorder(root.left, result)
self.postorder(root.right, result)
result.append(root.mid)
return result
print("后序遍历")
print(tree.postorder(tree.root))
"""
后序遍历
[3, 4, 1, 5, 6, 2, 0]
"""
到此这篇关于教你如何使用Python实现二叉树结构及三种遍历的文章就介绍到这了,更多相关Python实现二叉树结构及三种遍历内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
