第六章 树
一、求二叉树上结点的路径
1.题目要求：
求二叉树上结点的路径及二叉树的三种非递归遍历。该设计要求在采用链式存储结构存储的二叉树上，以bt指向根结点，p指向任一给定的结点，编程实现在建立的二叉树上完成的三种非递归遍历并求出从根结点到给定结点之间的路径。 2.算法分析：
分析：我们知道，在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求，但采用后序遍历二叉树是可行的。因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此我们可非递归地后序遍历二叉树bt，当后序遍历访问到结点*p时，此时栈stack中存放的所有结点均为给定结点*p的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。
在这个设计题目中可以在主函数中用菜单调用的方式实现二叉树的非递归遍历。 为了实现上述的设计要求，首先要定义二叉树的链式存储结构，通常采用的方法是：每个结点中设置三个域，即值域，左指针域，和右指针域。用data表示值域，lchild和rchild分别表示指向左右子树（孩子）的指针域。相应的类型说明为： typedef struct node{ DataType data;
Struct node *lchild, * rchild }BinTNode;
typedef BinTNode *BinTree
要实现二叉树的遍历，就需要建立二叉树，因此，还需要编写建立二叉树的算法。
二、二叉树的综合操作
1.题目要求：
要求对二叉树实现下列操作： 1.构造二叉链表树； 2.二叉树的前序遍历； 3.二叉树的中序遍历； 4.二叉树的后序遍历； 5.二叉树的层次遍历； 6.用广义表表示二叉树； 7.用凹入表表示二叉树； 8.求结点总数。 9.查找结点； 2.算法分析：
采用递归算法，实现二叉树的相关操作。
三、赫夫曼编码
1.题目要求：
在信息时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已经越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。本设计要求是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行编译，输出电文字符串。 2.算法分析：
数据描述：
typedef struct{ char ch;
char bits[n]; int len; }CodeNode;
typedef CodeNode HuffmanCode[n+1]; typedef struct{
int weight; /* 权值 */
int lchild,rchild,parent; /* 左右孩子及双亲指针 */ }HTNode; /* 树中结点类型 */
typedef HTNode HuffmanTree[m+1];/* 0号单元不用 */ int num; 算法描述：
1.初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。
2.编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。
3.译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。 4.打印 Huffman树。
四、烟花的寿命 1.题目要求：
见过夜空中美丽的烟花吗？它们总是由一块炸成多块，可能还会继续分裂成更小的块，然而并不是每块都会继续发光。如果把一个烟花炸开的整个过程中的亮点记录下来，并给所有的爆炸点标上号，你能算出它最长可能的存活时间吗？（指第一次爆炸到最后一次之间间隔的时间，假设任意两次相邻的爆炸时间间隔都是1秒）。
要求：
① 输入格式：
第一行输入一个数T，说明输入文件中共T组数据。每组的第一行是爆炸的总数N（1 行隔开。 ② 输出格式 对每组输入，输出若干行。第一行是最长的时间X秒，接着输出x+1个数，给出最长时间是怎么到达的，（从哪个点开始，经过哪些点）。如果存在多解，则任意输出一组解。 2.算法分析： 烟花的一点可以炸成多个点，爆炸点的前驱，后继十分明显，恰好是一对多的关系，可以抽象为树的数据结构。可以用静态链表来构建树，用双亲表示法表示树。题目要求的最长存活时间，即是求从树的根结点到叶子结点的最长路径。可以求出所有路径，然后输出最长路径。由于树用双亲表示法，结点寻找双亲容易。所以寻找路径从根结点开始，逐步寻找双亲，并用栈存储结点信息，最后出栈，即为根结点到叶子结点的路径信息。对于求最长路径，可以将栈存到一个数组中，只出元素最多的栈。 数据的组织形式： 每一组输入数据包括：爆炸的总点数以及爆炸点的前驱、后继信息。输入爆炸点的邻接关系时，以前驱->后继的格式输入，结点是从0开始的整数。 数据类型定义： #define MAX 100 //宏定义最大的爆炸点数 typedef struct ptNode //用静态链表来存储树，双亲表示法 { int data; //数据域 int point; //指针域 int deg; //记录树上的度 }ptNode; //定义一个结点 typedef struct { ptNode list[MAX]; //结点数组 int num; //list中元素的个数 }SLinkList; //定义一棵树 typedef struct //定义一个栈,用以保存树的路径信息 { int stack[MAX]; int top; }SeqStack; SLinkList S1; //定义静态链表 SeqStack S[MAX]; //定义栈的数组 数据存储结构： 栈以顺序结构实现，静态链表用树的双亲表示法实现树的前驱后继逻辑关系。
