二叉树应用实验

1、二叉树应用实验实验目的掌握二叉树的动态链表存储结构及表示。掌握二叉树的三种遍历算法(递归和非递归两类)。运用二叉树三种遍历的方法求解有关问题。实验运行环境Visual C+实验任务为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库 函数程序btrechar.h中的函数的形式给出，并假设该库函数中定义了二叉树指 针和结点类型分别为bitre和bnode，以及部分常用运算，例如构建二叉树、以 某种方式显示二叉树等。各运算的名称较为直观，因而易于理解。为便于数据的 描述，将测试数据结构列出，并以一个文件名的形式给出标注，例如测试数据名 为full41.cbt的二叉树，其具体结构形式参

2、见二叉树列表中的标有full41.cbt 实验树为容第一题：求二叉树的高度。实验测试数据基本要求：第一组数据：full41.cbt第二组数据：cbitre.cbt实验准备：第一步：将指针指向根结点，判断根结点是否为空，如果是则返回0，否则 进入第二步。第二步：判断当前结点是否有子树，如果没有，当前结点的高度为1，否则 进入第三步。第三步：求当前结点左右子树的高度，并将两者中较大的加1作为该结点的 高度。进入下一个结点，返回第二步。第二题：设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。实验测试数据基本要求：第一组数据：full41.cbt第二组数据：cbitre.cbt实验准备：第

3、一步：将根节点的层次赋值为1。第二步：判断当前结点是否为先序遍历的最后一个结点，是则输出二叉树中 各结点的值及其所对应的层次数，并结束;否则，将当前结点的值以及层次输出， 并将它的层次加1赋值给左右子树的层次。移向下一个结点继续进行。第三题：将按顺序方式存储在数组中的二叉树转换为二叉链表形式。实验测试数据基本要求：第一组数据：full41.cbt第二组数据：letter.cbt实验准备：第一步：根据数组中的信息判断当前结点是否有左右子树，如果有并且 已经建立了连接，就返回上一层，如果有但没建立连接就建立它与子树的连接。 如果两个子树都没有，进入第二步。第二步：返回该结点的上一层，进入第二步。第

4、四题：复制一棵二叉树T到T1实验准备：第一步：先序遍历二叉树T的每一个结点，并动态建立一个与T结构相同的 二叉树T1。第二步：判断先序遍历有没有到终点。如没有则进行第三步，否则结束。第三步：对于遍历到的每一个结点将它的数据复制到T1中，并建立它与子 树的关系。继续进入下一个结点，返回第二步。第五题:交换二叉树中每个结点的左右孩子指针的值。实验测试数据基本要求：第一组数据：full41.cbt第二组数据：cbitre.cbt实验准备：第一步：判断当前节点是否为空，是则结束，否则，进入第二步。第二步:判断当前结点是否有左右子树，若是就将左右子树的值交换;否则， 进入第三步。第三步：若只有左子树就将

5、它的左子树的值赋给右子树，并将左子树的值赋 值为默认值nulldata,若只有右子树就将它的右子树的值赋给左子树，并将右子 树的值赋值为默认值nulldata。左右都没有，无操作。进入下一结点，返回第 二步。第六题：设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建 二叉树的功能。实验测试数据基本要求：第一组数据：full41.cbt第二组数据：cbitre.cbt实验准备：第一步：按照先序遍历的方式找到要插入的位置。第二步：将元素插入，并修改关系，以维护先序序列的顺序。实验程序#include#includechar tree50;int m;int n;struct Bnodech

6、ar data;struct Bnode*lchild,*rchild;class Binary_treeprivate:Bnode*root;public:Binary_tree()root=NULL; Bnode*& getBnode()return root;int max(int i,int j);void visit(Bnode*& T);void creat(Bnode*& T);void creat_tree();int first(Bnode*& T);访问函数创建二叉树函数创建顺序二叉树函数/第一题：求二叉树的高度函数void second(Bnode*& T,int m);

7、 /第二题：输出二叉树元素值及对应层次void third(Bnode*& T,int m); /第三题：将顺序二叉树转化为二叉链表Bnode*fourth(Bnode*& T); /第四题:将二叉树T复制到二叉树T2 void fifth(Bnode*& T);void sixth(Bnode*& T);第五题:交换二叉树左右孩子指针第六题：按先序序列遍历；void Binary_tree:creat(Bnode*& T) 创建二叉树函数char x;cinx;if(x=0)return;T=new Bnode;T-data=x;T-lchild =NULL;T-rchild =NULL;c

8、reat(T-lchild);creat(T-rchild);void Binary_tree:creat_tree()创建顺序二叉树函数char x;coutendl;cout请输入二叉树中元素的值，元素为空时输入“0”，输入“o” 结束x;for(n = 1;x!=o&nx;for(int b=1;b = n;b+)couttreebendl;coutendl;void Binary_tree:visit(Bnode*& T)访问函数if(T= = NULL)return;coutdataj) return i; else return j;int Binary_tree:first(Bn

9、ode*& T)第一题：求二叉树的高度函数if(T= = NULL)return 0;return max(first(T-lchild),first(T-rchild)+1;void Binary_tree:second(Bnode*& T,int m) 第二题：输出二叉树元素值及 对应层次if(T= = NULL)return ;second(T-lchild,m + 1);coutdatatnrchild,m + 1);void Binary_tree:third(Bnode*& T,int m)/第 三题：将顺序二叉树转化为二叉链表 if(treem =0)return;elseT=n

10、ew Bnode;T-data=treem;T-lchild = NULL;T-rchild = NULL;third(T-lchild,2*m);third(T-rchild,2*m + 1);Bnode*Binary_tree:fourth(Bnode*& T)/第 四题：将二叉树 T 复制到二叉树 T2if(T= = NULL)return NULL;Bnode*left,*right;left=fourth(T-lchild);right=fourth(T-rchild);Bnode*q=new Bnode;q-data=T-data;q-lchild=left;q-rchild =

11、right;root=q;return root;void Binary_tree:fifth(Bnode*& T)/第五题：交换二叉树左右孩子指针Bnode*p=new Bnode;if(T= = NULL)return ;p=T-lchild;T-lchild=T-rchild;T-rchild = p;fifth(T-lchild);fifth(T-rchild);void Binary_tree:sixth(Bnode*& T)/第六题：按先序序列遍历if(T= = NULL)return ;visit(T);sixth(T-lchild);sixth(T-rchild);int ma

12、in()int choice;Binary_tree B_1,B_2;coutendl;cout数据结构实验三二叉树应用实验endl;coutendl;cout第1题： 求二叉树的高度endl;cout第2题：按中序次序输出二叉树中各结点的值及其所对 应层次数endl;cout第3题：将顺序方式存储在数组中的二叉树转换为二叉 链表endl;cout第4题： 复制一棵二叉树T到T1endl;cout第5题：交换二叉树中每个结点的左右孩子指针的值 endl;cout第6题：设计算法以实现下面所提到以扩展二叉树的先 序序列作为输入构建二叉树的功能endl;cout退出程序:0endl;coutend

13、l;cout请选择一道题choice;switch(choice)case 1：cout请按先序序列输入二叉树中元素的值，元素为空时 输入 “o endl;B_1.creat(B_1.getBnode();cout 高 度 为B_1.first(B_1.getBnode()endl;break;case 2：cout请按先序序列输入二叉树中元素的值，元素为空时输入 “o endl;B_1.creat(B_1.getBnode();B_1.second(B_1.getBnode(),1); break;case 3:B_1.creat_tree();B_1.third(B_1.getBnode(),1);cout”输 出二叉链表endl;B_1.sixth(B_1.getBnode();break;case 4:cout请按先序序列输入二叉树中元素的值，元素为空时 输入 “o endl;B_1.creat(B_1.getBnode();B_2.fourth(B_1.getBnode();cout 输出二叉树 2endl;B_2.sixth(B_2.getBnode();break;case 5:cout请按先序序列输入二叉树中元素的值，元素为空时 输入 “o endl;B_1.creat(B_1.getBnode();B_1.fifth(B_1.g