二叉树的基本操作

1、GB8878185555334563BT9125XW创作編号丄创作肴：凤呜大王*二叉树的基本操作#include <iostream.h>typedef struct node 定义结点 char data;struct node *lchild,打child; BinTNode;typedef BinTNode *BinTree; 定义二叉树void CreateBinTree(BinTree &T);先序创建二义树void PreOrder(BinTree T);先序遍历二叉树void InOrder(BinTree T);中序遍历二叉树void PostOrder(B

2、inTree 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 chl,ch2;cout«H欢迎进入二义树测试程序的基本操作H«endl;chl='y'while(chl=yilchl =*¥*)coutvvT建立二叉树 n”；cout«&quo

3、t;2先序遍历n"cout«"3中序遍历n"cout«"4后序遍历n"cout«"5单孩子结点数n"cout«"6双孩子结点数n"cout«"7叶子结点数n”；cout«"8层序遍历n"cout«nX退出 n”；cin»ch2;switch(ch2)case T:cout«"请输入按先序建立二义树的结点序列：n"Create B inTree(T);cout«

4、;endl;break;case 2:coutvv”二义树的先序遍历序列：n”；PreOrder(T);cout«endl;break;case 3:cout«"二叉树的中序遍历序列:n"InOrder(T);break;case 4:coutvv”二叉树的后序遍历序列：iiH;创作編号上GB8878185555334563BT9125XW创作肴：凤呜大王*PostOrder(T);cout«endl;break;case 51cout«H二义树的单孩子结点数：n”;n=onechild(T);cout«n«end

5、l;cout«endl;break;case &:cout«"二义树的双孩子结点数：n"n=twochild(T);cout«n«endl;cout«endl;break;case 7:cout«H二义树的叶子结点数：n"n=leafs(T);cout«endl;break;case 8:cout«".rX树的层序遍历序列：n”;translevel(T);cout«endl;break;case x*:case X:chl='x；break;voi

6、d CreateBinTree(BinTree &T)char ch;cin»ch;if(ch='0,) T=NULL;elseT=(BinTNode *)new BinTNode;lL>data=ch;CreateBinTree(T->lchild );CreateBinTree(T->rchild );void InOrder(BinTree T)if(T)InOrder(T->lchild ); cout«T->data;InOrder(T->rchild );)void PostOrder(BinTree T)if

7、(T)PostOrder(T->lchild );PostOrder(T->rchild );cout«T->data;GB8878185555334563盯9125XW创作褊号上创作者：凤呜大王*void PreOrder( B inTree T)if(T)cout«T->data;PreOrder(T->lchild );PreOrder(T->rchild );)层序遍历二义树釆用一个队列q,先将二义树的根结点入队列，然后退队列，输出 该结点，若它有左子树，便将左子树根结点入队列，若它有右子树， 便将右子树根结点入队列，如此直到队列

8、空为止。因为队列的特点是先进先出，从而达到按层序遍历的I的。#define MAXLEN 100void translevel(BinTree b)struct nodeBinTree vecMAXLEN;int f, r;q； 定义队列q，f表示队头指针，r队尾指针q.f=O; 置队列为空队列q.r=O;if(b!=NULL) cout« b->data«H H;q.vecq.r=b;结点指针进入队列q.r=q.r+l;队尾指针后移b=q.vecq.f; 队头出队列q.f=q.f+l;if(b->lchild!=NULL) 输出左孩子，并入队列cout

9、1; b->lchild->data«H ”；q.vecq.r=b->lchild;q.r=q.r+l;if(b->rchild!=NULL)输出右孩子，并入队列cout« b->rchild->data«H ”；q.vecq.r=b->rchild;q.r=q.r+l;) int onechild(BinTree T)/求度为1的结点的个数if(T=NULL) return 0;elseif(T->lchild=NULL&&T->rchild!=NULLIIT->lchild!=NULL

10、 && T->rchild=NULL)return (onechild(T->Ichild)+onechild(T->rchild)+1);elsereturn (onechild(T->lchiId)+onechild(T->rchild);int leafs(BinTree T)int numl,num2;if(T=NULL) return 0;else if(T->lchild=NULL &&T->rchild =NULL) return 1;elsenuml=leafs(T->lchild);num2=leafs(T->rchild );return numl+num2;)GB8878185555334563盯9125XW创作编号丄创作者：凤呜大王*int twochild(BinTree T)int num0=0,num I jium2;if(T=NULL) return 0;else if(T->lchild!