《二叉树操作设计和实现实验报告》由会员分享，可在线阅读，更多相关《二叉树操作设计和实现实验报告（7页珍藏版）》请在金锄头文库上搜索。
1、二叉树操作设计和实现实验报告一、 目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。二、 要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、 实验内容：1、分析、理解程序程序的功能是采用二叉树链表存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作。如输入二叉树ABD#CE#F#，链表示意图如下：ABCDEF2、添加中序和后序遍历算法/=LNR 中序遍历=void Inorder(BinTree T)if(T)Inorder(T-lchild);printf(%c,T-data);Inorder(T-rch
2、ild);/=LRN 后序遍历=void Postorder(BinTree T)if(T)Postorder(T-lchild);Postorder(T-rchild); printf(%c,T-data);3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。（1）输入完全二叉树的先序序列ABD#CE#F#，程序运行结果如下：(2)先序序列:(3)中序序列:(4)后序序列:(5)所有叶子及结点总数:(6)按层次遍历序列:四、源程序代码#includestdio.h#i
3、ncludestring.h#includestdlib.h#define Max 20 /结点的最大个数typedef struct node char data; struct node *lchild,*rchild;BinTNode; /自定义二叉树的结点类型typedef BinTNode *BinTree; /定义二叉树的指针int NodeNum,leaf; /NodeNum为结点数，leaf为叶子数/=基于先序遍历算法创建二叉树=/=要求输入先序序列，其中加入虚结点#以示空指针的位置=BinTree CreatBinTree(void) BinTree T; char ch;
4、if(ch=getchar()=#)return(NULL); /读入#，返回空指针 else T=(BinTNode *)malloc(sizeof(BinTNode); /生成结点T-data=ch;T-lchild=CreatBinTree(); /构造左子树T-rchild=CreatBinTree(); /构造右子树return(T); /=NLR 先序遍历=void Preorder(BinTree T) if(T) printf(%c,T-data); /访问结点Preorder(T-lchild); /先序遍历左子树Preorder(T-rchild); /先序遍历右子树 /=
5、LNR 中序遍历=void Inorder(BinTree T)if(T)Inorder(T-lchild);printf(%c,T-data);Inorder(T-rchild);/=LRN 后序遍历=void Postorder(BinTree T)if(T)Postorder(T-lchild);Postorder(T-rchild); printf(%c,T-data);/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T) int hl,hr,max; if(T)hl=TreeDepth(T-lchild); /求左深度hr=Tre
6、eDepth(T-rchild); /求右深度max=hlhr? hl:hr; /取左右深度的最大值NodeNum=NodeNum+1; /求结点数if(hl=0&hr=0) leaf=leaf+1; /若左右深度为0，即为叶子。return(max+1); else return(0);/=利用先进先出（FIFO）队列，按层次遍历二叉树=void Levelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%No
7、deNum;p=cqfront; /出队printf(%c,p-data); /出队，输出结点的值 if(p-lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-lchild; /左子树入队if(p-rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-rchild; /右子树入队 /=主函数=void main() BinTree root; int i,depth; printf(n);printf(Creat Bin_Tree； Input preorder:); /输入完全二叉树的先序序列， / 用#代表虚结
8、点，如ABD#CE#F# root=CreatBinTree(); /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。printf(t* select *n);printf(t1: Preorder Traversaln); printf(t2: Iorder Traversaln);printf(t3: Postorder traversaln);printf(t4: PostTreeDepth,Node number,Leaf numbern);printf(t5: Level Depthn); /按层次遍历之前，先选择4，求出该树的结点数。printf(t0: Exitn
9、);printf(t*n);scanf(%d,&i); /输入菜单序号（0-5）switch (i)case 1: printf(Print Bin_tree Preorder: );Preorder(root); /先序遍历break;case 2: printf(Print Bin_Tree Inorder: );Inorder(root); /中序遍历break;case 3: printf(Print Bin_Tree Postorder: );Postorder(root); /后序遍历break;case 4: depth=TreeDepth(root); /求树的深度及叶子数pr
10、intf(BinTree Depth=%d BinTree Node number=%d,depth,NodeNum);printf( BinTree Leaf number=%d,leaf);break;case 5: printf(LevePrint Bin_Tree: );Levelorder(root); /按层次遍历break;default: exit(1);printf(n); while(i!=0); 差距大，市场体系不完善，缺乏集聚效应等问题，同时充分考虑到该地周围已形成成熟建材商圈的商业价值，因地制宜的进行家居建材广场的建设。通过合理布局、优化环境、提升服务，该项目必将切实发挥商业区在引导消费、拉动经济增长方面的作用，促进该县经济和社会又好又快发展。7
