二叉树的操作

1、二叉树操作实验日志实验题目：二叉树操作实验目的：掌握二叉树的定义、性质及存储方式,各种遍历算法.实验要求：采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作.实验主要步骤：1、分析、理解程序程序的功能是采用二叉树链表存储结构,完成二叉树的建立,先序、中序和 后序以及按层次遍历的操作.如输入二叉树 ABD#CE#F# ,链表示意图如下：2、添加中序和后序遍历算法/=LNR中序遍历=void Inord er(BinTree T)(if(T)Inorder(T->lchild);printf("%c,T->data)

2、;Inorder(T->rchild);)/=LRN后序遍历=void Postorder(BinTree T) (if(T)Postorder(T->lchild);Postorder(T->rchild);printf("%c,T->data);)3、调试程序,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点空指针,如ABD#CE#F# ,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数.四、源程序代码#include"stdio.h" #include"string.h"#inclu

3、de"stdlib.h"#define Max 20/结点的最大个数typed ef struct nod echar data;struct node *l chil d,*rchil d;BinTNode;typed ef BinTNode *BinTree; int NodeNum,l eaf;/自定义二叉树的结点类型/定义二叉树的指针/NodeNum为结点数,leaf为叶子数/=基于先序遍历算法创立二叉树要求输入先序序列,其中参加虚结点"#"以示空指针的位置BinTree CreatBinTree(void) BinTree T; char ch

4、;if(ch=getchar()='#') return(NULL);elseT=(BinTNode *)mall T->data=ch;/读入#,返回空指针oc(sizeof(BinTNode);/生成结点/构造左子树/构造右子树T->lchil d=CreatBinTree();T->rchil d=CreatBinTree(); return(T);)/NLR先序遍历void Preorder(BinTree T) (if(T) printf("%c",T->data);/ 访问结点Preorder(T->l chil d

5、);/ 先序遍历左子树Preorder(T->rchil d);/ 先序遍历右子树=LNR中序遍历=void Inorder(BinTree T) if(T)Inorder(T->l chil d);printf("%c",T->data);Inorder(T->rchil d); /=LRN 后序遍历= void Postorder(BinTree T) if(T)Postorder(T->l chil d);Postorder(T->rchil d);printf("%c",T->data); /=采用后序遍

6、历求二叉树的深度、结点数及叶子数的递归算法int TreeDepth(BinTree T) int hl,hr,max;if(T)hl=TreeDepth(T->l chil d);/ 求左深度hr=TreeDepth(T->rchil d);/ 求右深度max=hl>hr? hl:hr;/取左右深度的最大值NodeNum=NodeNum+1;/ 求结点数if(hl=0&&hr=0) l eaf=leaf+1;/ 假设左右深度为0 ,即为叶子.return(max+1);else return(0);/= 利用"先进先生"(FIFO)队列,

7、按层次遍历二叉树=void Level order(BinTree T) /定义结点的指针数组/根入队cqint front=0,rear=1;BinTNode *cqMax,*p;cq1=T;whil e(front!=rear)cqrear=p->rchild;front=(front+1)%NodeNum; p=cqfront;printf("%c,p->data);if(p->l chil d!=NULL) rear=(rear+1)%NodeNum;cqrear=p->l chil d; if(p->rchil d!=NULL) rear=(r

8、ear+1)%NodeNum; /右子树入队/由队/由队,输由结点的值/左子树入队/主函数void main()BinTree root;int i,depth;printf("n");printf("Creat Bin_TreeInput preorder:"); /输入完全二叉树的先序序列,/root=CreatBinTree();do printf("t* selprintf("t1: Preorder Traversal'n");用#代表虚结点,如 ABD#CE#F#/创立二叉树,返回根结点/从菜单中选择遍历

9、方式,输入序号.ect *n"printf("t2: Iorder Traversal'n");printf("t3: Postorder traversal'n");printf("t4: PostTreeDepth,Node number,Leaf number'n");printf("t5: Level Depth'n"); /按层次遍历之前,先选择 4,求生该树的结点数.printf("t0: Exit'n");printf("

10、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

11、4: depth=TreeDepth(root);printf("BinTree Depth=%d number=%d",d epth,NodeNum);/后序遍历/求树的深度及叶子数BinTree Nodeprintf(" BinTree Leaf number=%d",l break;case 5: printf("LevePrint Bin_Tree:");eaf);Level order(root);break;default: exit(1);printf("n"); whil e(i!=0);实验结果：

12、(1)输入完全二叉树的先序序列/按层次遍历ABD#CE#F# ,程序运行结果如下:iteat Bin_ri*ee； Enput ppeoL'der=ftEjbnBttC£ltKF*ilH * XU H H廿 H y 04 1 a 4-WVMYlf1： Prepeder Trauersal 2* I order Ir«versAl 31 Postarder* traversal1- Pos c I re e De p t h , Mo de numlisr>ljeaf nuiulier S： Level Depth fl: Exit(2)先序序列：itrint

13、Bin_teee PFeorder1 ABDCEF selectX,X 乂 乂 N M1_:Tvauevsal2: larder Irv&rsal3s Postorder traversal4: PostlreeDepthpHode numberLeaf nunber 5： Leuel Depth0: Exit(3)中序序列Bin_Tr>efr I norden: DSRECF与 _® jjt* 17 i_1 z ifedrdfet1 T PAUfti*£Al2： 1 order TfauersaL3 : Postoi'dei' ti*av&a

14、mp;i*sa 14： Pos：tTr&eDeptJi»Node nunberL&aF numberS> Level Depthfl: ExitJtM.MM Jt-Jt X,JtltWXM*(4)后序序列T»int Bin-TFee Po&toirlei' = DHFFCfi1: 1t*匕ord世r ! rauet'sal2: I order rreiversal3： Posttfriier traversal4： PostTr&eDepth,Hade number>Leaf number5 L&vel D

15、epth.：Exit(5)所有叶子及结点总数*WM-WUM H 1*W-V X W 射 W »-> .tJinTree Depth=3 BinTree Node nunber=6 BinTree Leif nunber=3k,- HL M V M PT % k I IT I. Bi Pt M K 9K VI M JI XXX1: Ppeordep iFauersal2： lordev Ivauersal3 - Postot'det' ti*auei*sal4: PostTveeDepth,Node nunher,LeaF ntimber5： Level Depth 0 z Exit(6)按层次遍历序列LeuePi*int Bin_Ti*ee: ftBCDEF w" i h y k w8 匕 hr n 入1 人人 A u ihtxiiII g_ k1 ： Pi*eor<l住产 I r-AV&t*sa 12 - I d fde r rraveisal3 ： Postorde-r trAversl4 ： PotTr&oDepthMQdc: F>unht:r«Leaf