数据结构实验报告-二叉树

《数据结构实验报告-二叉树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验报告实验名称二叉树班级0901姓名高傲学号日期2011129实验目的：（1）掌握二叉树的创建及各种遍历算法（2）掌握二叉树遍历算法的应用（3）掌握二叉树的中序线索化方法及对中序线索二叉树的遍历算法（4）掌握哈夫曼树的构造及哈夫曼编码实验内容：2.1编写一个程序，实现二叉树的各种运算，并在此基础上设计一个主函数完成如下功能：（1）按先序遍历的字符序列创建二叉链表存储的二叉树，二叉树如下图所示：（2）用递归算法先序遍历创建的这棵二叉树（3）用递归算法后序遍历创建的这棵二叉树（4）用递归算法中序遍历创建的这棵二叉

2、树（5）输出二叉树的结点个数（6）输出二叉树的高度（7）输出二叉树每层结点个数2.3构造哈夫曼树：编写一个程序，构造一棵哈夫曼树，输出对应的哈夫曼编码。并对如下表所示的数据进行验证。单词TheofatoandinthatheisatonforHisarebe出现频度1192677541518462450242195190181174157138124123程序源代码：2.1源程序#include#includetypedefstructbnode{chardata;structbn

3、ode*lchild,*rchild;}Bnode,*BTree;BTreet;intcount=0;//创建二叉链表BTreeCreateBinTree(){BTreet;charch;ch=getchar();if(ch=='#')t=NULL;else{t=(Bnode*)malloc(sizeof(Bnode));t->data=ch;t->lchild=CreateBinTree();t->rchild=CreateBinTree();}returnt;}//显示每个结点中的内容voidVisit(chari

4、){printf("%c",i);}//先序遍历voidPreOrder(BTreet){if(t){Visit(t->data);PreOrder(t->lchild);PreOrder(t->rchild);}}//中序遍历voidInOrder(BTreet){if(t){InOrder(t->lchild);Visit(t->data);InOrder(t->rchild);}}//后序遍历voidPostOrder(BTreet){if(t){PostOrder(t->lchild);PostOrder(t-

5、>rchild);Visit(t->data);}}//求二叉树结点数voidCount_Tree(BTreet){if(t){Count_Tree(t->lchild);count=count+1;Count_Tree(t->rchild);}}//输出二叉树的高度intHeight(BTreet){inth1,h2;if(t==NULL)return(0);else{h1=Height(t->lchild);h2=Height(t->rchild);if(h1>h2)return(h1+1);return(h2+1

6、);}}//输出二叉树没层结点个数voidLevcount(BTreet,intL,intnum[]){if(t){num[L]++;Levcount(t->lchild,L+1,num);Levcount(t->rchild,L+1,num);}}//输出num数组中每层结点的个数voidDisp_num(intnum[]){for(inti=1;i

7、请按二叉树带空指针的先序次序输入结点值:");t=CreateBinTree();printf("先序遍历:");PreOrder(t);printf("");printf("后序遍历:");PostOrder(t);printf("");printf("中序遍历:");InOrder(t);printf("");Count_Tree(t);printf("输出二叉树的结点数:%d",count);printf("输出二叉树的高度:%d",Height(t));intL=1;Levcount(t,L

8、,num);Disp_num(num);}#include#include#defineN15typedefstruct{charch[5];intweight;intlchild,rchild,parent;}Htnode;typedefstruct{char*code;charleaf[5