树和二叉树的建立和遍历-数据结构试验报告

1、实验报告一：预习要求预习树和二叉树的存储结构、以递归为基本思想的相应遍历操作。二：实验目的1、通过实验，掌握二叉树的建立与存储方法。2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。4、理解 huffman 编解码的算法三：实验内容以括号表示法输入一棵二叉树， 编写算法建立二叉树的二叉链表结构； 编写先序、中序、后序、层次遍历二叉树的算法；编写算法计算二叉树的结点数，叶子结点数，以及二叉树的深度。四: 实验原理及试验方法adt binarytree 数据对象 ：d：d 是具有相同特征的数据元素的集合数据结构 ：r：若 d= 空集，则 r

2、= 空集，称 binarytree 为空二叉树；若 d不等于空集，则r=h，h是如下二元关系：（1） 在 d中存在唯一的称为根的数据元素root ，它在关系 h下无前驱；（2） 若 d-root不等于空集，则存在d-root=d1,dr,且 d1 dr=空集；（3） 若 d1不等于空集，则d1中存在唯一的元素x1， h，且存在 d1上的关系 h1包含于 h；若 dr空集，则 dr 中存在唯一的元素xr, h， 且 存 在dr上 的 关 系hr包 含 于h；h=,h1,hr; （4） (d1,h1)是一颗符合本定义的二叉树，称为根的左子树，（dr,hr ）是一颗符合本定义的二叉树，称为根的右子树

3、。基本操作 p：createbitree(&t,definition); 初始条件： definition给出二叉树的定义。操作结果：按 definition构造二叉树 t。preordertraverse(t); 初始条件：二叉树t 存在。操作结果：先序遍历t 。inordertraverse(t); 初始条件：二叉树t 存在。操作结果：中序遍历t。postordertraverse(t); 初始条件：二叉树 t 存在。操作结果：后序遍历t。 guangyi(t); 初始条件：二叉树 t 存在。操作结果：广义表遍历。prethreading(t) 初始条件：二叉树t 存在。操作结果：

4、二叉树先序线索化。preorderthreading （thrt,t ）初始条件：二叉树t 存在。操作结果：先序遍历二叉树将二叉树线索化。preorderthread(t) 初始条件： t存在。操作结果：将先序线索化的二叉树输出。inthreading(t) 初始条件： t存在。操作结果：二叉树中序线索化。inorderthreading （thrt,t ）初始条件： t存在。操作结果：中序遍历二叉树将二叉树线索化。inorderthread （t）初始条件： t存在。操作结果：将中序线索化的二叉树输出。postorderthreading （t）初始条件： t存在。操作结果：二叉树的后序遍历

5、。postthreading （thrt,t ）初始条件： t存在。操作结果：后序遍历二叉树并将其线索化。postorderthread （t）初始条件： t存在。操作结果：将后序线索化的二叉树输出。huffmancoding（ht,hc,n）初始条件： ht ，hc存在。操作结果：构造赫夫曼树ht ，并将赫夫曼译码保存在hc 。select(ht,n,s1,s2) 初始条件： ht存在。操作结果：用 s1 和 s2 返回 ht中权值最小的两个字符。adt binarytree线索二叉树结构体：#include typedef struct tree /树的结构体定义char data; /存

6、储类型int ltag,rtag; /判断结点是的左、右孩子指针的指向变量，/ ltag=0 表示该结点有左孩子且lchild 指向左孩子， ltag=1 表示该结点的lchild 指向该结点的前驱/rtag=0 表示该结点有右孩子且rchild 指向右孩子， rtag=1 表示该结点的rchild 指向该结点的后继struct tree *lchild,*rchild; /结点的左、右孩子指针bit,*bit; 构造一个二叉树：bit createbitree(bit t) /用先序遍历构建一个二叉树 char ch; ch=getchar(); /从刚在内存中输入的字符窜中依次获得字符if

7、(ch=#) /判断接受字符是否表示空 t=null; /指针为空 else t=(bit *)malloc(sizeof(bit); /向内存中申请一个结点t-data=ch; /对结点进行字符赋值t-ltag=0; /初始化 ltag 和 rtag,让他们的初值都为0 t-rtag=0; t-lchild=createbitree(t-lchild); /构建结点的左孩子t-rchild=createbitree(t-rchild); /构建结点的右孩子 return t; /返回结点的地址 二叉树的先序遍历：void preordertraverse(bit t) /先序遍历 if(t)

8、 printf(%c,t-data); /遍历根结点preordertraverse(t-lchild); /遍历左孩子preordertraverse(t-rchild);/ 遍历右孩子 二叉树的广义表遍历：void guangyi(bit t) /广义表遍历 if(t) if(t-lchild=null & t-rchild=null) /判断结点的左右孩子都是否为空 printf(%c,t-data);/ 都为空时，输出结点字符 else /至少有一个不为空时printf(%c,t-data);/ 输出结点的字符if(t-lchild)printf(,);guangyi(t-lc

9、hild);/判断结点的左孩子是否为空，不为空时，递归的调用guangyi 函数if(t-rchild)printf(,);guangyi(t-rchild);printf();/判断结点的右孩子是否为空，不为空时，递归的调用guangyi 函数else printf(); /否则输出） 二叉树的先序线索化：void prethreading(bit p) /先序线索化 if(p) / 判断结点是否为空 if(!p-lchild)p-ltag=1;p-lchild=pre; /前驱线索if(!pre-rchild)pre-rtag=1;pre-rchild=p; /后继线索pre=p; /保持

10、 pre 指向 p 的前驱if(p-ltag=0)prethreading(p-lchild);/ 左子树线索化if(p-rtag=0)prethreading(p-rchild); /右子树线索化 bit preorderthreading(bit thrt,bit t)/先序遍历二叉树t，并将其线索化， thrt 指向头结点并返回到主函数中 thrt=(bit)malloc(sizeof(bit);/相内存中申请结点thrt-data=#; /头指针内容为空thrt-ltag=0;thrt-rtag=1; /建立头结点thrt-rchild=thrt;/ 右指针回指if(!t)/ 若二叉树

11、为空，则左指针回指 thrt-lchild=thrt; else thrt-lchild=t; pre=thrt; prethreading(t); /先序遍历进行先序线索化pre-rchild=thrt;pre-rtag=1;/ 最后一个结点的线索化thrt-rchild=null; return thrt; 先序二叉树的还原：int returntree(bit t) if(t-ltag=0)returntree(t-lchild);/遍历左子树 ,找到 ltag=1 的结点else t-lchild=null; /令左指针指向空if(t-rtag=0)returntree(t-rchil

12、d);/遍历右子树，找到rtag=1 的结点else t-rchild=null; /令右指针指向空 7、树的清空：int cleantree(bit t) / 树的清空if(t) if(t-lchild)cleantree(t-lchild); if(t-rchild)cleantree(t-rchild); free(t); 赫夫曼树的结构体：typedef struct / 赫夫曼编码结构体char ch; /编码存储类型unsigned int weight;/ 权值unsigned int parent,lchild,rchild; / 双亲、左孩子、右孩子htnode,*huffm

13、antree; typedef char *huffmancode; /动态分配数组存储赫夫曼编码两个权值最小字符的寻找：int select(huffmantree ht,int n,int *s1,int *s2) /在赫夫曼树中选取两个双亲为零且权值最小的两个节点，用s1、s2 返回 int i,j; for(j=1;j=n;+j) if(htj.parent=0) /选取第一个双亲不为零的结点赋值给s1 *s1=j; break; for(i=j+1;i=n;+i) if(hti.weightht*s1.weight&hti.parent=0)/选出权值最小的节点*s1=i;

14、for(j=1;j=n;+j) /选出双亲为零且不是s1 的结点if(htj.parent=0&*s1!=j) *s2=j; break; for(i=j+1;i=n;+i) if(hti.weightht*s2.weight&hti.parent=0&*s1!=i) /选出权值次小的节点 *s2=i; if(*s2*s1) /判断两个权值的大小是否符合要求，不符合交换 i=*s1; *s1=*s2; *s2=i; 赫夫曼编码：void huffmancoding(huffmantree ht,huffmancode *hc,int n) /构造赫夫曼树ht，并求出赫夫

15、曼树所对应的的赫夫曼编码 int i,j,f,m,c,start; int s1,s2; char *cd; m=n*2; for(i=1;i=n;i+) /初始构造赫夫曼树 printf( 请输入第 %d 个字符和字符对应权值（中间用空格隔开，如：g 29）： ,i); scanf(%s %d,&hti.ch,&hti.weight); hti.parent=0; /双亲和左右孩子均初始化为0；hti.lchild=0; hti.rchild=0; for(;im;i+) /将没有存放字符的结点权值、双亲和左右孩子均初始化为0 hti.weight=0; hti.lchild

16、=0; hti.rchild=0; hti.parent=0; for(i=n+1;im;i+) select(ht,i-1,&s1,&s2);/ 从结点中选取两个最小的结点hts1.parent=i;hts2.parent=i; /将新结点的位置的值赋给最小的两个结点的双亲hti.lchild=s1;hti.rchild=s2; /将最小的两个结点的位置的值赋给新结点的左右孩子hti.weight=hts1.weight+hts2.weight; /将两个最小结点的权值相加赋新结点的权值 cd=(char *)malloc(n*sizeof(char); /向内存中申请分配求

17、编码的存储空间cdn-1=0;/ 编码的标示符for(i=1;i=n;i+)/逐个字符求赫夫曼编码 start=n-1; /编码结束符位置for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/从叶子到根逆向求编码 if(htf.lchild=c)cd-start=0; / 判断 c 是结点的那个孩子，左孩子添加0，右孩子添加1 else cd-start=1; hci=(char *)malloc(n-start)*sizeof(char);/向内存中申请第i 个字符编码分配空间strcpy(hci,&cdstart); /从 cd 复制编码串到hc

18、printf( 字符译码 n); for(i=1;i=n;i+) /显示译码 printf(%5c %sn,hti.ch,hci); free(cd);/释放空间 六、思考题：1. 输入进行编码的字符串2. 遍历字符串，并为叶子节点权重赋值3. 依次对各字符进行哈弗曼编码， 自下往上，若是双亲节点左孩子则编码前插入0，若是双亲节点右孩子则编码钱插入1。4. 显示各字符的哈弗曼编码。5. 对字符串进行编码，挨个遍历字符，找到相应的编码，复制到总的编码里，最后输出字符串的编码。6. 对字符串的哈弗曼码进行译码。自上往下，若是0，则递归到左孩子，若是1，则递归到右孩子，知道叶子节点，输出该叶子节点代

19、表字符，再继续遍历。7. 分析内存占用情况。若用ascii 编码，每个字符占1 个字节，即 8bit ，该情况下占用内存就是 （字符长度） *8。若用哈弗曼编码， 占用内存是各（字符频度）*（每个字符占用位数）之和。七：参考文献：1. c语言入门经典（第5 版）作者： ( 美）霍尔顿 (horton,i.)著，杨浩译，清华大学出版社， 2013年 11 月2. 数据结构（ c 语言版），严蔚敏，吴伟民编著，清华大学出版社，2011年 11 月3. 数据结构（ c语言版）（第 2 版），严蔚敏，李冬梅，吴伟民编著，人民邮电出版社， 2015年 2 月八：源代码：1、二叉树：#include ty

20、pedef struct tree /树的结构体定义char data; /存储类型int ltag,rtag; /判断结点是的左、右孩子指针的指向变量，/ ltag=0表示该结点有左孩子且lchild 指向左孩子， ltag=1 表示该结点的 lchild指向该结点的前驱/rtag=0表示该结点有右孩子且rchild 指向右孩子，rtag=1表示该结点的 rchild指向该结点的后继struct tree *lchild,*rchild; /结点的左、右孩子指针bit,*bit; bit createbitree(bit t) /用先序遍历构建一个二叉树 char ch; ch=getcha

21、r(); /从刚在内存中输入的字符窜中依次获得字符if(ch=#) /判断接受字符是否表示空 t=null; /指针为空 else t=(bit *)malloc(sizeof(bit); /向内存中申请一个结点t-data=ch; /对结点进行字符赋值t-ltag=0; /初始化 ltag 和 rtag,让他们的初值都为0 t-rtag=0; t-lchild=createbitree(t-lchild); /构建结点的左孩子t-rchild=createbitree(t-rchild); /构建结点的右孩子 return t; /返回结点的地址 /二叉树的递归遍历void preorder

22、traverse(bit t) /先序遍历 if(t) printf(%c,t-data); /遍历根结点preordertraverse(t-lchild); /遍历左孩子preordertraverse(t-rchild);/ 遍历右孩子 void inordertraverse(bit t) /中序遍历 if(t) inordertraverse(t-lchild);/遍历左孩子printf(%c,t-data);/ 遍历根结点inordertraverse(t-rchild);/遍历右孩子 void postordertraverse(bit t) /后序遍历 if(t) postor

23、dertraverse(t-lchild);/遍历左孩子postordertraverse(t-rchild);/ 遍历右孩子printf(%c,t-data);/ 遍历根结点 void guangyi(bit t) /广义表遍历 if(t) if(t-lchild=null & t-rchild=null) /判断结点的左右孩子都是否为空 printf(%c,t-data);/ 都为空时，输出结点字符 else /至少有一个不为空时printf(%c,t-data);/ 输出结点的字符if(t-lchild)printf(,);guangyi(t-lchild);/判断结点的左孩子是

24、否为空，不为空时，递归的调用guangyi 函数if(t-rchild)printf(,);guangyi(t-rchild);printf();/判 断 结 点 的右孩子是否为空，不为空时，递归的调用guangyi 函数else printf(); /否则输出） /二叉树的线索化bit pre;/定义全局的指针变量，用于指向当前时刻的结点位置/先序线索void prethreading(bit p) /先序线索化 if(p) / 判断结点是否为空 if(!p-lchild)p-ltag=1;p-lchild=pre; /前驱线索if(!pre-rchild)pre-rtag=1;pre-rc

25、hild=p; /后继线索pre=p; /保持 pre指向 p 的前驱if(p-ltag=0)prethreading(p-lchild);/ 左子树线索化if(p-rtag=0)prethreading(p-rchild); / 右子树线索化 bit preorderthreading(bit thrt,bit t)/ 先序遍历二叉树 t，并将其线索化， thrt 指向头结点并返回到主函数中 thrt=(bit)malloc(sizeof(bit);/ 相内存中申请结点thrt-data=#; /头指针内容为空thrt-ltag=0;thrt-rtag=1; /建立头结点thrt-rchil

26、d=thrt;/ 右指针回指if(!t)/ 若二叉树为空，则左指针回指 thrt-lchild=thrt; else thrt-lchild=t; pre=thrt; prethreading(t); /先序遍历进行先序线索化pre-rchild=thrt;pre-rtag=1;/最后一个结点的线索化thrt-rchild=null; return thrt; void preorderthread(bit t) /先序遍历 if(t) /判断输出的内容if(t-ltag=0 & t-rtag=0)printf(%c的 左 、 右 孩 子 分 别为：%c %cn,t-data,t-lc

27、hild-data,t-rchild-data); if(t-ltag=1 & t-rtag=0)printf(%c的 右 孩 子 和 前 驱 分 别为：%c %cn,t-data,t-rchild-data,t-lchild-data); if(t-ltag=0 & t-rtag=1)printf(%c的 左 孩 子 和 后 继 分 别为：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t-rtag=1)printf(%c的 前 驱 和 后 继 分 别为：%c %cn,t-data,t-lchild-

28、data,t-rchild-data); if(t-ltag=0)preorderthread(t-lchild); /遍历左孩子if(t-rtag=0)preorderthread(t-rchild); / 遍历右孩子 /中序线索int inthreading(bit p)/ 中序线索化 if(p) inthreading(p-lchild);/ 左子树线索化if(!p-lchild)p-ltag=1;p-lchild=pre;/判断结点的左孩子是否存在，让其指向其前驱if(!pre-rchild)pre-rtag=1;pre-rchild=p;/ 后继线索化pre=p;/保持 pre指向

29、p 的前驱inthreading(p-rchild);/右子树线索化 bit inorderthreading(bit thrt,bit t)/ 中序遍历二叉树 t，并将其线索化， thrt 指向头结点并返回到主函数中 thrt=(bit)malloc(sizeof(bit);/ 向内存中申请一个头结点thrt-data=#;/给头结点赋值为空thrt-ltag=0; thrt-rtag=1;thrt-rchild=thrt;/ 头结点右指针回指if(!t)thrt-lchild=thrt;/ 若二叉树为空，则左指针回指else thrt-lchild=t;/ 二叉树不为空，左指针指向树pre

30、=thrt;/pre 赋初值inthreading(t);/中序线索化二叉树pre-rchild=thrt;/ 最后一个结点线索化pre-rtag=1; thrt-rchild=null; return thrt; void inorderthread(bit t) if(t) if(t-ltag=0)preorderthread(t-lchild); /遍历左孩子if(t-ltag=0 & t-rtag=0)printf(%c的 左 、 右 孩 子 分 别为：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t

31、-rtag=0)printf(%c的 右 孩 子 和 前 驱 分 别为：%c %cn,t-data,t-rchild-data,t-lchild-data); if(t-ltag=0 & t-rtag=1)printf(%c的 左 孩 子 和 后 继 分 别为：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t-rtag=1)printf(%c的 前 驱 和 后 继 分 别为：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-rtag=0)preorderthre

32、ad(t-rchild); / 遍历右孩子 /后序线索int postthreading(bit p) if(p) inthreading(p-lchild); inthreading(p-rchild); if(!p-lchild)p-ltag=1;p-lchild=pre; if(!pre-rchild)pre-rtag=1;pre-rchild=p; pre=p; bit postorderthreading(bit thrt,bit t) thrt=(bit)malloc(sizeof(bit); thrt-data=#; thrt-ltag=0; thrt-rtag=1;thrt-r

33、child=thrt; if(!t)thrt-lchild=thrt; else thrt-lchild=t; pre=thrt; inthreading(t); pre-rchild=thrt; pre-rtag=1; thrt-rchild=null; return thrt; void postorderthread(bit t) if(t) if(t-ltag=0)preorderthread(t-lchild); /遍历左孩子if(t-rtag=0)preorderthread(t-rchild); / 遍历右孩子if(t-ltag=0 & t-rtag=0)printf(%

34、c的 左 、 右 孩 子 分 别为：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t-rtag=0)printf(%c的 右 孩 子 和 前 驱 分 别为：%c %cn,t-data,t-rchild-data,t-lchild-data); if(t-ltag=0 & t-rtag=1)printf(%c的 左 孩 子 和 后 继 分 别为：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t-rtag=1)printf(%c的 前

35、驱 和 后 继 分 别为：%c %cn,t-data,t-lchild-data,t-rchild-data); /将线索树还原成普通树int returntree(bit t) if(t-ltag=0)returntree(t-lchild);/ 遍历左子树 ,找到 ltag=1的结点else t-lchild=null; /令左指针指向空if(t-rtag=0)returntree(t-rchild);/遍历右子树，找到rtag=1 的结点else t-rchild=null; /令右指针指向空 int cleantree(bit t) / 树的清空if(t) if(t-lchild)cl

36、eantree(t-lchild); if(t-rchild)cleantree(t-rchild); free(t); void main() bit *l,*thrt; char x; printf( *n); printf( 二叉树的三种遍历（ #表示为空！） n); printf( 例如输入： abc#de#g#f#n); printf( *n); printf( 请输入二叉树： ); l=createbitree(l); while(1) printf( =*操 作 选 择*=n); printf( * 遍 历* 请输入 *1n); printf( * 线 索* 请输入 *2n);

37、printf( * 退 出* 请输入 *0n); printf( 操作数： ); scanf(%s,&x); switch(x) case 1: printf( 先序遍历： ); preordertraverse(l); printf(n); printf( 中序遍历： ); inordertraverse(l); printf(n); printf( 后序遍历： ); postordertraverse(l); printf(n); printf( 广义遍历： ); guangyi(l); printf(n);break; case 2: thrt=preorderthreading

38、(thrt,l); if(thrt)printf( 二叉树先序线索化成功！ n); preorderthread(l); returntree(l); free(thrt); thrt=inorderthreading(thrt,l); if(thrt)printf( 二叉树中序线索化成功！ n); inorderthread(l); returntree(l); free(thrt); thrt=postorderthreading(thrt,l); if(thrt)printf( 二叉树后序线索化成功！ n); postorderthread(l); returntree(l); free

39、(thrt);break; case 0:break; default:printf(输入有误！请重新输入！n); if(x=0)break; 2、赫夫曼编码：#include typedef struct /赫夫曼编码结构体char ch; /编码存储类型unsigned int weight;/权值unsigned int parent,lchild,rchild; / 双亲、左孩子、右孩子htnode,*huffmantree; typedef char *huffmancode; /动态分配数组存储赫夫曼编码int select(huffmantree ht,int n,int *s1

40、,int *s2) /在赫夫曼树中选取两个双亲为零且权值最小的两个节点，用s1、s2 返回 int i,j; for(j=1;j=n;+j) if(htj.parent=0) /选取第一个双亲不为零的结点赋值给s1 *s1=j; break; for(i=j+1;i=n;+i) if(hti.weightht*s1.weight&hti.parent=0)/选出权值最小的节点*s1=i; for(j=1;j=n;+j) /选出双亲为零且不是s1的结点if(htj.parent=0&*s1!=j) *s2=j; break; for(i=j+1;i=n;+i) if(hti.weightht*s2.weight&hti.parent=0&*s1!=i) /选出权值次小的节点 *s2=i; if(*s2*s1) /判断两个权值的大小是否符合要求，不符合交换 i=*s1; *s1=*s2; *s2=i; void huffmancoding(huffma