2024年二叉树实验报告

数

据

結

构实验报告试验名称:二叉树的常見操作指导老師:金保华班级:计科02姓名:高延庆學号:07010208试验目的及规定1．掌握二叉树的存储实現。2．掌握二叉树的遍历思想。3．掌握二叉树的常見算法的程序实現。二、试验内容：1．输入字符序列，建立二叉链表。 2．中序遍历二叉树:递归算法。3．先序、中序、後序遍历二叉树:非递归算法。4．求二叉树的高度。5．求二叉树的叶子個数。6．借助队列实現二叉树的层次遍历。7．在主函数中设计一种简朴的菜單，分别调试上述算法。8．综合训练：為N個权值设计哈夫曼编码。三、试验源代码#include<stdio.h>#include<stdlib.h>#include<stack>#include<queue>usingnamespacestd;#defineElemTypeint//元素类型typedefstructBiTNode{\ ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;stack<BiTree>S;intHeight,Num;//树高及叶子個数intPreCreateBiTree(BiTree&T)//递归先序建立{ inte; scanf("%d",&e); if(!e){T=NULL;return1;} T=(BiTree)malloc(sizeof(BiTNode)); if(!T){printf("失败\n");return0;} T->data=e; PreCreateBiTree(T->lchild); PreCreateBiTree(T->rchild); return1;}voidMidVisit(BiTree&T)//递归中序遍历{ if(!T)return; MidVisit(T->lchild); printf("%d",T->data); MidVisit(T->rchild);}void_PreVisit(BiTree&T)//非递归先序遍历{ BiTreet=T,tem; //printf("非递归先序遍历:"); while(!S.empty())S.pop(); if(!T)return; S.push(t); while(!S.empty()){ while(S.top()){ printf("%d",(S.top())->data); S.push((S.top())->lchild); } S.pop(); if(S.empty())break; tem=S.top(); S.pop(); S.push(tem->rchild); } printf("\n");}void_MidVisit(BiTree&T)//非递归中序遍历{ BiTreet=T,tem; //printf("非递归中序遍历:"); while(!S.empty())S.pop();//清空栈 if(!T)return; S.push(t); while(!S.empty()){ while(S.top()){S.push((S.top())->lchild);} S.pop(); if(S.empty())break; tem=S.top();printf("%d",tem->data); S.pop(); S.push(tem->rchild);} printf("\n");}void_BehVisit(BiTree&T)//非递归後序遍历{ BiTreep; //printf("非递归後序遍历："); while(!S.empty())S.pop();//清空栈 S.push(T); while(!S.empty()){ while(S.top()!=NULL)S.push((S.top())->lchild); p=S.top(); S.pop(); boolflag=true; while(!S.empty()&&flag){ BiTreer=S.top(); if(r->rchild==p){ printf("%d",r->data); p=S.top();S.pop(); } else{ S.push(r->rchild); flag=false; } } } printf("\n");}voidLayerVisit(BiTree&T)//层次遍历{ BiTreetem; queue<BiTree>Q;//定义队列 printf("层次遍历:"); Q.push(T); while(!Q.empty()){ tem=Q.front(); Q.pop(); if(tem->lchild)Q.push(tem->lchild); if(tem->rchild)Q.push(tem->rchild); printf("%d",tem->data); } printf("\n");}voidNum_Height(BiTree&T,inth)//计算树的叶子個数和高度{ h++; if(!T)return; if(T->lchild==NULL&&T->rchild==NULL){ Num++; if(h>Height)Height=h; return; } //printf("%d",T->data);Num_Height(T->lchild,h); Num_Height(T->rchild,h);}//主函数的实現intmain(){ BiTreeT,Thrt;PreCreateBiTree(T);//先序创立二叉树 /*递归先序、中序、後序遍历*/ printf("递归先序、中序、後序遍历:\n"); PreVisit(T); printf("\n"); MidVisit(T);printf("\n"); BehVisit(T); printf("\n"); /*非递归先序、中序、後序遍历*/ printf("非递归先序、中序、後序遍历:\n"); _PreVisit(T);_MidVisit(T); _BehVisit(T); /*层次遍历*/ LayerVisit(T);/*中序线索线索二叉树并遍历*//* printf("中序线索线索二叉树并遍历:"); MidThread(T,Thrt); MidThreadVisit(Thrt);*/ /*计算二叉树的高度及叶子個数*/ Num=0;Height=0; inth=0; while(!S.empty())S.pop();//清空栈 Num_Height(T,h);printf("\n此树的高度和叶子個数分别為：%d%d\n",Height,Num);return0;}//测试实例//124005003600700//124005700030600试验成果试验總結本次试验是有关二叉树的常見操作，重要是二叉树的建立和遍历，在這次试验中我是按先序方式建立二叉树的，而遍历方式则相對要多某些，有递归的先序、中序、後序遍历，和非递归的先序、中序、後序遍历，此外尚有层次遍历，其中递归的三种遍历大同小异，此处仅以中序替代，非递归遍历