二叉树的基本操作技巧

1、/二叉树的基本操作 #i nclude viostream.h>typ edef struct node/定义结点 char data;struct node *lchild, *rchild; Bi nTNode;typ edef Bin TNode *Bi nTree; /定义二叉树void CreateB in Tree(Bi nTree & T);/先序创建二叉树void P reOrder(B in Tree T);/先序遍历二叉树void In Order(B in Tree T);/中序遍历二叉树void P ostOrder(Bi nTree T);/后序遍历二叉

2、树int on echild(Bi nTree T);/求度为1的结点的个数int leafs(B in Tree T);/求叶子结点的个数int twochild(B in Tree T);/度为2的结点的个数/层序遍历二叉树void tran slevel(B in Treeb);void mai n()int n;Bin Tree T;char ch1,ch2;coutvv"欢迎进入二叉树测试程序的基本操作"<<endl;cout<<"请选择"<<e ndl;ch仁y； while(ch1='y'

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

4、>ch2;switch(ch2)case '1':coutvv"请输入按先序建立二叉树的结点序列：n"CreateBi nTree(T);coutvve ndl;break;case 2:coutvv"二叉树的先序遍历序列:n"P reOrder(T);coutvve ndl;break;case 3:coutvv"二叉树的中序遍历序列:n"In Order(T);coutvve ndl;break;case '4':coutvv"二叉树的后序遍历序列:n"P ostOrder

5、(T);coutvve ndl;break;case '5':coutvv"二叉树的单孩子结点数:n"n=on echild(T);coutv vnvven dl;coutvve ndl;break;case '6':coutvv"二叉树的双孩子结点数：n"n=twochild(T);coutv vnwen dl;coutvve ndl;break;case 7':coutvv"二叉树的叶子结点数：n"n=leafs(T);cout< vnwen dl;coutvve ndl;break;

6、case 8:coutvv"二叉树的层序遍历序列：n"tran slevel(T);coutvve ndl;break;case 'x': case 'X':ch1='x'break;void CreateBi nTree(Bi nTree &T)char ch;cin> >ch;if(ch='O') T=NULL;elseT=(Bi nTNode *)new Bin TNode;T->data=ch;CreateBi nTree(T->lchild );CreateBi nTr

7、ee(T->rchild );void In Order(B in Tree T)if(T)In Order(T->lchild );cout<<T->data;In Order(T->rchild );void P ostOrder(B in Tree T)if(T)P ostOrder(T->lchild );P ostOrder(T->rchild );cout<<T->data;void P reOrder(B in Tree T)if(T)cout<<T->data;P reOrder(T->l

8、child );P reOrder(T->rchild );/层序遍历二叉树/采用一个队列q，先将二叉树的根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。/因为队列的特点是先进先出，从而达到按层序遍历的目的。#defi ne MAXLEN 100void tran slevel(B in Treeb)struct nodeBin Tree vecMAXLEN;int f, r;q;/定义队列q，f表示队头指针，r队尾指针q.vecq.r=b;/结点指针进入队列q.f=0;/置队列为空队列Hq.r=0;i

9、f(b!=NULL) cout<< b->data<<"q.r=q.r+1;/队尾指针后移while(q.fvq.r)/队列不为空b=q.vecq.f;/队头出队列q.f=q.f+1;if(b->lchild!=NULL)/输出左孩子，并入队列H.coutvv b->lchild->data<<"q.vecq.r=b->lchild;q.r=q.r+1;if(b->rchild!=NULL)/输出右孩子，并入队列H.coutvv b->rchild->data<<" q

10、.vecq.r=b->rchild;q.r=q.r+1;if(T=NULL) retur n 0;elseif(T->lchild=NULL&&T->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, num2;if(T=NULL) retur n 0;else if(T->lchild=NULL &&T->rchild =NULL) return 1;elsenu m1=leafs(T->lchild );nu m2=leafs(T->rchild );retu rn nu m1+ num2;int twochild(B in Tree T)int numO=O,nu m1, num2;