二叉树的基本 操作.doc

/二叉树的基本操作#include typedef struct node /定义结点 char data; struct node *lchild, *rchild; BinTNode; typedef BinTNode *BinTree; /定义二叉树 void CreateBinTree(BinTree &T); /先序创建二叉树void PreOrder(BinTree T); /先序遍历二叉树void InOrder(BinTree T); /中序遍历二叉树void PostOrder(BinTree T); /后序遍历二叉树int onechild(BinTree T); /求度为1的结点的个数int leafs(BinTree T); /求叶子结点的个数int twochild(BinTree T); /度为2的结点的个数void translevel(BinTree b); /层序遍历二叉树 void main() int n; BinTree T; char ch1,ch2; cout欢迎进入二叉树测试程序的基本操作endl; cout-请选择-endl; ch1=y; while(ch1=y|ch1=Y) cout1-建立二叉树 n; cout2-先序遍历n; cout3-中序遍历n; cout4-后序遍历n; cout5-单孩子结点数n; cout6-双孩子结点数n; cout7-叶子结点数n; cout8-层序遍历n; coutch2; switch(ch2) case 1: cout请输入按先序建立二叉树的结点序列：n;CreateBinTree(T);coutendl;break; case 2: cout二叉树的先序遍历序列：n; PreOrder(T); coutendl; break; case 3: cout二叉树的中序遍历序列：n; InOrder(T); coutendl; break; case 4: cout二叉树的后序遍历序列：n; PostOrder(T); coutendl; break;case 5: cout二叉树的单孩子结点数：n; n=onechild(T); coutnendl; coutendl; break;case 6: cout二叉树的双孩子结点数：n; n=twochild(T); coutnendl; coutendl; break;case 7: cout二叉树的叶子结点数：n; n=leafs(T); coutnendl; coutendl; break; case 8: cout二叉树的层序遍历序列：n; translevel(T); coutch; if(ch=0) T=NULL; else T=(BinTNode *)new BinTNode; T-data=ch; CreateBinTree(T-lchild ); CreateBinTree(T-rchild ); void InOrder(BinTree T)if(T)InOrder(T-lchild );coutdata;InOrder(T-rchild ); void PostOrder(BinTree T)if(T)PostOrder(T-lchild );PostOrder(T-rchild );coutdata; void PreOrder(BinTree T)if(T)coutdata;PreOrder(T-lchild );PreOrder(T-rchild ); /层序遍历二叉树/采用一个队列q，先将二叉树的根 结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。/因为队列的特点是先进先出，从而达到按层序遍历的目的。 #define MAXLEN 100void translevel(BinTree b) struct node BinTree vecMAXLEN; int f, r;q; /定义队列q， f 表示队头指针，r队尾指针q.f=0; /置队列为空队列q.r=0; if(b!=NULL) coutdata ;q.vecq.r=b; /结点指针进入队列q.r=q.r+1; /队尾指针后移 while(q.flchild!=NULL) /输出左孩子，并入队列 coutlchild-datalchild; q.r=q.r+1;if(b-rchild!=NULL) /输出右孩子，并入队列 coutrchild-datarchild; q.r=q.r+1; int onechild(BinTree T)/求度为1的结点的个数if(T=NULL) return 0;else if(T-lchild =NULL & T-rchild!=NULL|T-lchild!=NULL & T-rchild=NULL) return (onechild(T-lchild)+onechild(T-rchild)+1);elsereturn (onechild(T-lchild)+onechild(T-rchild);int leafs(BinTree T)int num1,num2;if(T=NULL) return 0;else if(T-lchild=NULL &T-rchild =NULL) return 1;else num1=leafs(T-lchild );num2=leafs(T-rchild );return num1+num2;int twochild(BinTree T)int num0=0,num1,num2;if(T=NULL) retur