二叉树设计

定义节点类

class Node:
# 修改初始化方法
def init(self,value):
self.value = value # 节点值
self.left = None # 左子树
self.right = None # 右子树

定二叉树类

class BinaryTree:
# 修改初始化方法
def init(self,root=None):
self.root = root # 根节点
# 定义添加节点方法 广度优先
def add(self,value):
if self.root == None:
self.root = Node(value)
return # 根节点已存在，不再添加
# 根节点不为空，开始遍历
queue= []
# 将根节点加入队列
queue.append(self.root)
# 循环判断，哪个节点为空，将新节点加入该节点
while True:
# 从队列中取出根节点
node = queue.pop(0)
# 判断该节点左子树是否为空
if node.left == None:
node.left = Node(value)
return
else:
queue.append(node.left)
# 判断该节点右子树是否为空
if node.right == None:
node.right = Node(value)
return
else:
queue.append(node.right)
# 遍历二叉树 广度优先
def traverse(self,root):
# 判断根节点是否为空，若为空，则返回
if self.root == None:
return
# 创建队列
queue = []
# 将根节点添加到队列中
queue.append(self.root)
# 循环遍历,根据队列长度来循环，需要大于0
while len(queue) > 0:
# 从队列中取出节点
node = queue.pop(0)
# 打印节点内容
print(node.value,end=' ')
# 判断左子树是否为空，若不为空，则添加到队列中
if node.left != None:
queue.append(node.left)
# 判断右子树是否为空，若不为空，则添加队列中
if node.right != None:
queue.append(node.right)
# 遍历二叉树，深度优先，先序遍历 （根左右）
def pre_traverse(self,root):
# 判断根节点是否为空,不为空则执行
if root is not None:
# 打印根节点
print(root.value,end=' ')
# 递归调用左子树
self.pre_traverse(root.left)
# 递归调用右子树
self.pre_traverse(root.right)
# 遍历二叉树，深度优先，中序遍历 (左根右)
def mid_traverse(self,root):
# 判断根节点是否为空，不为空则执行
if root is not None:
# 递归调用左子树
self.mid_traverse(root.left)
# 打印根节点
print(root.value,end=' ')
# 递归调用右子树
self.mid_traverse(root.right)
# 遍历二叉树，深度优先，后序遍历 (左右根)
def post_traverse(self,root):
# 判断根节点是否为空，不为空则执行
if root is not None:
# 递归调用左子树
self.post_traverse(root.left)
# 递归调用右子树
self.post_traverse(root.right)
# 打印根节点
print(root.value,end=' ')

测试

def Dm01():
# 创建二叉树
tree = BinaryTree()
# 添加节点
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
tree.add(7)
tree.add(8)
tree.add(9)
# 先序遍历
print("\n先序遍历：")
tree.pre_traverse(tree.root)
# 中序遍历
print("\n中序遍历：")
tree.mid_traverse(tree.root)
# 后序遍历
print("\n后序遍历：")
tree.post_traverse(tree.root)

运行测试

if name == 'main':
Dm01()1.