二叉树的基本 操作

《二叉树的基本 操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、

4、ch1=='Y'){cout<<"1---------建立二叉树";cout

5、<<"2---------先序遍历";cout<<"3---------中序遍历";cout<<"4---------后序遍历";cout<<"5---------单孩子结点数";cout<<"6---------双孩子结点数";cout<<"7---------叶子结点数";cout<<"8---------层序遍历";cout<<"X---------退出";cin>>ch2;switch(ch2){case'1':cout<<"请输入按先序建立二叉树的结点序列：";CreateBinTree(T);cout<

6、reak;case'2':cout<<"二叉树的先序遍历序列：";PreOrder(T);cout<

7、";n=twochild(T);cout<>ch;if(ch=='0')T=NULL;else{T=(Bin

8、TNode*)newBinTNode;T->data=ch;CreateBinTree(T->lchild);CreateBinTree(T->rchild);}}voidInOrder(BinTreeT){if(T){InOrder(T->lchild);cout<data;InOrder(T->rchild);}}voidPostOrder(BinTreeT){if(T){PostOrder(T->lchild);PostOrder(T->rchild);cout<data;}}voidPreOrder(BinTreeT){if(T){cout

9、<data;PreOrder(T->lchild);PreOrder(T->rchild);}}//层序遍历二叉树//采用一个队列q，先将二叉树的根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。//因为队列的特点是先进先出，从而达到按层序遍历的目的。#defineMAXLEN100voidtranslevel(BinTreeb){structnode{BinTreevec[MAXLEN];intf,r;}q;//定义队列q，f表示队头指针，r队尾指针q.f=0;//置队列

10、为空队列q