软件设计师 http://www.educity.cn/jiaocheng/zg7.html
的二叉树，其中有n+1个空指针域，它们可以被用来存放\线索\增加了线索的二叉树称为线索树（穿线树）。
设有一棵采用标准形式存储的二叉树BT,对于BT中的每个结点k,如它没有左（或右）子结点，而k1是k的按中序遍历的前面（或后面）结点，则置结点k的左（或右）指针为k1结点的指针。为了与k结点的真正子结点指针区别，另需在结点上增加两个标志域ltag和rtag.如此改造后的线索树的结点类型定义如下： typedef stuct BTnode{ / *穿线树结点类型 * / char data;
struct node *lchild,*rchild; int 1tag,rtag; }BTNODE;
当ltag=0时，表示lchild指针指向其左孩子结点；当ltag=1时，表示lchild指针指向其前驱结点。当rtag=0时，表示rchild指针指向其右孩子结点；当rtag=1时，表示rchild指针指向其后继结点。
1.2.6 最优二叉树
树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。在一些应用中，赋予树中结点的一个有某种意义的实数，这些数字称为结点的权。结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度。树中所有叶结点的带权路径长度之和，称为树的带权路径长度（树的代价），通常记为：
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
其中n表示叶子结点的数目，wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。
在权值为w1,w2,…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或哈夫曼树。
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为w1,w2,…，wn,则哈夫曼树的构造规则为：
①将w1,w2,…，wn看成是有n棵树的森林（每棵树仅有一个结点）；
②在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； ③从森林中删除选取两棵树，并将新树加入森林；
④重复第②和③步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。 例如如果叶子结点的权值分别为1,2,3,4,5,6,则构造哈夫曼树的过程如图1-10所示。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
图1-10 哈夫曼树的构造过程
在构造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心算法。
给定结点序列
将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码。
给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是依次以叶子结点C[i]（0≤i≤n–1）为出发点，向上回溯至根为止。上溯时走左分支则生成代码0,走右分支则生成代码1.需要注意以下几个问题。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时串中，并设一个指针start指示编码在该串中的起始位置（start初始时指示串的结束位置）。 当某字符编码完成时，从临时串的start处将编码复制到该字符相应的位串bits中即可。 因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符\的大小应为n+1.
给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。
平均码长 =
其中pi为第i个字符的概率，li为码长。
利用哈夫曼树很容易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉20%至90%,其压缩效率取决于被压缩文件的特征。
1.3 图
在线性结构（例如队列和栈）中，除第一个结点没有前驱，最后一个结点没有后继之外，每一个结点都有唯一的一个前驱和后继。在树形结构（例如树和二叉树）中，除根结点没有前驱外，一个结点只有一个前驱结点，但可以有若干个后继。在图结构中，一个结点的前驱和后继的个数都是任意的。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
1.3.1 图的基础知识
1.图的基本概念
图G由两个集合V和E组成，记为G=（V,E），其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集合。通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集。若E（G）为空，则图G只有顶点而没有边。
图分为有向图和无向图两种。如图1-10（a）所示是一个有向图，在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。
如图1-10（b）所示是一个无向图，无向图中的边均是顶点的无序对，无序对通常用圆括号表示。在无向图G中，如果i≠j,i、j∈V,（i,j）∈E,即i和j是G的两个不同的顶点，（i,j）是G中一条边，顶点i和顶点j是相邻的顶点，边（i,j）是与顶点i和j相关联的边。
如果限定任何一条边或弧的两个顶点都不相同，则有n个顶点的无向图最多有n（n–1）/2条边，这样的无向图称为无向完全图。一个有向图最多有n（n–1）条弧，这样的有向图称为有向完全图。
如果同为无向图或同为有向图的两个图G1=（V1,E1）和G2=（V2,E2），满足V2