数据结构--二叉树操作

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

1、实验目的：1.基木要求：深刻理解二叉树性质和及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；2.较高要求：在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。实验内容：1.以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能:1…建立树2…前序遍历树3…中序（非递归）遍历树4…后序遍历树0…结束2）实验要求：在程序屮定义下述函数，并实现要求的函数功能：CreateTreeO:按从键盘输入的

2、前序序列，创建树PreOrderTree（）:前序遍历树（递归）InOrderTree（）:中序（非递归）遍历树LaOrderTreeO:后序遍历树（递归）3）实验提示：◊二叉链表存储数据类型定义#defineElemTypechar//元素类型typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;◊元素类型可以根据实际情况选取。4）注意问题：◊注意理解递归算法的执行步骤。◊注意字符类型数据在输入吋的处理。◊重点理解如何利用栈结构实现非递归算法1.编写算法交换二叉树中所

3、有结点的左、右子树（实验类型：综合型）1）问题描述：编写一算法，交换二叉树中所有结点的左、右子树2）实验要求：以二叉链表作为存储结构3）实现提示：设二叉树的根指针未I,且以二叉链表表示，可利用一个类型为seqstack的指针来实现，1L栈单元包含两个域，一个为data,另一个为top,整个栈容量为maxsize,当树非空时，将当前的树根结点入栈，同吋将当前栈顶元素出栈当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换；再将交换后的左指针或右指针入栈，这样反复进行，直到栈空为止。4）注意问题：◊注意理解算法中栈结构的利用2.试编写按层次顺序遍历二

4、叉树的算法（实验类型：综合型）1）问题描述：编写按层次顺序遍历二叉树的算法2）实验要求：以二叉链表作为存储结构3）实现提示：本算法要采用一个队列q,先将二叉树根结点入队列，然后出队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树,便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先岀，从而达到按层次顺序遍历二叉树目的。4）注意问题：◊理解算法中队列结构的利用3.实现一个哈夫曼编/译码系统（实验类型：综合型）1）问题描述：利用哈夫曼编码进行信息通信可以大大编写按层次顺序遍历二叉树的算法提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发

5、送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编码/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。2）实验要求：一个完整的系统应具有以下功能：（1）I：初始化（Initialization）□从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree屮。（2）E：编码（Encoding）o利用已建好的哈夫曼树对文件ToBeTran屮的正文进行编码，然后将结果存入文件CodeFile屮。（3）D：译码（Decoding）o利用已建好的哈夫曼树将文件CodeFile屮的代码进

6、行译码，结果存入文件TextFile屮。(4)P：打印代码文件(Print)o将文件CodcFilc以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。(5)T：打印哈夫曼树(Treeprinting)o将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TrecPrint中。3)实现提不：(1)文件CodeFile的基类型可以设为字节型。(2)用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”,表示退出运行Quito请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了

7、“E”为止。(3)在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。1.森林(孩子兄弟链表)的建立与遍历(实验类型：验证型)1)问题描述：以“孩子兄弟二叉链表”为存储结构，建立和遍历一个森林2)实验要求：以“孩子兄弟二叉链表”作为存储结构3)实现提示：◊可参考二叉树的前序遍历和中序遍历算法4)注意问题：◊理解二叉树与树的对应关系◊理解树和森林遍历的实质实验内容(应包括实验题目、实验要求、实验任务等)附录(可包括源程