一、思维导图（相关概念）
二、遍历
def prior_show(self, node):
"""
先序遍历、根左右
"""
if node is not None:
print(node.data, end=" ")
self.prior_show(node.lchild)
self.prior_show(node.rchild)
def mid_show(self, node):
"""
中序遍历、左根右
"""
if node is not None:
self.mid_show(node.lchild)
print(node.data, end=" ")
self.mid_show(node.rchild)
def post_show(self, node):
"""
后序遍历、左 右 根
"""
if node is not None:
self.post_show(node.lchild)
self.post_show(node.rchild)
print(node.data, end=" ")
三、二叉树的初始化以及树的创建
class Node():
def __init__(self, data, lchild=None, rchild=None):
self.data = data
self.lchild = lchild
self.rchild = rchild
class Tree():
def __init__(self, root=None):
self.root = root # 根节点
self.index = 0 # 用于遍历一串数据的索引
def tree_creat(self, data_str):
if self.index >= len(data_str): # 最大条件，数据读取完之后直接返回
return None
# 开始创建,开始之前先读取对应的数据并且后移index
data = data_str[self.index]
self.index += 1
# 开始递归,先写一个可以终止递归的目标条件
if data == "#": # 终止递归的条件:直到没有左or右子树
return None
node = Node(data)
node.lchild = self.tree_creat(data_str) # 当满足终止递归的条件时触发return None才能进一步往下走走到return node开始逐步往回收递归函数,并向父函数返回node
node.rchild = self.tree_creat(data_str)
return node
四、完整代码
class Node():
def __init__(self, data, lchild=None, rchild=None):
self.data = data
self.lchild = lchild
self.rchild = rchild
class Tree():
def __init__(self, root=None):
self.root = root # 根节点
self.index = 0 # 用于遍历一串数据的索引
def tree_creat(self, data_str):
if self.index >= len(data_str): # 最大条件，数据读取完之后直接返回
return None
# 开始创建,开始之前先读取对应的数据并且后移index
data = data_str[self.index]
self.index += 1
# 开始递归,先写一个可以终止递归的目标条件
if data == "#": # 终止递归的条件:直到没有左or右子树
return None
node = Node(data)
node.lchild = self.tree_creat(data_str) # 当满足终止递归的条件时触发return None才能进一步往下走走到return node开始逐步往回收递归函数,并向父函数返回node
node.rchild = self.tree_creat(data_str)
return node
def prior_show(self, node):
"""
先序遍历、根左右
"""
if node is not None:
print(node.data, end=" ")
self.prior_show(node.lchild)
self.prior_show(node.rchild)
def mid_show(self, node):
"""
中序遍历、左根右
"""
if node is not None:
self.mid_show(node.lchild)
print(node.data, end=" ")
self.mid_show(node.rchild)
def post_show(self, node):
"""
后序遍历、左 右 根
"""
if node is not None:
self.post_show(node.lchild)
self.post_show(node.rchild)
print(node.data, end=" ")
if __name__ == '__main__':
# data_str = input("输入二叉树：")
data_str = "ABD##E##CFH###G##"
# 创建二叉树
tree = Tree()
tree.root = tree.tree_creat(data_str)
# 遍历
print("先序遍历结果")
tree.prior_show(tree.root)
print()
print("中序遍历结果")
tree.mid_show(tree.root)
print()
print("后序遍历结果")
tree.post_show(tree.root)
print()
# ABD##E##CFH###G##