二叉树的建立与基本应用.doc

实验序号及名称：实验 三 二叉树实验 一、实验目的和要求(1)掌握二叉树的动态链表存储结构及表示。(2)掌握二叉树的三种遍历算法（递归和非递归两类）。(3)运用二叉树三种遍历的方法求解有关问题。二、实验环境和仪器设备Windows xp Dev C+三、相关资料和参考文献(教材和实验指导书以外)（无）四、实验任务求二叉树的高度。设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。 将按顺序方式存储在数组中的二叉树转换为二叉链表形式。复制一棵二叉树T到T1。交换二叉树中每个结点的左右孩子指针的值。设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二叉树的功能。五、实验内容（步骤）设计循环链表、双链表、链表的数据结构，并根据数据结构设计算法实现。编写源代码上机调试总结六、完整的实验结果记录（ 二叉树均以先序方式表示）求二叉树的高度。第一组数据： full41.cbt 结果：4第二组数据： cbitre.cbt 结果：6设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。第一组数据full41.cbt第二组数据： cbitre.cbt 将按顺序方式存储在数组中的二叉树转换为二叉链表形式。第一组数据： full41.cbt 第二组数据： cbitre.cbt 复制一棵二叉树T到T1。二叉树的构造问题。遍历二叉树，然后访问每一个结点以创建新的二叉树。交换二叉树中每个结点的左右孩子指针的值。遍历二叉树，对于每一个遍历到的结点交换其左右孩子指针。第一组数据： full41.cbt 第二组数据： cbitre.cbt 设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二叉树的功能。二叉树的构造问题。第一组数据： full41.cbt 第二组数据： cbitre.cbt 七、实验结果分析二叉树的先序输出：Full41.cbt:ABCDEFGHIJKLMNOCbitre.cbt:abcdefghijklmnopqrstuLetter.cbt :abcdefghijklmnopqrstuvwxyz求二叉树的高度。依次遍历每一个叶子结点，找到它们中的最大层次数。因此对于树full41.cbt，其高度即为每一个叶子节点层次数，为4。对于树cbitre.cbt，其高度为u的层次数，为6.设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。使用递归函数调用，输出中序次序结果：DCEBGFHAKJLINMO层次：434243414342434第二组数据： cbitre.cbt 结果：EDFCGBIHJAMLNKPQOSRUT层次：545342434143424535465将按顺序方式存储在数组中的二叉树转换为二叉链表形式。二叉树的构造问题。第n个结点的左右孩子分别为第2n+1和2n+2。第一组数据： full41.cbt ABICFJMDEGHKLNO.第二组数据： cbitre.cbt abqcnrvdkop.swy.elm.tu.x.z.fh.gij.结果略复制一棵二叉树T到T1。二叉树的构造问题。遍历二叉树，然后访问每一个结点以创建新的二叉树。新的二叉树和原来的二叉树输出结果都一样。结果略交换二叉树中每个结点的左右孩子指针的值。遍历二叉树，对于每一个遍历到的结点交换其左右孩子指针。第一组数据： full41.cbt 结果：AIMONJLKBFHGCED第二组数据： cbitre.cbt 结果：akortuspqlnmbhjicgdfe设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二叉树的功能。二叉树的构造问题。第一组数据： full41.cbt ABCD.E.FG.H.IJK.L.MN.O.第二组数据： cbitre.cbt abcde.f.g.hi.j.klm.n.op.q.rs.tu.结果略八、实验总结：构造二叉树时使用了文件流读入，只是在第一次输入数据时比较麻烦，但方便了以后数据输入。这个类中重用了几个方法，为了便于编程实现要求，又设置了几个私有的方法，使得整个成员方法比较多。这次代码长度较长，编写的时候变量拼写错误较多，比较麻烦。因为事先对程序的实现方法进行了较多的思考，所以调试过程相应的比较简单九、相关思考题及解答十、备注：函数手册BinTree();BinTree(const char* filename); /根据文件中的扩展二叉树的先序序列构造二叉树BinTree(Element_type tree ); /根据按顺序方式存储在数组中先序序列二叉树构造二叉树BinTree(BinTree & tree); /根据一棵二叉树构造新的二叉树BinTree();void build(const char *filename); /根据文件中扩展二叉树的先序序列创建二叉树void build(BinTree &tree ); /根据据按顺序方式存储在数组中先序序列二叉树创建二叉树void build(Element_type tree ); /复制一棵二叉树int height(BinTreeNode * node)const; /node的层次数int height()const; /二叉树的高度void midOrder()const; /中序遍历void midOrder(BinTreeNode * node ,int i)const; /中序遍历node子树void swapChild(); /交换左右孩子void swapChild(BinTreeNode * node); /交换node子树的左右孩子void clear(); /删除二叉树v