二叉树的基本操作技巧.doc
cout«"请选择"<<e ndl;/二叉树的基本操作/定义结点#i nclude <iostream.h> typedef struct node char data;struct node *lchild, *rchild; Bi nTNode;typedef Bin TNode *Bi nTree; / void CreateB in Tree(Bi nTree & T);void PreOrder(Bi nTree T);void In Order(B in Tree T);void PostOrder(BinTree T);int on echild(Bi nTree T);int leafs(B in Tree T);int twochild(B in Tree T);void tran slevel(B in Treeb);定义二叉树/先序创建二叉树/先序遍历二叉树/中序遍历二叉树/后序遍历二叉树/求度为1的结点的个数/求叶子结点的个数/度为2的结点的个数/层序遍历二叉树void mai n()int n;Bin Tree T;char ch1,ch2;coutvv"欢迎进入二叉树测试程序的基本操作"<<endl;ch仁'y'while(ch1='y'|ch1='Y')cout<<"1 建立二叉树 n"cout<<"2 先序遍历 n"cout<<"3 中序遍历 n"cout<<"4 后序遍历 n"cout<<"5 单孩子结点数n"cout<<"6 双孩子结点数n"cout<<"7 叶子结点数n"cout<<"8 层序遍历 n"cout«"X 退出 n"cin> >ch2;switch(ch2)case '1':coutvv"请输入按先序建立二叉树的结点序列：n"CreateBi nTree(T);cout«e ndl;break;cout«"二叉树的先序遍历序列:n"case 2:PreOrder(T);cout«e ndl;break;case 3:coutvv"二叉树的中序遍历序列:In Order(T);cout«e ndl;break;case '4':coutvv"二叉树的后序遍历序列:PostOrder(T);coutvve ndl;break;case '5':coutvv"二叉树的单孩子结点数：n=on echild(T);cout< vnvven dl;coutvve ndl;break;n"n"n"case '6':n=twochild(T);cout< <n<<en dl;cout«e ndl;break;case 7':cout«"二叉树的叶子结点数：n"n=leafs(T);cout< <n<<en dl;cout«e ndl;break;case 8:cout«"二叉树的层序遍历序列：n"tran slevel(T);cout«e ndl;break;case 'x':case 'X':ch1='x'break;void CreateBi nTree(Bi nTree &T)char ch;cin> >ch;if(ch='0') T=NULL;elseT=(Bi nTNode *)new Bi nTNode;T->data=ch;CreateBi nTree(T->lchild );CreateBi nTree(T->rchild ); void In Order(B in Tree T)if(T)In Order(T->lchild );cout<<T->data;InOrder(T->rchild);void PostOrder(B in Tree T)if(T)PostOrder(T->lchild );PostOrder(T->rchild ); cout<<T->data; void PreOrder(B in Tree T)if(T)cout<<T->data;PreOrder(T->lchild );PreOrder(T->rchild );q.r=q.r+1;/队尾指针后移/层序遍历二叉树/采用一个队列q，先将二叉树的根结点入队列，然后退队列，输出该结 点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子 树根结点入队列，如此直到队列空为止。/因为队列的特点是先进先出，从而达到按层序遍历的目的。#defi ne MAXLEN 100void tran slevel(B in Treeb)struct nodeBin Tree vecMAXLEN;int f, r;q; /定义队列q，f表示队头指针，r队尾指针q.f=0;/置队列为空队列q.r=0;if(b!=NULL) cout<< b->data<<""while(q.fvq.r)/ 队列不为空b=q.vecq.f;/队头出队列q.f=q.f+1;if(b->lchild!=NULL)/输出左孩子，并入队列cout« b->lchild->data<<""q.vecq.r=b->lchild;q.r=q.r+1;if(b->rchild!=NULL)/输出右孩子，并入队列cout« b->rchild->data<<""q.vecq.r=b->rchild;q.r=q.r+1;inton echild(B in Tree T)求度为1的结点的个数if(T=NULL) retur n 0;&&elseif(T->lchild=NULLT->rchild!=NULL|T->lchild!=NULL && T->rchild=NULL) retur n (on echild(T->lchild)+on echild(T->rchild)+1);elsereturn (on echild(T->lchild)+on echild(T->rchild); int leafs(Bi nTree T)int nu m1, nu m2;if(T=NULL) retur n 0;else if(T->lchild=NULL &&T->rchild =NULL) retur n 1;elsenum1=leafs(T->lchild);nu m2=leafs(T->rchild );retur n nu m1+ num2;int twochild(Bi nTree T)int numO=O,nu ml, num2;if(T=NULL) retur n 0;else if(T->lchild!=NULL && T->rchild!=NULL) num 0=1;nu m仁twochild(T->lchild);nu m2=twochild(T->rchild);retur n num0+nu m1+ num2;
