实验2二 叉 树 的基本操作及哈夫曼编码 (1)

二叉树的基本操作及哈夫曼编码实现实验目的•1掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。•2掌握用指针类型描述、访问和处理二叉树的运算。•3掌握哈夫曼编码实验要求•认真阅读和掌握本实验的程序•上机运行程序。•保存和打印出程序的运行结果，并结合程序进行分析。•按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。实验内容•1输入字符序列，建立二叉链表。•2按先序、中序和后序遍历二叉树（递归算法）。•3按某种形式输出整棵二叉树。•4求二叉树的高度。•5求二叉树的叶节点个数。•6交换二叉树的左右子树。•7借助队列实现二叉树的层次遍历。•8哈夫曼编码的实现(选作)•9在主函数中设计一个简单的菜单，分别调试上述算法。•运行结果：•===================主菜单===================•1.建立二叉树方法1•2.建立二叉树方法2•3.先序递归遍历二叉树•4.中序递归遍历二叉树•5.后序递归遍历二叉树•6.层次遍历二叉树•7.计算二叉树的高度•8.计算二叉树中叶结点个数•9.交换二叉树的左右子树•10.打印二叉树•0.结束程序运行•============================================•请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)1•请输入二叉树各结点的编号和对应的值（如1，a）：1，a•请继续输入二叉树各结点的编号和对应的值：2，b•请继续输入二叉树各结点的编号和对应的值：3，c•请继续输入二叉树各结点的编号和对应的值：4，d•请继续输入二叉树各结点的编号和对应的值：6，e•请继续输入二叉树各结点的编号和对应的值：7，f•请继续输入二叉树各结点的编号和对应的值：9，g•请继续输入二叉树各结点的编号和对应的值：13，h•请继续输入二叉树各结点的编号和对应的值：0，#•===================主菜单===================);•1.建立二叉树方法1•2.建立二叉树方法2•3.先序递归遍历二叉树•4.中序递归遍历二叉树•5.后序递归遍历二叉树•6.层次遍历二叉树•7.计算二叉树的高度•8.计算二叉树中叶结点个数•9.交换二叉树的左右子树•10.打印二叉树•0.结束程序运行•============================================•请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)4•中序遍历二叉树：dgbaehcf•===================主菜单===================);•1.建立二叉树方法1•2.建立二叉树方法2•3.先序递归遍历二叉树•4.中序递归遍历二叉树•5.后序递归遍历二叉树•6.层次遍历二叉树•7.计算二叉树的高度•8.计算二叉树中叶结点个数•9.交换二叉树的左右子树•10.打印二叉树•0.结束程序运行•============================================•请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)7•二叉树的高度为：4程序清单•#includestdio.h•#includestdlib.h•#defineM100•typedefcharEtype;//定义二叉树结点值的类型为字符型•typedefstructBiTNode//树结点结构•{•Etypedata;•structBiTNode*lch,*rch;•}BiTNode,*BiTree;•BiTreeque[M];•intfront=0,rear=0;•//函数原型声明•BiTNode*creat_bt1();•BiTNode*creat_bt2();•voidpreorder(BiTNode*p);•voidinorder(BiTNode*p);•voidpostorder(BiTNode*p);•voidenqueue(BiTree);•BiTreedelqueue();•voidlevorder(BiTree);•inttreedepth(BiTree);•voidprtbtree(BiTree,int);•voidexchange(BiTree);•intleafcount(BiTree);•voidpaintleaf(BiTree);•BiTNode*t;•intcount=0;•//主函数•voidmain()•{•charch;•intk;•do{•printf(\n\n\n);•printf(\n===================主菜单===================);•printf(\n\n1.建立二叉树方法1);•printf(\n\n2.建立二叉树方法2);•printf(\n\n3.先序递归遍历二叉树);•printf(\n\n4.中序递归遍历二叉树);•printf(\n\n5.后序递归遍历二叉树);•printf(\n\n6.层次遍历二叉树);•printf(\n\n7.计算二叉树的高度);•printf(\n\n8.计算二叉树中叶结点个数);•printf(\n\n9.交换二叉树的左右子树);•printf(\n\n10.打印二叉树);•printf(\n\n0.结束程序运行);•printf(\n============================================);•printf(\n请输入您的选择(0,1,2,3,4,5,6,7,8,9,10));•scanf(%d,&k);•switch(k)•{•case1:t=creat_bt1();//调用性质5建立二叉树算法•break;•case2:printf(\n请输入二叉树各结点值:);fflush(stdin);•t=creat_bt2();//调用递归建立二叉树算法•break;•case3:if(t){•printf(先序遍历二叉树:);•preorder(t);•printf(\n);•}•elseprintf(二叉树为空!\n);•break;••case4:if(t)•{printf(中序遍历二叉树:);•inorder(t);•printf(\n);•}•elseprintf(二叉树为空!\n);•break;•case5:if(t)•{printf(后序遍历二叉树:);•postorder(t);•printf(\n);•}•elseprintf(二叉树为空!\n);•break;••case6:if(t)•{printf(层次遍历二叉树：);•levorder(t);•printf(\n);•}•elseprintf(二叉树为空！\n);•break;•case7:if(t)•{printf(二叉树的高度为：%d,treedepth(t));•printf(\n);•}•elseprintf(二叉树为空！\n);•break;••case8:if(t)•{printf(二叉树的叶子结点数为：%d\n,leafcount(t));•printf(二叉树的叶结点为：);paintleaf(t);•printf(\n);•}•elseprintf(二叉树为空！\n);•break;case9:if(t)•{printf(交换二叉树的左右子树：\n);•exchange(t);•prtbtree(t,0);•printf(\n);•}•elseprintf(二叉树为空！\n);•break;••case10:if(t)•{printf(逆时针旋转90度输出的二叉树：\n);•prtbtree(t,0);•printf(\n);•}•elseprintf(二叉树为空！\n);•break;case0:exit(0);•}//switch••}while(k=1&&k=10);•printf(\n再见！按回车键，返回…\n);•ch=getchar();•}//main•//利用二叉树性质6，借助一维数组V建立二叉树•BiTNode*creat_bt1()•{BiTNode*t,*p,*v[20];inti,j;Etypee;•/*输入结点的序号i、结点的数据e*/•printf(\n请输入二叉树各结点的编号和对应的值（如1，a）：);•scanf(%d,%c,&i,&e);•while(i!=0&&e!='#')//当i为0，e为'#'时，结束循环•{•p=(BiTNode*)malloc(sizeof(BiTNode));•p-data=e;•p-lch=NULL;•p-rch=NULL;•v[i]=p;•if(i==1)•t=p;//序号为1的结点是根•else•{•j=i/2;•if(i%2==0)v[j]-lch=p;//序号为偶数，作为左孩子•elsev[j]-rch=p;//序号为奇数，作为右孩子•}•printf(\n请继续输入二叉树各结点的编号和对应的值：);•scanf(%d,%c,&i,&e);•}•return(t);•}//creat_bt1;•//模仿先序递归遍历方法，建立二叉树•BiTNode*creat_bt2()•{•BiTNode*t;•Etypee;•scanf(%c,&e);•if(e=='#')t=NULL;//对于'#'值，不分配新结点•else{•t=(BiTNode*)malloc(sizeof(BiTNode));•t-data=e;•t-lch=creat_bt2();//左孩子获得新指针值•t-rch=creat_bt2();//右孩子获得新指针值•}•return(t);•}//creat_bt2•//模仿先序递归遍历方法，建立二叉树•BiTNode*creat_bt2()•{•BiTNode*t;•Etypee;•scanf(%c,&e);•if(e=='#')t=NULL;//对于'#'值，不分配新结点•else{•t=(BiTNode*)malloc(sizeof(BiTNode));•t-data=e;•t-lch=creat_bt2();//左孩子获得新指针值•t-rch=creat_bt2();//右孩子获得新指针值•}•return(t);•}//creat_bt2•//先序递归遍历二叉树•voidpreorder(BiTNode*p)•{•if(p){•printf(%3c,p-data);•preorder(p-lch);•preorder(p-rch);•}•}//preorder•//中序递归遍历二叉树•voidinorder(BiTNode*p)•{•if(p){•inorder(p-lch);•printf(%3c,p-data);•inorder(p-rch);•}•}//inorder•//后序递归遍历二叉树•voidpostorder(BiTNode*p)•{•if(p){postorder(p-lch);•postorder(p-rch);•printf(%3c,p-data);•}•}//postorder•//层次遍历二叉树•voidenqueue(BiTreeT)•{•if(front!=(rear+1)%M)•{rear=(rear+1)%M;•que[rear]=T;}•}•BiTreedelqueue()•{•if(front==rear)returnNULL;•front=(front+1)%M;•return(que[front]);•}层次遍历二叉树(cont.)•voidlevorder(BiTreeT)//层次遍历二叉树•{•BiTreep;•if(T){enqueue(T);•while(front!=rear){•p=delqueue();•printf(%3d,p-data);•if(p-lch!=NULL)enqueue(p-lch);•if(p-rch!=NULL)enqueue(p-rc