二叉树的基本操作.doc

1、页眉内容/二叉树的基本操作#include typedef struct node/ 定义结点char data;struct node *lchild, *rchild;typedef BinTNode *BinTree; / 定义二叉树void CreateBinTree(BinTree &T);void PreOrder(BinTree T);void InOrder(BinTree T);void PostOrder(BinTree T);int onechild(BinTree T);int leafs(BinTree T);int twochild(BinTree T);void

2、translevel(BinTreeb);void main()/先序创建二叉树/先序遍历二叉树/ 中序遍历二叉树/ 后序遍历二叉树/求度为 1 的结点的个数/求叶子结点的个数/ 度为 2 的结点的个数/层序遍历二叉树int n;BinTree T;char ch1,ch2;cout欢迎进入二叉树测试程序的基本操作endl;cout- 请选择 -endl;ch1=y;while(ch1=y|ch1=Y)cout1- 建立二叉树n;cout2-先序遍历 n;cout3-中序遍历 n;cout4-后序遍历 n;页眉内容cout5- 单孩子结点数 n;cout6- 双孩子结点数 n;cout7- 叶

3、子结点数 n;cout8- 层序遍历 n;coutch2;switch(ch2)case 1:cout请输入按先序建立二叉树的结点序列：n;CreateBinTree(T);coutendl;break;case 2:cout二叉树的先序遍历序列：n;PreOrder(T);coutendl;break;case 3:cout二叉树的中序遍历序列：n;InOrder(T);coutendl;break;case 4:cout二叉树的后序遍历序列：n;PostOrder(T);coutendl;break;case 5:页眉内容cout二叉树的单孩子结点数：n;n=onechild(T);cou

4、tnendl;coutendl;break;case 6:cout二叉树的双孩子结点数：n;n=twochild(T);coutnendl;coutendl;break;case 7:cout二叉树的叶子结点数：n;n=leafs(T);coutnendl;coutendl;break;case 8:cout二叉树的层序遍历序列：n;translevel(T);coutch;if(ch=0)T=NULL;elseT=(BinTNode *)new BinTNode;T-data=ch;CreateBinTree(T-lchild );CreateBinTree(T-rchild );void

5、InOrder(BinTree T)if(T)InOrder(T-lchild );coutdata;InOrder(T-rchild );void PostOrder(BinTree T)if(T)PostOrder(T-lchild );PostOrder(T-rchild );coutdata;页眉内容void PreOrder(BinTree T)if(T)coutdata;PreOrder(T-lchild );PreOrder(T-rchild );/层序遍历二叉树/采用一个队列q，先将二叉树的根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树

6、，便将右子树根结点入队列，如此直到队列空为止。/因为队列的特点是先进先出，从而达到按层序遍历的目的。#define MAXLEN 100void translevel(BinTreeb)struct nodeBinTreevecMAXLEN;int f, r;q; /定义队列 q， f 表示队头指针， r 队尾指针 q.f=0; /置队列为空队列q.r=0;if(b!=NULL) coutdata;q.vecq.r=b;/结点指针进入队列q.r=q.r+1;/队尾指针后移while(q.flchild!=NULL)/输出左孩子，并入队列coutlchild-datalchild;q.r=q.r

7、+1;if(b-rchild!=NULL)/输出右孩子，并入队列coutrchild-datarchild;q.r=q.r+1;int onechild(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;页眉内容elsenum1=leafs(T-lchild );num2=leafs(T-rchild );return num1+num2;int twochild(BinTree T)int num0=0,num1,num2;if(T=NULL) return