数据结构辅导2

1、第6章树和二叉树树是一种重要的非线性结构，从逻辑角度看，其数据元素之间体现的是一对多的非线性 关系，一切具有层次关系的问题都可以用树来描述。一、相关术语树、二叉树、树根、子树、有序树、无序数、森林、终端结点(叶子)、非终端结点、 结点的度、结点的层次、树的深度、满二叉树、完全二叉树、理想二叉树、孩子、双亲、左 孩子、右孩子、先序遍历、中序遍历、后序遍历、层次遍历、哈夫曼树、最优二叉树、路径、 路径长度、权、带权路径长度、哈夫曼编码。二、树的概念树的定义树的递归定义：树(Tree)是n(nG)个结点的有限集T, T为空时称为空树，否则它满足如下两个条 件：有且仅有一个特定的称为根(Root)的结

2、点；其余的结点可分为m(mAG)个互不相交的子集TT2，T其中每个子集本身又是一棵树，并称其为根的子树(Subree)。注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由 若干棵更小的子树构成。三、二叉树的定义二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的 形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简 单，因此二叉树显得特别重要。二叉树与无序树不同二叉树中，每个结点最多只能有两棵子树，并且有左右之分。二叉树并非是树的特殊情形，它们是两种不同的数据结构。二叉树与度数为2的有序树不同在有序树中，虽然一

3、个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子， 就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。四、二叉树的存储结构顺序存储结构该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。结点 在这个序列中的相互位置还能反映出结点之间的逻辑关系。完全二叉树结点编号(1)编号办法在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有 结点编号，能得到一个反映整个二叉树结构的线性序列。【例】如下图所示。结烦端扑的完全:叉树(2)编号特点完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层 结点个数的2倍。从一个结点的

4、编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假 设编号为i的结点是kj(1WiWn)，则有：若i1，则ki的双亲编号为i/2；若i=1，则Ki是根结点，无双亲。若2iWn，则Ki的左孩子的编号是2i；否则，K；无左孩子，即必定是叶子。因此完全二叉树中编号in/2的结点必定是叶结点。11若2i+1Wn，则Ki的右孩子的编号是2i+1 ；否则，Ki无右孩子。若i为奇数且不为1，则Ki的左兄弟的编号是i-1；否则，Ki无左兄弟。若i为偶数且小于n，则K：的右兄弟的编号是i+1；否则，K：无右兄弟。完全二叉树的顺序存储将完全二叉树中所有结点按编号顺序依次存储在一个向量bt0.n中。其中：bt1.

5、 n用来存储结点bt0不用或用来存储结点数目。【例】下表是上图的完全二叉树的顺序存储结构，bt0为结点数目，b7的双亲、左右 孩子分别是 bt3、btl4和 bt15。卜标 U I Z 3 = 6 7 村叫 1口 11 12 1% l-l I” W I7ABCDErGiiJKLN（.）PQ一般二叉树的顺序存储(1)具体方法将一般二叉树添上一些虚结点，成为完全二叉树为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给 结点编号将结点按编号存入向量对应分量，其中虚结点用季表示【例】上图中单支树的顺序存储结构如下图卜标12 H 1；5 E 了3A*B44C（2）优点和缺点对完全二

6、叉树而言，顺序存储结构既简单又节省存储空间。一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。【例】最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存 储空间。在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。二叉树的顺序存储结构类型定义【参见教材】（二）链式存储结构结点的结构二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点 本身的数据外，还应设置两个指针域Ichild和rchild，分别指向该结点的左孩子和右孩子。 结点的结构为：Ichildda taichiId结点的类型说明typedef char DataTyp

7、e； /*用户可根据具体应用定义DataType的实际类型*/typedef struct nodeDataType data；Struct node *lchild，*rchild； /*左右孩子指针*/BinTNode； /* 结点类型*/typedef BinTNode *BinTree； /*BinTree 为指向 BinTNode 类型结点的指针类型*/二叉链表（二叉树的常用链式存储结构）在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点（即根结点） 的BinTree型头指针（即根指针）root，就构成了二叉树的链式存储结构，并将其称为二叉链 表。（示例参见教材

8、）注意：一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL；若结点的某 个孩子不存在，则相应的指针为空。具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、 右孩子，其余的n+1个指针域为空。带双亲指针的二叉链表经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针 parent，形成一个带双亲指针的二叉链表。注意：二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。五、二叉树的遍历（一）中序序列中序遍历二叉树时，对结点的访问次序为中序序列【例】中序遍历上图所示的二叉树时，得到的中序序列为:D B A E C F（二）先

9、序序列先序遍历二叉树时，对结点的访问次序为先序序列【例】先序遍历上图所示的二叉树时，得到的先序序列为:A B D C E F（三）后序序列后序遍历二叉树时，对结点的访问次序为后序序列【例】后序遍历上图所示的二叉树时，得到的后序序列为： D B E F C A注意：（1）在搜索路线中，若访问结点均是第一次经过结点时进行的，则是先序遍历；若访 问结点均是在第二次（或第三次）经过结点时进行的，则是中序遍历（或后序遍历）。只要将搜 索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的先 序序列、中序序列和后序序列。（2）上述三种序列都是线性序列，有且仅有一个开始结点和一个终端

10、结点，其余结点 都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋（即双亲）结点和后继 （即孩子）结点的概念，对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历次序 名称。六、哈夫曼树用哈夫曼算法构造哈夫曼树的要注意以下问题。初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树 中共有2n-1个结点。哈夫曼树是严格的二叉树，没有度数为1的分支结点。下面对教材中的哈夫曼编码加以补充，以帮助同学们理解。（一）编码方案编码和解码数据压缩过程称为编码。即将文件中的每个字符均转换为一个惟一的二进

11、制位串。数据解压过程称为解码。即将二进制位串转换为对应的字符。等长编码方案和变长编码方案给定的字符集C，可能存在多种编码方案。（1）等长编码方案等长编码方案将给定字符集C中每个字符的码长定为lg|C|，|C|表示字符集的大小。【例】设待压缩的数据文件共有100000个字符，这些字符均取自字符集C=a，b，c， d，e，f，等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为 300000 位。（2）变长编码方案变长编码方案将频度高的字符编码设置短，将频度低的字符编码设置较长。【例】设待压缩的数据文件共有100000个字符，这些字符均取自字符集C=a，b，c， d，e，f，其中每

12、个字符在文件中出现的次数（简称频度）见表。字符编码问题字符abcdef频度（单位：千次）4513121695定长编码000001010011100101变长编码010110011111011100根据计算公式：（45*1+13*3+12*3+16*3+9*4+584）*1000=224000整个文件被编码为224000位，比定长编码方式节约了约25%的存储空间。注意：变长编码可能使解码产生二义性。产生该问题的原因是某些字符的编码可能与其他字符 的编码开始部分（称为前缀）相同。【例】设E、T、W分别编码为00、01、0001，则解码时无法确定信息串0001是ET还 是W。前缀码方案对字符集进行编

13、码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这 种编码称为前缀（编）码。注意：等长编码是前缀码最优前缀码平均码长或文件总长最小的前缀编码称为最优的前缀码。最优的前缀码对文件的压缩效 果亦最佳。平均码长=旗讪2=1其中：Pj为第i个字符得概率，为码长【例】若将表6.5所示的文件作为统计的样本，则a至f六个字符的概率分别为0.45, 0.13, 0.12, 0.16, 0.09, 0.05,对变长编码求得的平均码长为2.24，优于定长编码（平均 码长为3）。（二）根据哈夫曼树构造哈夫曼编码利用哈夫曼树很容易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码 正是一种应用广

14、泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20%至 90%，其压缩效率取决于被压缩文件的特征。具体做法（1）用字符c.作为叶子，p.或f.做为叶子c.的权，构造一棵哈夫曼树，并将树中左分 支和右分支分别标记为0和1；（2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即 为最优前缀码（也称哈夫曼编码）。哈夫曼编码为最优前缀码由哈夫曼树求得编码为最优前缀码的原因：每个叶子字符c.的码长恰为从根到该叶子的路径长度1.，平均码长（或文件总长）又 是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小的二叉树，因此编码的平均码长（或 文件总长）亦最小。树中没有一片叶

15、子是另一叶子的祖先，每片叶子对应的编码就不可能是其它叶子编 码的前缀。即上述编码是二进制的前缀码。求哈夫曼编码的算法（1）思想方法给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子 Ti（0WiWn-1）为出发点，向上回溯至根为止。上溯时走左分支则生成代码0,走右分支 则生成代码1。注意：由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时 向量中，并设一个指针start指示编码在该向量中的起始位置（start初始时指示向量的结 束位置）。当某字符编码完成时，从临时向量的start处将编码复制到该字符相应的位串b.ts 中即可。因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符0 , b.ts 的大小应为n+1。（2）字符集编码的存储结构及其算法描述typedef struct char ch； /*存储字符*/char bitsn+1 ； /*存放编码位串*/CodeNode；typedef CodeNode HuffmanCoden；void CharSetHuffmanEncoding(HuffmanTree T，