一、实验目的
1．掌握二叉树的概念和二叉树的性质；
2．掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构；
3．掌握二叉树的基本运算算法和二叉树的先序、中序和后序遍历的递归算法的实现。
二、实验环境
1．Windows操作系统的计算机
2．Python3.7环境平台和PyCharm编辑器
三、实验说明
1．实现二叉树的先序、中序和后序遍历的递归算法程序设计方法。
2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。
3．自主编写程序，必要时参考相关资料。
4．实验学时：2学时
四、实验内容和步骤
1．实验内容
假设二叉树中每个节点值为单个字符，采用二叉链存储结构存储。二叉树bt的后序遍历序列为a1，a2，…,an，设计一个算法按an，an-1，…,a1的次序输出各结点值。
参考思路：
from collections import deque
class BTNode: #二叉链中结点类
def __init__(self,d=None): #构造方法
……
class BTree: #二叉树类
def __init__(self,d=None): #构造方法
……
def SetRoot(self,r): #设置根结点为r
……
def DispBTree(self): #返回二叉链的括号表示串
……
def _DispBTree1(self,t): #被DispBTree方法调用
…….
if __name__ == '__main__':
b=BTNode('A') #建立各个结点
p1=BTNode('B')
……
b.lchild=p1 #建立结点之间的关系
b.rchild=p2
……
bt=BTree()
bt.SetRoot(b)
print("bt:",end=' '); print(bt.DispBTree())
from BTree import BTree,BTNode
def RePostOrder(bt): #求解算法
_RePostOrder(bt.b)
def _RePostOrder(t):
if _________:
print(t.data+" ")
_______________
_______________
#主程序
b=BTNode('A') #建立各个结点
p1=BTNode('B')
……
b.lchild=p1 #建立结点之间的关系
b.rchild=p2
……
bt=BTree()
bt.SetRoot(b)
print("bt:",end=' ');print(bt.DispBTree())
print("求解结果:")
_______________
2．实验步骤
（1）分析实验内容，写出程序大致框架或完整的程序代码。
（2）进入Python集成环境。
（3）编辑程序并进行保存。
（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。
（5）检查程序输出结果。
五、实验代码与结果（程序运行代码及其结果）
1． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
from collections import deque
class BTNode:
def __init__(self,d=None): #构造方法
self.data=d
self.lchild=None
self.rchild=None
class BTree:
def __init__(self,d=None): #构造方法
self.root=d
def SetRoot(self,r): #设置根结点为r
self.root=r
def DispBTree(self): #返回二叉链的括号表示串
res=self._DispBTree1(self.root)
return res[:-1]
def _DispBTree1(self,t): #被DispBTree1调用
if t==None:
return ''
elif t.lchild==None and t.rchild==None:
return str(t.data)+'^'
else:
return str(t.data)+'('+self._DispBTree1(t.lchild)+')('+self._DispBTree1(t.rchild)+')'
def RePostOrder(bt): #求解算法
print("后序遍历结果：", end="")
_RePostOrder(bt.root)
def _RePostOrder(t):
if t:
_RePostOrder(t.lchild)
_RePostOrder(t.rchild)
print(t.data, end=" ")
if __name__ == '__main__':
b=BTNode('A')
p1=BTNode('B')
p2=BTNode('C')
p3=BTNode('D')
p4=BTNode('E')
p5=BTNode('F')
b.lchild=p1
b.rchild=p2
p1.lchild=p3
p1.rchild=p4
p2.lchild=p5
bt=BTree()
bt.SetRoot(b)
print("bt:",end=' ');print(bt.DispBTree())
RePostOrder(bt)