二叉树的基本操作.doc

《二叉树的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、//二叉树的基本操作#includetypedefstructnode//定义结点{chardata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;//定义二叉树voidCreateBinTree(BinTree&T);//先序创建二叉树voidPreOrder(BinTreeT);//先序遍历二叉树voidInOrder(BinTreeT);//中序遍历二叉树voidPostOrder(BinTreeT);//后序遍历二叉树int

2、onechild(BinTreeT);//求度为1的结点的个数intleafs(BinTreeT);//求叶子结点的个数inttwochild(BinTreeT);//度为2的结点的个数voidtranslevel(BinTreeb);//层序遍历二叉树voidmain(){intn;BinTreeT;charch1,ch2;cout<<"欢迎进入二叉树测试程序的基本操作"<

3、

4、ch1=

5、='Y'){cout<<"1---------建立二叉树";cout<<"2---------先序遍历";cout<<"3---------中序遍历";cout<<"4---------后序遍历";cout<<"5---------单孩子结点数";cout<<"6---------双孩子结点数";cout<<"7---------叶子结点数";cout<<"8---------层序遍历";cout<<"X---------退出";cin>>ch2;switch(ch2){case'1':cou

6、t<<"请输入按先序建立二叉树的结点序列：";CreateBinTree(T);cout<

7、=onechild(T);cout<

8、ch1='x';break;}}}voidCreateBinTree(BinTree&T){charch;cin>>ch;if(ch=='0')T=NULL;else{T=(BinTNode*)newBinTNode;T->data=ch;CreateBinTree(T->lchild);CreateBinTree(T->rchild);}}voidInOrder(BinTreeT){if(T){InOrder(T->lchild);cout<data;InOrder(T->rchild);}}voidPostOrder

9、(BinTreeT){if(T){PostOrder(T->lchild);PostOrder(T->rchild);cout<data;}}voidPreOrder(BinTreeT){if(T){cout<data;PreOrder(T->lchild);PreOrder(T->rchild);}}//层序遍历二叉树//采用一个队列q，先将二叉树的根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。//因为队列的特点是先进先出，

10、从而达到按层序遍历的目的。#defineMAXLEN100voidtranslevel(BinTreeb){structnode{BinTreevec[MAXLEN];intf,r;}q;//定义队列q，f表示队头指针，r队尾指针q.f=0;//置队列为空队列q