二叉树运算菜单实验报告.docx

二叉树运算菜单实验报告一：问题描述：功能要求(1-3必做，其他选做）,或Huffman编码 1. 创建 2. 遍历（先序、中序、后序、层序） 3. 计算（结点数、叶子数、高度、宽度） 4. 查找（找结点、找双亲、找孩子、找兄弟，找祖先） 5. 判断（二叉排序树、平衡二叉树、完全二叉树） 6. 处理（左右子树互换，销毁、删子树、插子树、复制） 二：算法描述：主函数用switch函数创建菜单，菜单下使用各个子函数完成各项功能。我使用的二叉树定义是链式定义，包括左孩子，右孩子，数据。创建用的是扩展二叉树的先序序列以保证唯一性。三：数据结构的描述：typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;如上所示。四：算法时空分析：时间复杂度较为合理（因为用的是书上的算法。）；空间复杂度一般，没编；几个函数就二百四十行了。五：实验收获：对二叉树的定义和使用有了更加清晰的认识，再一次的加强了编程能力，锻炼了耐心，发现了一个小知识，就是fflush(stdin)函数可以清空缓存，很有用。六：源程序：#include#include#define BiTree_Size 20typedef struct BiTNode/定义了二叉树结构体。char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Creat(BiTree &t)/创建，#表示空。char e;fflush(stdin);scanf(%c,&e);if(e=#)t=NULL;elset=(BiTNode*)malloc(sizeof(BiTNode);t-data=e;Creat(t-lchild);Creat(t-rchild); void Pre(BiTree &t)/前序遍历。if(!t)return;elseprintf(%c ,t-data);Pre(t-lchild);Pre(t-rchild);void Mid(BiTree &t)/中序遍历。if(!t)return;elseMid(t-lchild);printf(%c ,t-data);Mid(t-rchild);void Post(BiTree &t)/后续遍历。if(!t)return;elsePost(t-lchild);Post(t-rchild);printf(%c ,t-data);int Count(BiTree &t,int i)/求节点数。if(!t)return i;elsei+;i=Count(t-lchild,i);i=Count(t-rchild,i);return i;int Yezi(BiTree &t,int i)/求叶子树，利用先序遍历。if(!t)return i;elseif(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;elseai+;/printf(%dn,ai);Kuan(t-lchild,a,i+1);Kuan(t-rchild,a,i+1);return;void Destroy(BiTree &t)/销毁二叉树。if(!t)return;elseDestroy(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 TBiTree_Size=NULL;int a15=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,&menue); switch(menue) case 0:return; case 1: printf(从0%d选择一个作为二叉树的代号n,BiTree_Size-1); scanf(%d,&n1);if(Tn1=NULL)printf(请扩展二叉树的先序序列输入！n);Creat(Tn1);elseprintf(该二叉树非空！n);break;case 2:printf(你想要先序输出哪个二叉树？n);scanf(%d,&n2);if(Tn2=NULL)printf(该二叉树为空！n);elsePre(Tn2);printf(n);break;case 3:printf(你想要中序输出哪个二叉树？n);scanf(%d,&n3);if(Tn3=NULL)printf(该二叉树为空！n);elseMid(Tn3);printf(n);break;case 4:printf(你想要中序输出哪个二叉树？n);scanf(%d,&n4);if(Tn4=NULL)printf(该二叉树为空！n);elsePost(Tn4);printf(n);break;case 5:printf(你想要求哪个二叉树的节点数？n);scanf(%d,&n5);if(Tn5=NULL)printf(该二叉树为空！n);elseprintf(节点数为%dn,Count(Tn5,0);break;case 6:printf(你想要求哪个二叉树的叶子数？n);scanf(%d,&n6);if(Tn6=NULL)printf(该二叉树为空！n);elseprintf(叶子数为%dn,Yezi(Tn6,0);break;case 7:printf(你想要求哪个二叉树的宽度？n);scanf(%d,&n7);if(Tn7=NULL)printf(该二叉树为空！n);elsefor(i=0;i15;i+)ai=0;Kuan(Tn7,a,0);for(i=0;imax)max=ai;printf(该树的宽度为%dn,max);break;case 8:printf(你想要求哪个二叉树的高度？n);scanf(%d,&n8);if(Tn8=NULL)printf(该二叉树为空！n);elsefor(i=0;i15;i+)ai=0;Kuan(Tn8,a,0);for(i=0;ai!=0;i+);printf(该树的高度为%dn,i);break;case 9:printf(你想要销毁哪个二叉树？n);scanf(%d,&n9);if(Tn9=NULL)printf(该二叉树为空！n);elseDestr