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

数据结构实验报告实验名称二叉树班级0901姓名高傲学号20091185015日期2011 12 9实验目的：（1）掌握二叉树的创建及各种遍历算法（2）掌握二叉树遍历算法的应用（3）掌握二叉树的中序线索化方法及对中序线索二叉树的遍历算法（4）掌握哈夫曼树的构造及哈夫曼编码实验内容：2.1编写一个程序，实现二叉树的各种运算，并在此基础上设计一个主函数完成如下功能：（1）按先序遍历的字符序列创建二叉链表存储的二叉树，二叉树如下图所示：（2）用递归算法先序遍历创建的这棵二叉树（3）用递归算法后序遍历创建的这棵二叉树（4）用递归算法中序遍历创建的这棵二叉树（5）输出二叉树的结点个数（6）输出二叉树的高度（7）输出二叉树每层结点个数2.3 构造哈夫曼树：编写一个程序，构造一棵哈夫曼树，输出对应的哈夫曼编码。并对如下表所示的数据进行验证。单词theofatoandinthatheisatonforhisarebe出现频度1192677541518462450242195190181174157138124123程序源代码：2.1源程序#include #include typedef struct bnodechar data;struct bnode *lchild, *rchild;bnode, *btree;btree t;int count=0;/创建二叉链表btree createbintree()btree t;char ch;ch=getchar();if(ch=#) t=null;elset=(bnode*)malloc(sizeof(bnode);t-data=ch;t-lchild=createbintree();t-rchild=createbintree();return t;/显示每个结点中的内容void visit(char i)printf(%c,i);/先序遍历void preorder(btree t)if(t)visit(t-data);preorder(t-lchild);preorder(t-rchild);/中序遍历void inorder(btree t)if(t)inorder(t-lchild);visit(t-data);inorder(t-rchild);/后序遍历void postorder(btree t)if(t)postorder(t-lchild);postorder(t-rchild);visit(t-data);/求二叉树结点数void count_tree(btree t)if(t)count_tree(t-lchild);count=count+1;count_tree(t-rchild);/输出二叉树的高度int height(btree t)int h1, h2;if(t=null) return (0);elseh1=height(t-lchild);h2=height(t-rchild);if(h1h2) return (h1+1);return (h2+1);/输出二叉树没层结点个数void levcount(btree t, int l, int num)if(t) numl+;levcount(t-lchild, l+1, num);levcount(t-rchild, l+1, num);/输出num数组中每层结点的个数void disp_num(int num)for(int i=1; iheight(t)+1; i+)printf(第%d层结点个数:%dn, i, numi);void main()int num10=0;printf(请按二叉树带空指针的先序次序输入结点值:);t=createbintree();printf(先序遍历:);preorder(t);printf(n);printf(后序遍历:);postorder(t);printf(n);printf(中序遍历:);inorder(t);printf(n);count_tree(t);printf(输出二叉树的结点数:%dn,count);printf(输出二叉树的高度:%dn,height(t);int l=1;levcount(t, l ,num);disp_num(num);#include #include #define n 15typedef structchar ch5;int weight;int lchild, rchild, parent;htnode;typedef structchar *code;char leaf5;int length;codetype;/对叶子结点进行排序void select(htnode huftree, int x, int *s1, int *s2)int w1=10000, w2=10000;for(int i=1; i=x; i+)if(huftreei.parent=-1)if(huftreei.weightw1)w2=w1;*s2=*s1;w1=huftreei.weight;*s1=i;elseif(huftreei.weightw2)w2=huftreei.weight;*s2=i;/构造哈夫曼树void hufcoding(htnode huftree, codetype cd, int w, int n)int i, k, s1, s2, m, f, c, sum;char tempn;m=2*n-1;printf(请输入单词:n);for(i=1; i=n; i+) huftreei.weight=wi-1;huftreei.lchild=huftreei.rchild=huftreei.parent=-1;gets(huftreei.ch);for(i=n+1; i=m; i+)huftreei.weight=-1;huftreei.lchild=huftreei.rchild=huftreei.parent=-1;for(i=1; i=n-1; i+)select(huftree, n+i-1, &s1, &s2);sum=huftrees1.weight+huftrees2.weight;huftreen+i.weight=sum;huftrees1.parent=huftrees2.parent=n+i;huftreen+i.lchild=s1; huftreen+i.rchild=s2;for(i=1; i=0) cdi.codek+=tempc-;for(int k=0; k5; k+)cdi.leafk=huftreei.chk;cdi.length=k;/输出哈夫曼树中对应字符的编码void disp_code(codetype cd)for(int i=1; i=n; i+)printf(字符%s的编码是:%sn,cdi.leaf,cdi.code);void main()h