实验一栈与队列.pptVIP

实验三 二叉树及其应用 实验目的 熟悉二叉树的操作，并且能够应用二叉树解决实际问题。 实验要求 仔细阅读课本， 掌握二叉树的存储及其操作； 按照实验内容要求，完成程序的编写和测试。仔细测试你的程序！你的程序必须能够正常运行！你的程序必须具有可读性。 在完成每个任务的同时, 认真书写实验报告, 包括: 程序设计思想, 测试过程报告, 程序使用说明和文件清单, 以及其他实验体会。 每个任务均应由两个人为一组协同完成。 递交打包文件命名方式: 学号1姓名1_学号2姓名2 递交内容：实验报告，代码及运行测试的有关文件。 Deadline:实验内容 实现建立二叉树和遍历二叉树的算法。假设二叉树用二叉链表存储。 给定二叉树的前序遍历序列，如果用一个特殊字符表示无子结点，则由此序列可以唯一确定 一棵二叉树，如下图。使用先序序列和中序序列也可以唯一确定一棵二叉树（参见E17，P444）。 分别使用上述方法实现建立二叉树的算法 Binary_tree::Binary_tree(const char *s); /* s是二叉树的前序遍历序列，其中包括了表示无子结点的特殊字符。算法按照先序序列建立二叉树。 */ Binary_tree::Binary_tree(const char *p, const char *s); /* p是二叉树的先序序列，s是二叉树的中序序列。算法建立二叉树，使其先序序列和中序序列分别为p和s。 */ 实现中序遍历二叉树的递归算法recursiveInorder和非递归算法nonrecursiveInorder: void Bianry_tree::recursiveInorder(void(*visit)(char e)); void Bianry_tree::nonrecursiveInorder(void (*visit)(char e)); 设计一个测试程序，检查上述两个遍历算法结果是否相同： bool Bianry_tree:: testTraverse(); /* 测试两个遍历算法recursiveInorder和nonrecursiveInorder结果 是否相同。如果相同，返回true, 否则返回false。 注：为了检查遍历序是否相同，你可能需要在遍历中记录下遍历结点序列。 */ 随机建立一些二叉树， 检验你的遍历算法实现是否正确。 （选做）你的任务是编写一个基于Huffman编码的压缩和解压缩算法。 假设压缩和解压缩程序分别为huffmanCoding, huffmanDecoding, 则运行 huffmanCoding inputfile outputfile 将文件inputfile编码后输出到outputfile. 运行huffmanDecoding inputfile outputfile将编码文件inputfile译码后输出到outputfile. 注意，为了译码， 你需要将Huffman编码存储在编码文件中。