实验3
二叉树的基本操作与应用实验
第三次实验主要包括两部分。 1 .二叉树基本操作实验； 2 .二叉树的应用——哈夫曼树和哈夫曼编码实验。 基本操作包括存储结构的构建和遍历算法。 本文仅提供了部分参考步骤。 请尽量完成很多基本操作。
第一部分基本操作实验
[问题描述]二叉树使用二叉树的链表作为存储结构，编程实现二叉树的以下基本操作
1 .先构建二叉树链表表示的二叉树t；
2 .对该二叉树进行扫描：先后顺序、中顺序、后顺序及分层扫描序列，分别输出节点的扫描序列；
3 .求解二叉树深度、节点数、叶节点数； [数据说明] //二叉树的二叉树链表存储表示
2先遍历二叉树递归算法
6 .分层遍历二叉树的非递归算法
7 .求二叉树的深度
[说明]
1 .先输入二叉树中节点的值，用‘#’表示空树。 必须为每个节点确定其左右子树的值。 (如果为空，则必须使用特定的空字符作为占位符。 )执行此步骤时，必须首先在纸上绘制要创建的二叉树，并确定每个节点的左右子树。 如果为空，用特定的字符标记，先输入此二叉树的字符串。
2 .为了简化程序的写入量，提高程序的清晰性，对节点的访问用一个输出语句表示，如果有更复杂或更多的访问，可以将对节点的访问描述为函数，用函数指针进行函数的调用读者感兴趣的话，可以自己写。
3.c语言函数的参数传递都是“传价”方式，设计函数时要注意参数传递。 要在函数中更改实际参数的值，必须将指针变量用作参数。 具体设计时； 读者必须明确指针变量和指针变量所指的值等概念。
4 .完整的参考程序仅给出了部分遍历算法。 对于其他算法，请读者参考示例，自行编程完成，加深学习体验。 三叉链表的制作也是如此，在例子中只是展示了先后顺序法的制作过程，读者可以自行练习中顺序、后顺序二叉链表的制作方法、叶节点或二叉树节点总数的求法等。
第二部分二叉树的应用实验
---------rdrs树和rdrs代码
利用HuffMan编码器的通信极大地提高了信道利用率，缩短了信息传输时间，并且减少了传输成本。 然而，这要求：发送侧使用一个编码系统对传输数据进行预先编码，接收侧对传输数据的编码进行解码(复原)。 一些渠道要求每一端都有完整的编辑/解密系统。 让我们为这种信息收发站创建一个Huffman编辑/解密系统。 给出一组权重值{7、9、5、6、10、L、13、15、4、8}，构建赫夫曼树，计算权重路径长度WPL。
Huffman编码存在于磁盘文件中。 提出这些要求是给读者提高一定的思维空间和自己编程能力的机会。 读者需要注意用c类语言编写的算法转换为c源程序时函数参数的处理，以及其他变量的定义和使用方法。
2 .读者可参考该程序，实现Huffman编辑/解码系统的其他算法，进一步加深理解和体会。
心得体会
)通信领域的编码问题曾经是许多通信技术专家的难题，但直到后来人们对鞋楦数据结构有了一定的认识，才有效地解决了通信的编码需求。 这不仅缩短了通信代码的长度，更现实的意义是大大缩短了电文整体的长度，迅速提高了通信的效率。
)2)鞋楦数据结构不仅为各种实用问题找到了有效的解决途径，而且在编译原理过程中的编码问题等计算机科学技术本身的发展中也起到了非常重要的作用，提高了编译系统的速度。
实验3
二叉树的基本操作与应用实验
第三次实验主要包括两部分。 1 .二叉树基本操作实验； 2 .二叉树的应用——哈夫曼树和哈夫曼编码实验。 基本操作包括存储结构的构建和遍历算法。 本文仅提供了部分参考步骤。 请尽量完成很多基本操作。
第一部分基本操作实验
[问题描述]二叉树使用二叉树的链表作为存储结构，编程实现二叉树的以下基本操作
1 .先构建二叉树链表表示的二叉树t；
2 .对该二叉树进行扫描：先后顺序、中顺序、后顺序及分层扫描序列，分别输出节点的扫描序列；
3 .求解二叉树深度、节点数、叶节点数； [数据说明] //二叉树的二叉树链表存储表示
2先遍历二叉树递归算法
6 .分层遍历二叉树的非递归算法
7 .求二叉树的深度
[说明]
1 .先输入二叉树中节点的值，用‘#’表示空树。 必须为每个节点确定其左右子树的值。 (如果为空，则必须用特定的空字符占位。 )执行此步骤时，必须首先在纸上绘制要创建的二叉树，并确定每个节点的左右子树。 如果为空，用特定的字符标记，先输入此二叉树的字符串。
2 .为了简化程序的写入量，提高程序的清晰性，对节点的访问用一个输出语句表示，如果有更复杂或更多的访问，可以将对节点的访问描述为函数，用函数指针进行函数的调用读者感兴趣的话，可以自己写。
3.c语言函数的参数传递都是“传价”方式，设计函数时要注意参数传递。 要在函数中更改实际参数的值，必须将指针变量用作参数。 具体设计时； 读者必须明确指针变量和指针变量所指的值等概念。
4 .完整的参考程序只给出了部分遍历算法
其他算法，请读者参照示例，自行编程完成，以加深学习体会。对于二叉链表的建立也是如此，示例中只是给出了先序法建立过程，读者可自行练习中序、后序二叉链表建立法，叶子结点或二叉树结点总数求法等。第二部分 二叉树应用实验
---------rdrs树与rdrs编码
[问题描述] 利用HuffMan编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据编码进行译码(复原)。对于有些信道，每端都需要一个完整的编／译码系统。试为这样的信息收发站编写一个Huffman的编／译码系统。给定一组权值{7，9，5，6，10，l，13，15，4，8}．构造一棵赫夫曼树，并计算带权路径长度WPL。
Huffman编码存在磁盘文件中。提出这些要求，是给读者一定的思考空间和提高自己的编程能力的机会。读者需要注意类c语言描述的算法在转变为C源程序时关于函数参数的处理以及其他变量的定义与使用方法。
2．读者可参考此程序，实现Huffman编／译码系统的其他算法，以进一步加深理解和体会。
心得体会
(1)通信领域的编码问题曾经对许多的通信技术专家形成了困扰，后来人们对树型数据结构有了一定的认识之后，才有效地解决了通信的编码需求。它不仅使通信编码的长度缩短，更实际的意义是使整个电文的长度大大缩短了，从而迅速地提高了通信的效率。
(2)树型数据结构不仅使各类实际应用问题找到了一种有效解决途径，而且它也对计算机科学技术本身的发展起到了非常重要的作用，如在编译原理过程中的编码问题，使得编译系统提高了速度。
实验8 二叉树的基本操作
班级: 学号:
一、题目
由数字序列生成二叉树 假设我们有这样的二叉树：
节点的元素(key)是正整数，且互不相同。 可能给出这样一个虚拟的树更有利于理解输入。 是的，我们的输入是上图的先序遍历；
即,要求根据1 3 0 2 0 0 4 5 0 0 0这样的输入， 构造出一棵只含有正整数节点的二叉树。
【输入】
扩展的二叉树的先序遍历 【输出】
构造的简单树的节点个数 【样例输入】
1 3 0 2 0 0 4 5 0 0 0 【样例输出】
二、程序清单
三、程序调试过程中所出现的错误
四、运行结果(界面)：
五、心得体会
实验三
实验目的：
二叉树的建立及基本操作
本次实验的主要目的是熟练掌握二叉树的定义、三序(先序、中序、后序)遍历方法，并用遍历思想求解具体二叉树应用问题。通过程序实现，体会递归算法的优缺点。
实验要求：
用C语言编程实现二叉树的基本操作，并完成下述函数功能： (1) CreateBiTree( )：根据先序遍历序列生成一棵二叉树 (2) Depth( )：求此二叉树的深度
(3) CountLeaf( )：统计该二叉树中叶子结点的个数 (4) InOrderTraverse( )：中序遍历二叉树 (5) PostOrderTraverse( )：后序遍历二叉树
在主函数main( )中调用各个子函数完成单链表的基本操作。例： void main() { BiTree T; CreateBiTree (T); int d= Depth ( T ); printf(“深度为%d”, d); int num= CountLeaf ( T ); printf(“叶子结点个数为%d”, num); InOrderTraverse ( T ); PostOrderTraverse ( T ); } //注意函数调用时，只传递参数名称，不需要传递参数类型和&符号。
[实现提示] 采用特殊符号，如*号表示空树的情况。
通过输入扩展的先序序列建立一棵二叉树，即，二叉树中结点为空时应输入*符号表示。 [测试数据] 由学生自己确定，注意边界数据。
程序检查时，由老师提供用于建树的初始输入序列。
程序源码：(后付纸) 程序运行结果：
实验心得体会：
有一些概念不明白，看书之后弄懂了，仔细看了二叉树遍历的知识点，问了同学有了思路。熟悉了二叉树的基本操作，掌握了二叉树实现。
浙江大学城市学院实验报告
课程名称
数据结构基础
实验项目名称
实验十
二叉树的基本操作
实验成绩
迅速的火龙果(签名 )
日期
一. 实验目的和要求
1、掌握二叉树的链式存储结构。
2、掌握在二叉链表上的二叉树操作的实现原理与方法。
3、进一步掌握递归算法的设计方法。
二. 实验内容
1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。
二叉树二叉链表存储表示如下： struct BTreeNode {
ElemType data;
// 结点值域
BTreeNode *lchild , *rchild ; // 定义左右孩子指针 } ; 基本操作如下：
①void InitBTree( BTreeNode *&BT );
//初始化二叉树BT
②void CreateBTree( BTreeNode *&BT, char *a );
//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构
③int EmptyBTree( BTreeNode *BT);
//检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree( BTreeNode *BT); //求二叉树BT的深度并返回该值
⑤int FindBTree( BTreeNode *BT, ElemType x);
//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
⑥void PreOrder( BTreeNode *BT); //先序遍历二叉树BT ⑦void InOrder( BTreeNode *BT); //中序遍历二叉树BT ⑧void PostOrder( BTreeNode *BT);
//后序遍历发二叉树BT
⑨void PrintBTree( BTreeNode *BT );
//输出二叉树BT ⑩void ClearBTree( BTreeNode *&BT );
//清除二叉树BT
2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tree.h中，并在主函数文件test4_1.cpp中添加相应语句进行测试。 ①void LevelOrder( BTreeNode *BT ) //二叉树的层序遍历
②int Get_Sub_Depth( BTreeNode *T , ElemType x) //求二叉树中以元素值为x的结点为根的子树的深度
3、填写实验报告，实验报告文件取名为report10.doc。
4、上传实验报告文件report10.doc 、源程序文件test4_1.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。
三. 函数的功能说明及算法思路
(包括每个函数的功能说明，及一些重要函数的算法实现思路) 函数：void InitBTree( BTreeNode *&BT ) 功能：初始化二叉树BT 思路：将BT指向NULL
函数：void CBTree(BTreeNode *&BT ) 功能：输入二叉树
思路：按先序次序输入二叉树中结点的值(一个字符)特殊字符 $ 表示空树
函数：void PBTree(BTreeNode *BT,int n) 功能：横向打印二叉树
思路：先递归输出右子树，按层次输出空格和“---”控制格式，再输出当前结点值，最后递归左子树
函数：void CreateBTree( BTreeNode *&BT, char *a ) 功能：根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构
思路：根据广义表表示的”(”,”)”和”,”等字符来构建二叉树，用栈S来存储根结点指针，用p来接收当前结点值数据并链接为栈顶元素的左/右孩子
函数：int EmptyBTree( BTreeNode *BT) 功能：检查二叉树BT是否为空，空返回1，否则返回0 思路：返回判断BT是否指向NULL
函数：int DepthBTree( BTreeNode *BT) 功能：求二叉树BT的深度并返回该值
思路：若一棵二叉树为空，则它的深度为0，否则它的深度等于左子树和右子树中的最大深度加1
函数：int FindBTree( BTreeNode *BT, ElemType x) 功能：查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
思路：类似于前序遍历，若空树则返回0。若根结点值等于查找值x则返回1，否则先调用函数本身查找左子树，还未找到则再查找右子树，所有操作完成均为找到，则返回0
函数：void PreOrder( BTreeNode *BT) 功能：先序遍历二叉树BT 思路：使用“根左右”的顺序遍历二叉树
函数：void InOrder( BTreeNode *BT) 功能：中序遍历二叉树BT 思路：使用“左根右”的顺序遍历二叉树
函数：void PostOrder( BTreeNode *BT)
功能：后序遍历二叉树BT 思路：使用“左右根”的顺序遍历二叉树
函数：void PrintBTree( BTreeNode *BT )
功能：输出二叉树BT 思路：按照广义表表示方法输出二叉树(与输入时相同)
函数：void ClearBTree( BTreeNode *&BT )
功能：清除二叉树BT 思路：按照先子树后根结点的顺序删除二叉树
函数(选作)：void LevelOrder( BTreeNode *BT ) 功能：二叉树的层序遍历
思路：初始化一个空队列，若二叉树为空，则空操作；否则，树根指针入队列。当队列非空时循环：出队首元素，并输出该元素(指针)所指结点的值；且若该结点存在左右孩子，则左右孩子指针进队列。输出结果就是层序遍历序列
函数(选作)：求二叉树中以元素值为x的结点为根的子树的深度 功能：int Get_Sub_Depth( BTreeNode *T , ElemType x) 思路：在FindBTree函数的基础上修改，将找到结点时的返回值改为调用DepthBTree求出以该结点为根结点的子树深度即可
四. 实验结果与分析
(包括运行结果截图、结果分析等)
测试数据：a(b(c),d(e(f,g),h(,i)))，abc$$$def$$g$$h$i$$ 结果分析：针对该二叉树，程序输出深度为4，正确；查找值f能够找到，正确；先序遍历结果为a b c d e f g h i，正确；中序遍历结果为c b a f e g d h i，正确；后续遍历结果为c b f g e I h d a，正确；输出二叉树的结果与输入一致，正确；使用先序输入二叉树和横向输出部分正确。选作部分，层序遍历结果为a b d c e h f g i，正确；以结点d为根结点的子树深度为3，正确。
五. 心得体会
(记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。)
【附录----源程序】