实验二二叉树实验报告

实验二二叉树实验报告110228刘宇110211991.实验目的掌握二叉树的存储结构2.实验内容1．对给定二叉树用链式存储结构；利用队列与栈对二叉树进行运算。2．按层次输出所有结点。3．输出所有叶子结点。4．将所有左右子树值交换。3.实验步骤和要求1．分别编制实验内容中题2、3、4的三个子程序。2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。（1）输入二叉树用链式结构存储；（2）调用题2的子程序，并输出结果；（3）调用题3的子程序，并输出结果；（4）调用题4的子程序，并输出结果；3．自行设计一棵二叉树，重复步骤2。4．整理程序清单与所有结果，并写出实验报告。15403070604510206984.方法说明（1）二叉树的链式存储结构二叉树的每一个结点i有三个域：值域V（i），左链域L（i），右链域R（i）。我们分别用三个一维数组表示它们，并用头指针HBT指向二叉树的根结点。具体存储方案由读者自行考虑。（2）按层次输出所有结点为了达到按层次扫描结点的目的，需要设置一个容量足够大的循环队列（可以用一个首尾相接的一维数组模拟）。初始时，将根结点序号入队。然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出，且依次将此结点的左右链指针入队。（3）输出所有叶子结点叶子结点的左右指针域均为零。因此，为了输出所有叶子结点，需要设置一个容量足够大的栈S（可以用一个一维数组模拟它，栈底在数组的第一个元素处）。具体过程是：从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出次叶子结点；否则将非零的右指针和左指针值推入堆栈。然后从栈中退出一个结点序号重新进行这个过程，直至栈空为止。（4）将所有左右子树值交换这个问题的处理和输出所有叶子结点的问题很类似，只要将非叶子结点的左右指针交换即可，其算法如下：五、程序代码：#includeiostream#includefstreamusingnamespacestd;structtnode//链式存储节点{intdata,lv;tnode*left,*right;};structlnode//单向链表节点用来实现队列和栈{tnode*data;lnode*next;};classmyList//列表类提供初始化，插入，读取，删除，清除方法{private:lnode*rear,*last;public:voidLinit()//{rear=(lnode*)malloc(sizeof(lnode));last=rear;last-next=NULL;last-data=NULL;}boolLempty()//judgingafterwardrequired{if(last==rear)returntrue;elsereturnfalse;}voidinsert(tnode*d){lnode*p;p=(lnode*)malloc(sizeof(lnode));p-data=d;last-next=p;p-next=NULL;last=p;}lnode*read(){lnode*p;p=rear;if(rear-next)rear=rear-next;elsecoutThelistisempty!\n;returnp;}};classmyStack//栈类提供初始化，压栈，出栈，销毁方法{private:lnode*top;public:voidSinit(){top=(lnode*)malloc(sizeof(lnode));top-data=NULL;top-next=NULL;}voidpush(tnode*d){lnode*p;p=(lnode*)malloc(sizeof(lnode));p-data=d;p-next=top;top=p;}lnode*pop(){lnode*p;if(top-next){p=top;top=top-next;returnp;}else{coutTheStackisEmpty!\n;returnNULL;}}boolSempty(){if(top-next==NULL)returntrue;returnfalse;}};classbiTree//二叉树类提供初始化，先序建树，按层读取，交换等方法{private:tnode*r,*p;public:tnode*getRoot(){returnr;}voidTinit(){r=(tnode*)malloc(sizeof(tnode));r-data=-1;r-left=NULL;r-right=NULL;r-lv=0;}tnode*firstCreate(tnode*t,intl){intad;t=(tnode*)malloc(sizeof(tnode));cinad;t-data=ad;t-lv=l;if(ad!=0){t-left=firstCreate(t-left,l+1);t-right=firstCreate(t-right,l+1);}returnt;}voidlvlRead(tnode*t){tnode*q;lnode*p;myListml;ml.Linit();ml.insert(t);//ml.read();do{p=ml.read();p=p-next;q=p-data;if(q-data){coutq-data'';ml.insert(q-left);ml.insert(q-right);}else{if(ml.Lempty())break;}}while(!ml.Lempty());}voidleafRead(tnode*t){tnode*q,*l,*r;lnode*p;myStackms;ms.Sinit();ms.push(t);do{p=ms.pop();q=p-data;l=q-left;r=q-right;if(l-data==0&&r-data==0)coutq-data'';else{if(r-data!=0)ms.push(r);if(l-data!=0)ms.push(l);}}while(!ms.Sempty());}voidallReverse(tnode*t){tnode*q,*l,*r,*tmp;lnode*p;myStackms;ms.Sinit();ms.push(t);do{p=ms.pop();q=p-data;l=q-left;r=q-right;if(l-data!=0||r-data!=0){tmp=q-left;q-left=q-right;q-right=tmp;}if(l-data!=0)ms.push(l);if(r-data!=0)ms.push(r);}while(!ms.Sempty());}voidfirstTrav(tnode*t){intm;tnode*l,*r;l=t-left;r=t-right;m=t-data;if(m){coutm'';if(l-data)firstTrav(l);if(r-data)firstTrav(r);}}voidmidTrav(tnode*t){intm;tnode*l,*r;l=t-left;r=t-right;m=t-data;if(m){if(l-data)firstTrav(l);coutm'';if(r-data)firstTrav(r);}}};intmain(){inti,j,n;tnode*rt;biTreebt;rt=bt.getRoot();//使用rt指针记录指向二叉树的根节点//使用firstCreate函数以先序序列建立二叉树，0表示结束节点rt=bt.firstCreate(rt,0);//先序打印所有节点cout先序打印二叉树：\n;bt.firstTrav(rt);coutendl;//使用lvlRead()方法按层打印所有节点cout按层打印二叉树：\n;bt.lvlRead(rt);coutendl;//使用leafRead()方法打印所有叶节点cout打印二叉树所有叶子节点：\n;bt.leafRead(rt);coutendl;//使用leafRead()方法交换所有左右节点bt.allReverse(rt);cout二叉树交换后先序打印：\n;bt.firstTrav(rt);//先序打印所有节点//system(pause);return0;}六、结果分析编制实验内容中题2、3、4的三个子程序。按先序输入以上二叉树159820300040001000604506070000,其中0代表结尾。存入链式存储结构。1、分别按先序打印二叉树；2、按层打印二叉树；2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。（1）输入二叉树用链式结构存储；（2）调用题2的子程序，并输出结果；（3）调用题3的子程序，并输出结果；（4）调用题4的子程序，并输出结果；3．自行设计一棵二叉树，重复步骤2。1540307060451020698如图，先序序列为1354100120002103100结果：七、实验反思：本次实验中使用链式结构直观的构造了二叉树数据结构，同时，构造了一维的队列和栈对二叉树的搜索和遍历进行辅助存储。其中实现二叉树时，以特殊符号标记结束节点，方便输入和建立二叉树，使得使用唯一确定的先序序列即可表13521411231达二叉树。递归建立二叉树时，需要注意返回二叉树子树的根节点地址给上级节点左右子节点记录。实现队时，使用单向链表，在堆动态分配存储空间，空间效率更高。基于面向对象思想，设计了二叉树类，具体实现了初始化，先序遍历，按层遍历，交换左右节点的接口，可扩展性较强。