二叉树的基本 操作参考模板

1、/二叉树的基本操作#include <iostream.h> 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 on

2、echild(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=

3、'y'|ch1='Y') cout<<"1-建立二叉树 n" cout<<"2-先序遍历n" cout<<"3-中序遍历n"1 / 8 cout<<"4-后序遍历n" cout<<"5-单孩子结点数n" cout<<"6-双孩子结点数n" cout<<"7-叶子结点数n" cout<<"8-层序遍历n" cou

4、t<<"X-退出n" cin>>ch2; switch(ch2) case '1': cout<<"请输入按先序建立二叉树的结点序列：n"CreateBinTree(T);cout<<endl;break; case '2': cout<<"二叉树的先序遍历序列：n" PreOrder(T); cout<<endl; break; case '3': cout<<"二叉树的中序遍历序列：n&qu

5、ot; InOrder(T); cout<<endl; break; case '4': cout<<"二叉树的后序遍历序列：n" PostOrder(T); cout<<endl; break;case '5': cout<<"二叉树的单孩子结点数：n" n=onechild(T); cout<<n<<endl; cout<<endl; break;case '6': cout<<"二叉树的双孩子结点

6、数：n" n=twochild(T); cout<<n<<endl; cout<<endl; break;case '7': cout<<"二叉树的叶子结点数：n" n=leafs(T); cout<<n<<endl; cout<<endl; break; case '8': cout<<"二叉树的层序遍历序列：n" translevel(T); cout<<endl; break;case 'x&

7、#39;:case 'X': ch1='x' break; void CreateBinTree(BinTree &T) char ch; cin>>ch; 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 );cout<&

8、lt;T->data;InOrder(T->rchild ); void PostOrder(BinTree T)if(T)PostOrder(T->lchild );PostOrder(T->rchild );cout<<T->data; void PreOrder(BinTree T)if(T)cout<<T->data;PreOrder(T->lchild );PreOrder(T->rchild ); /层序遍历二叉树/采用一个队列q，先将二叉树的根 结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结

9、点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。/因为队列的特点是先进先出，从而达到按层序遍历的目的。 #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) cout<< b->data<<" "q.vecq.r=b; /结点指针进入队列q.r=q.r+1; /队尾指针后移 while(q.f&

10、lt;q.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; int onech

11、ild(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