《二叉树操作设计和实现实验报告.docx》由会员分享，可在线阅读，更多相关《二叉树操作设计和实现实验报告.docx（5页珍藏版）》请在三一办公上搜索。
1、二叉树操作设计和实现实验报告二叉树操作设计和实现实验报告 一、 目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 二、 要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。 三、 实验内容： 1、分析、理解程序 程序的功能是采用二叉树链表存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作。 如输入二叉树ABD#CE#F#，链表示意图如下： A 1 2、添加中序和后序遍历算法 /=LNR 中序遍历= voidInorder(BinTree T) if(T) Inorder(T-lchild); printf
2、(%c,T-data); Inorder(T-rchild); /=LRN 后序遍历= voidPostorder(BinTree T) if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); 3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点，如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。 输入完全二叉树的先序序列ABD#CE#F#，程序运行结果如下： 2 (2)先序序列: (3)中序序列: (4)后序序列: 3 (5)所有叶子及结点总数: (6
3、)按层次遍历序列: 四、源程序代码 #includestdio.h #includestring.h #includestdlib.h #define Max 20 /结点的最大个数 typedefstruct node char data; struct node *lchild,*rchild; BinTNode; /自定义二叉树的结点类型 typedefBinTNode *BinTree; /定义二叉树的指针 intNodeNum,leaf; /NodeNum为结点数，leaf为叶子数 /=基于先序遍历算法创建二叉树= /=要求输入先序序列，其中加入虚结点#以示空指针的位置= BinTr
4、eeCreatBinTree(void) BinTree T; 4 charch; 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-lchi
5、ld); /先序遍历左子树 Preorder(T-rchild); /先序遍历右子树 /=LNR 中序遍历= voidInorder(BinTree T) if(T) Inorder(T-lchild); printf(%c,T-data); Inorder(T-rchild); /=LRN 后序遍历= voidPostorder(BinTree T) if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); /=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法= intTreeDepth(BinTree T) 5
6、 inthl,hr,max; if(T) hl=TreeDepth(T-lchild); /求左深度 hr=TreeDepth(T-rchild); /求右深度 max=hlhr? hl:hr; /取左右深度的最大值 NodeNum=NodeNum+1; /求结点数 if(hl=0&hr=0) leaf=leaf+1; /若左右深度为0，即为叶子。 return(max+1); else return(0); /=利用先进先出队列，按层次遍历二叉树= voidLevelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定义结点的
7、指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%NodeNum; 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; inti,depth; printf(n); printf
8、(CreatBin_Tree； Input preorder:); /输入完全二叉树的先序序列， / 用#代表虚结点，如ABD#CE#F# root=CreatBinTree; /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。 printf(t* select *n); printf(t1: Preorder Traversaln); 6 printf(t2: Iorder Traversaln); printf(t3: Postorder traversaln); printf(t4: PostTreeDepth,Nodenumber,Leaf numbern); prin
9、tf(t5: Level Depthn); /按层次遍历之前，先选择4，求出该树的结点数。 printf(t0: Exitn); printf(t*n); scanf(%d,&i); /输入菜单序号 switch (i) case 1: printf(Print Bin_tree Preorder: ); Preorder(root); /先序遍历 break; case 2: printf(Print Bin_TreeInorder: ); Inorder(root); /中序遍历 break; case 3: printf(Print Bin_TreePostorder: ); Postorder(root); /后序遍历 break; case 4: depth=TreeDepth(root); /求树的深度及叶子数 printf(BinTree Depth=%d BinTree Node number=%d,depth,NodeNum); printf( BinTree Leaf number=%d,leaf); break; case 5: printf(LevePrintBin_Tree: ); Levelorder(root); /按层次遍历 break; default: exit(1); printf(n); while(i!=0); 7
