实验二、二叉树操作

《实验二、二叉树操作》由会员分享，可在线阅读，更多相关《实验二、二叉树操作（15页珍藏版）》请在金锄头文库上搜索。

1、实验二、二叉树操作实验二、二叉树操作、目的掌握二叉树的定义、性质及存储方式，各种遍IWJ历算法。二、要求采用二叉树链表作为存储结构，完成二叉树的 作，求所有叶子及结点总数的操作。建立，先序、中序和后序以及按层次遍历的操iwJ三、实验内容1、分析程序存储结构Typedef struct nodeChar data;Struct node*lchild/rchild;BinTNode;/ 自定义二叉树的结点类型typedef BinTNdoe *BinTree; 自定义二叉树的指针int NodeNum,leaf;/NodeNum为结点数，leaf为叶子数主要流程及模块调用进入主函数先进行创建二叉

2、树CreatBinTreeiwJ出现主界面调用先序，中序，后序，层次， 以及求所有叶子及结点总数的函数进行遍 历。2、测试内容及结果：设计一棵二叉树，输入完全二叉树的先序序 列，用#代表虚结点（空指针），如liiiJABD#CE#F#，建立二叉树，求出先序、 中序和后序以及按层次遍历序列，求所有叶子 及结点总数。Cneat Bin_Tree- npu pFenvdei*：abd.ttttttcettttfttU hnk -njc e lect JCNNNK WN NJC1 : Preorder Tiaucrsal2 : larder1 Trtyerscil3 - Fostorder traij

3、ersal4: PDstIreeDept：li,Node nLimtieE,Leaf number 5: Leuel Uepth 0： ExitkPpijnft Bin_tree Pi*enipd.ei?： abdeef jotKJtJoociTNJC e Leet 竟nmjckjn)oo(nj( 1: Prcordcr TIavcrsal2 - I order1 Triy erscil3 = Pustcrdep traversal4: PDstIreeDept：li,Node nLimtieE,Leaf nLimber 5: Level Depth 0: ExitEPiijTt Binjre

4、e Inoi*dei dlbaef jotKJtJoociTNJC e lect 竟 jockmjot*xit1 s Picordev Tiavereal2 - Iurdier1 Trciyerscil3 = PuStorden traversal4: PDstIieeDepth,Node nLimtieF,Leaf nLimber S: Level Depth0: Exit3Pftint BinTree Postorder: Mcefa jotKJtJoociTNJC e lect 竟 jockmjot*xit1 Picordei* Tawersal2 - larder1 Trciycrsa

5、l3: Pustordei traueFsal4: Pd stive e Depth, No de nun)Jjer,Leaf number 5: Leuel Bepth 0： Exit4BinTree Depth= BinTree Node numbei*=6 BinTree Leaf nuiiiibeF= MMHJOc jrjoc se lect 算kjocpoocxm/jck1 - Picordcr TiauoiEal2 - larder1 Trciyersal3: Fustcidei traversal3、改正后的程序: #include #include#include#define

6、 Max 20结点的最大个数=/typedef struct node char data;struct node *lchild产rchild;BinTNode;/自定义二叉树的结点类型typedef BinTNode *BinTree;定义二叉树/NodeNum 为的指针int NodeNumJeaf;结点数，leaf为叶子数，/NosdeNum是全局变量，应用时要初始化=基于先序遍历算法创建二叉树/=要求输入先序序列，其中加入虚结点呻”以示空指针的位置=BinTree CreatBinTree(void) BinTree T; char ch; if(ch=getchar()=#)ret

7、urn(NULL);读入#，返回空指针else T=(BinTNode *)malloc(sizeof(BinTNode);/生成结点if( T != NULL )/构/构造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); /=LNR 中序遍历void Inorder

8、(BinTree T)if(T) iwJiwJInorder(T-lchild); 中序遍历左子树 printf(%c”,T-data); 访问结点 Inorder(T-rchild); 中序遍历右子树 liijJ=LRN 后序遍历 void Postorder(BinTree T)if(T) /后序遍历左子树/后序遍历右子树访问结点Preorder(T-lchild);Preorder(T-rchild);printf(%c,T-data);iliiJ/=采用后序遍历求二叉树的深度、结点数 及叶子数的递归算法=int TreeDepth(BinTree T)int hl,hr,max;if(

9、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);=利用”先进先出(FIFO)队列，按层次遍历二叉树=void Levelorder(BinTree 丁)/判断内存分配失败int front=0,rear=1;BinTNode *cqMax,*p;定义结点的指针数组cqif( T != NULL )

10、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 DesdroyBinTree(BinTree T )BinTree p = T,r;if(p!

11、=NULL)r = p+;while(r != NULL )free(p);p=r;r=p+;free(p);/=主函数=void main()BinTree root; int i=1,depth;printf(n);printf(Creat Bin_Tree； Input preorder:); /输入完全二叉树的先序序列，/用#代表虚结点，创建二叉树，如 ABD#CE#F#root=CreatBinTree();/从菜单中选择返回根结点do 遍历方式，输入序号。selectprintf(t*n，)；printf(t1: Preorder Traversaln);printf(t2: lo

12、rder Traversaln);printf(t3: Postorder traversaln);printf(t4:PostTreeDepth,NodeijiiJnumber,Leaf numbern); printf(t5: Level Depthn); /按层次遍历之前，先选择4,求出该树的结点数。printf(t0: Exitn);_ AA al* ale ale ate afte aft* ale ! ale ale al afte aft* ale ! ale ale al afte et aft* ale ! ale ale al afteDnntfi t*n);scanf(%

13、d,&i);输入菜单序号(0-5 )switch (i)/先序遍历case 1: printf(Print Bin_tree Preorder: );iwJPreorder(root); break;case 2: printf(Print Bin_Tree Inorder:);liiiJInorder(root); 中序遍历 break; case 3: printf(Print Bin_Tree Postorder: );Postorder(root);后序遍历/求树的break; case 4: depth=TreeDepth(root);BinTree深度及叶子数Leafprintf(BinTree Depth=%d Node number=%d,depth,NodeNum);printf(BinTreenumber=%d,leaf); break; case 5: printf(LevePrint Bin_Tree:);Levelorder(root);按层次遍历break;default