二叉树操作设计和实现

实验2实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序。2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。实验代码#includestdio.h#includestdlib.h#includestring.h#defineMax20//结点的最大个数typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定义二叉树的结点类型typedefBinTNode*BinTree;//定义二叉树的指针intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点#以示空指针的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL);//读入#，返回空指针else{T=(BinTNode*)malloc(sizeof(BinTNode));//生成结点T-data=ch;T-lchild=CreatBinTree();//构造左子树T-rchild=CreatBinTree();//构造右子树return(T);}}//========NLR先序遍历=============voidPreorder(BinTreeT){if(T){printf(%c,T-data);//访问结点Preorder(T-lchild);//先序遍历左子树Preorder(T-rchild);//先序遍历右子树}}//========LNR中序遍历===============voidInorder(BinTreeT){if(T){Inorder(T-lchild);//中序遍历左子树printf(%c,T-data);//访问结点Inorder(T-rchild);//中序遍历右子树}}//==========LRN后序遍历============voidPostorder(BinTreeT){if(T){Postorder(T-lchild);//后序遍历左子树Postorder(T-rchild);//后序遍历右子树printf(%c,T-data);//访问结点}}//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========intTreeDepth(BinTreeT){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);}elsereturn(0);}//====利用先进先出（FIFO）队列，按层次遍历二叉树==========voidLevelorder(BinTreeT){intfront=0,rear=1;BinTNode*cq[Max],*p;//定义结点的指针数组cqcq[1]=T;//根入队while(front!=rear){front=(front+1)%NodeNum;p=cq[front];//出队printf(%c,p-data);//出队，输出结点的值if(p-lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p-lchild;//左子树入队}if(p-rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p-rchild;//右子树入队}}}//====数叶子节点个数==========intcountleaf(BinTreeT){inthl,hr;if(T){hl=countleaf(T-lchild);hr=countleaf(T-rchild);if(hl==0&&hr==0)//若左右深度为0，即为叶子。return(1);elsereturnhl+hr;}elsereturn0;}//==========主函数=================voidmain(){BinTreeroot;chari;intdepth;printf(\n);printf(CreatBin_Tree；Inputpreorder:);//输入完全二叉树的先序序列，//用#代表虚结点，如ABD###CE##F##root=CreatBinTree();//创建二叉树，返回根结点do{//从菜单中选择遍历方式，输入序号。printf(\t**********select************\n);printf(\t1:PreorderTraversal\n);printf(\t2:IorderTraversal\n);printf(\t3:Postordertraversal\n);printf(\t4:PostTreeDepth,Nodenumber,Leafnumber\n);printf(\t5:LevelDepth\n);//按层次遍历之前，先选择4，求出该树的结点数。printf(\t0:Exit\n);printf(\t*******************************\n);fflush(stdin);scanf(%c,&i);//输入菜单序号（0-5）switch(i-'0'){case1:printf(PrintBin_treePreorder:);Preorder(root);//先序遍历break;case2:printf(PrintBin_TreeInorder:);Inorder(root);//中序遍历break;case3:printf(PrintBin_TreePostorder:);Postorder(root);//后序遍历break;case4:depth=TreeDepth(root);//求树的深度及叶子数printf(BinTreeDepth=%dBinTreeNodenumber=%d,depth,NodeNum);printf(BinTreeLeafnumber=%d,countleaf(root));break;case5:printf(LevePrintBin_Tree:);Levelorder(root);//按层次遍历break;default:exit(1);}printf(\n);}while(i!=0);}实验结果：CreatBin_Tree；Inputpreorder:ABD###CE##F##**********select************1:PreorderTraversal2:IorderTraversal3:Postordertraversal4:PostTreeDepth,Nodenumber,Leafnumber5:LevelDepth0:Exit*******************************1PrintBin_treePreorder:ABDCEF2PrintBin_TreeInorder:DBAECF3PrintBin_TreePostorder:DBEFCA4BinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnumber=35LevePrintBin_Tree:ABCDEF0Pressanykeytocontinue二叉树示意图ABFEDC