Python实现二叉树结构及三种遍历 教你怎样使用Python实现二叉树结构及三种遍历
小白地瓜 人气:0想了解教你怎样使用Python实现二叉树结构及三种遍历的相关内容吗,小白地瓜在本文为您仔细讲解Python实现二叉树结构及三种遍历的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Python实现二叉树结构,python实现二叉树的三种遍历方式,下面大家一起来学习吧。
一:代码实现
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] """
加载全部内容