1 问题
Python中二叉树的先序遍历、中序遍历、后序遍历。
2 方法
- 先序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： ⑴ 访问根结点； ⑵ 遍历左子树； ⑶ 遍历右子树。
- 中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： ⑴ 遍历左子树； ⑵ 访问根结点； ⑶ 遍历右子树。
- 后序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴ 遍历左子树；⑵ 遍历右子树；⑶ 访问根结点。
代码清单 1
代码语言：text复制'''
树的构建：
3
9 20
15 7
'''
class Tree():
'树的构造'
def __init__(self,data, left = 0, right = 0):
self.data = data
self.left = left
self.right = right
def __str__(self):
return str(self.data)
class MyTree():
'二叉树的实现'
def __init__(self,base = 0):
self.base = base
def _Empty(self):
'判断是否为空树'
if self.base == 0:
return True
else:
return False
def front_search(self,tree_base):
'前序遍历:根-左-右'
if tree_base == 0:
return
print(tree_base.data)
self.front_search(tree_base.left)
self.front_search(tree_base.right)
def middle_search(self,tree_base):
'中序遍历:左-根-右'
if tree_base == 0:
return
self.middle_search(tree_base.left)
print(tree_base.data)
self.middle_search(tree_base.right)
def behind_search(self,tree_base):
'后序遍历:左-右-根'
if tree_base == 0:
return
self.behind_search(tree_base.left)
self.behind_search(tree_base.right)
print(tree_base.data)
# test tree
tree1 = Tree(data=15)
tree2 = Tree(data=7)
tree3 = Tree(20,tree1,tree2)
tree4 = Tree(data=9)
base = Tree(3,tree4,tree3)
btree = MyTree(base)
print('前序遍历:')
btree.front_search(btree.base)
print('中序遍历:')
btree.middle_search(btree.base)
print('后序遍历:')
btree.behind_search(btree.base)3 结语
我们针对Python中二叉树的先序遍历、中序遍历、后序遍历的问题，运用书上相应的基础知识，通过代码运行成功证明该方法是有效的，二叉树的遍历的应用非常广泛，希望通过未来的学习我们能写出更多长的、复杂的代码和程序。
