二叉树运算菜单实验报告

一：问题描述：

功能要求(1-3必做，其他选做）,或Huffman编码 1. 创建

2. 遍历（先序、中序、后序、层序） 3. 计算（结点数、叶子数、高度、宽度）

4. 查找（找结点、找双亲、找孩子、找兄弟，找祖先） 5. 判断（二叉排序树、平衡二叉树、完全二叉树） 6. 处理（左右子树互换，销毁、删子树、插子树、复制） 二：算法描述：

主函数用switch函数创建菜单，菜单下使用各个子函数完成各项功能。我使用的二叉树定义是链式定义，包括左孩子，右孩子，数据。创建用的是扩展二叉树的先序序列以保证唯一性。

三：数据结构的描述：

typedef struct BiTNode{ char data;

struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

如上所示。 四：算法时空分析：

时间复杂度较为合理（因为用的是书上的算法。）；空间复杂度一般，没编；几个函数就二百四十行了。

五：实验收获：

对二叉树的定义和使用有了更加清晰的认识，再一次的加强了编程能力，锻炼了耐心，发现了一个小知识，就是fflush(stdin)函数可以清空缓存，很有用。 六：源程序：

#include #include #define BiTree_Size 20

typedef struct BiTNode{//定义了二叉树结构体。 char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

void Creat(BiTree &t){//创建，#表示空。 char e; fflush(stdin); scanf(\"%c\ if(e=='#') t=NULL; else{ t=(BiTNode*)malloc(sizeof(BiTNode)); t->data=e; Creat(t->lchild); Creat(t->rchild); } }

void Pre(BiTree &t){//前序遍历。 if(!t) return; else{ printf(\"%c \ Pre(t->lchild); Pre(t->rchild); } }

void Mid(BiTree &t){//中序遍历。 if(!t)

return; else{ Mid(t->lchild); printf(\"%c \ Mid(t->rchild); } }

void Post(BiTree &t){//后续遍历。 if(!t) return; else{ Post(t->lchild); Post(t->rchild); printf(\"%c \ } }

int Count(BiTree &t,int i){//求节点数。 if(!t) return i; else{ i++; i=Count(t->lchild,i); i=Count(t->rchild,i); } return i; }

int Yezi(BiTree &t,int i){//求叶子树，利用先序遍历。 if(!t) return i; else{ if(t->lchild==NULL&&t->rchild==NULL) i++; i=Yezi(t->lchild,i); i=Yezi(t->rchild,i); } return i; }

void Kuan(BiTree &t,int a[],int i){//二叉树求宽度，a存放的下标表示层，内容表示宽度。 if(!t)

return; else{ a[i]++; // printf(\"%d\\n\ Kuan(t->lchild,a,i+1); Kuan(t->rchild,a,i+1); } return; }

void Destroy(BiTree &t){//销毁二叉树。 if(!t) return; else{ Destroy(t->lchild); Destroy(t->rchild); free(t); t=NULL; } }

void Copy(BiTree &t1,BiTree &t2){//复制二叉树。 if(!t1) return; else{

t2=(BiTNode*)malloc(sizeof(BiTNode)); t2->data=t1->data; Copy(t1->lchild,t2->lchild); Copy(t1->rchild,t2->rchild); } }

void main(){ BiTree T[BiTree_Size]={NULL}; int a[15]={0},menue,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,max=0,i; while(1){ printf(\"输入o表示退出\\n\"); printf(\"输入1表示创建二叉树\\n\"); printf(\"输入2表示先序二叉树\\n\"); printf(\"输入3表示中序二叉树\\n\"); printf(\"输入4表示后序二叉树\\n\"); printf(\"输入5表示求节点数\\n\"); printf(\"输入6表示求叶子树\\n\"); printf(\"输入7表示求宽度\\n\");

printf(\"输入8表示求高度\\n\"); printf(\"输入9表示销毁二叉树\\n\"); printf(\"输入10表示复制二叉树\\n\"); printf(\"Please choose:\"); scanf(\"%d\ switch(menue){ case 0:return; case 1: printf(\"从0~%d选择一个作为二叉树的代号\\n\ scanf(\"%d\ if(T[n1]==NULL){ printf(\"请扩展二叉树的先序序列输入！\\n\"); Creat(T[n1]); } else printf(\"该二叉树非空！\\n\"); break; case 2: printf(\"你想要先序输出哪个二叉树？\\n\"); scanf(\"%d\ if(T[n2]==NULL) printf(\"该二叉树为空！\\n\"); else{ Pre(T[n2]); printf(\"\\n\"); } break; case 3: printf(\"你想要中序输出哪个二叉树？\\n\"); scanf(\"%d\ if(T[n3]==NULL) printf(\"该二叉树为空！\\n\"); else{ Mid(T[n3]); printf(\"\\n\"); } break; case 4: printf(\"你想要中序输出哪个二叉树？\\n\"); scanf(\"%d\ if(T[n4]==NULL) printf(\"该二叉树为空！\\n\"); else{ Post(T[n4]);

printf(\"\\n\"); } break; case 5: printf(\"你想要求哪个二叉树的节点数？\\n\"); scanf(\"%d\ if(T[n5]==NULL) printf(\"该二叉树为空！\\n\"); else printf(\"节点数为%d\\n\ break; case 6: printf(\"你想要求哪个二叉树的叶子数？\\n\"); scanf(\"%d\ if(T[n6]==NULL) printf(\"该二叉树为空！\\n\"); else printf(\"叶子数为%d\\n\ break; case 7: printf(\"你想要求哪个二叉树的宽度？\\n\"); scanf(\"%d\ if(T[n7]==NULL) printf(\"该二叉树为空！\\n\"); else{ for(i=0;i<15;i++) a[i]=0; Kuan(T[n7],a,0); for(i=0;i<15;i++) if(a[i]>max) max=a[i]; printf(\"该树的宽度为%d\\n\ } break; case 8: printf(\"你想要求哪个二叉树的高度？\\n\"); scanf(\"%d\ if(T[n8]==NULL) printf(\"该二叉树为空！\\n\"); else{ for(i=0;i<15;i++) a[i]=0; Kuan(T[n8],a,0); for(i=0;a[i]!=0;i++);

}

}

printf(\"该树的高度为%d\\n\ } break; case 9: printf(\"你想要销毁哪个二叉树？\\n\"); scanf(\"%d\ if(T[n9]==NULL) printf(\"该二叉树为空！\\n\"); else Destroy(T[n9]); break; case 10: printf(\"你想要复制哪个二叉树？\\n\"); scanf(\"%d\ printf(\"你想要复制到哪个二叉树中？\\n\"); fflush(stdin); scanf(\"%d\ if(T[n10]==NULL) printf(\"该二叉树为空！\\n\"); else Copy(T[n10],T[n11]); break; }