《山东广播电视大学开放教育数据结构复习第四分》由会员分享，可在线阅读，更多相关《山东广播电视大学开放教育数据结构复习第四分（11页珍藏版）》请在金锄头文库上搜索。
1、山东广播电视大学开放教育数据结构复习第四部分 作者： 日期：2 山东广播电视大学开放教育数据结构期末复习指导 树是一种重要的非线性结构，从逻辑角度看，其数据元素之间体现的是一对多的非线性关系，一切具有层次关系的问题都可以用树来描述。一、相关术语 树、二叉树、树根、子树、有序树、无序数、森林、终端结点（叶子）、非终端结点、结点的度、结点的层次、树的深度、满二叉树、完全二叉树、理想二叉树、孩子、双亲、左孩子、右孩子、先序遍历、中序遍历、后序遍历、层次遍历、哈夫曼树、最优二叉树、路径、路径长度、权、带权路径长度、哈夫曼编码。二、树的概念树的定义 树的递归定义： 树(Tree)是n(n0)个结点的有限
2、集T，T为空时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m0)个互不相交的子集Tl，T2，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。注意： 树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。三、二叉树的定义二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。（1）二叉树与无序树不同 二叉树中，每个结点最多只能有两棵子树，并且
3、有左右之分。 二叉树并非是树的特殊情形，它们是两种不同的数据结构。 （2）二叉树与度数为2的有序树不同 在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。四、二叉树的存储结构（一）顺序存储结构 该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。1完全二叉树结点编号（1） 编号办法 在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。【例】如下图所示。（2）
4、编号特点 完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是ki(1in)，则有：若i1，则ki的双亲编号为i/2；若i=1，则Ki是根结点，无双亲。若2in，则Ki的左孩子的编号是2i；否则，Ki无左孩子，即Ki必定是叶子。因此完全二叉树中编号in/2的结点必定是叶结点。若2i+1n，则Ki的右孩子的编号是2i+1；否则，Ki无右孩子。若i为奇数且不为1，则Ki的左兄弟的编号是i-1；否则，Ki无左兄弟。若i为偶数且小于n，则Ki的右兄弟的编号是i+1；否则，Ki无右兄弟
5、。2完全二叉树的顺序存储 将完全二叉树中所有结点按编号顺序依次存储在一个向量bt0.n中。 其中： bt1n用来存储结点 bt0不用或用来存储结点数目。【例】下表是上图的完全二叉树的顺序存储结构，bt0为结点数目，b7的双亲、左右孩子分别是bt3、btl4和bt15。3一般二叉树的顺序存储（1） 具体方法 将一般二叉树添上一些 虚结点，成为完全二叉树 为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号 将结点按编号存入向量对应分量，其中虚结点用表示【例】上图中单支树的顺序存储结构如下图（2） 优点和缺点 对完全二叉树而言，顺序存储结构既简单又节省存储空间。 一般的
6、二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。【例】最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间。在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。4二叉树的顺序存储结构类型定义 【参见教材】（二）链式存储结构 1结点的结构 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构为：2结点的类型说明 typedef char DataType； /*用户可根据具体应用定义DataType的实际类型*/ typede
7、f struct node DataType data； Struct node *lchild，*rchild； /*左右孩子指针*/ BinTNode； /*结点类型*/ typedef BinTNode *BinTree；/*BinTree为指向BinTNode类型结点的指针类型*/3二叉链表（二叉树的常用链式存储结构） 在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root，就构成了二叉树的链式存储结构，并将其称为二叉链表。（示例参见教材）注意： 一个二叉链表由根指针root惟一确定。若二叉树为空，则root=N
8、ULL；若结点的某个孩子不存在，则相应的指针为空。 具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。4带双亲指针的二叉链表 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。注意：二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。五、二叉树的遍历ACFEDB（一） 中序序列 中序遍历二叉树时，对结点的访问次序为中序序列 【例】中序遍历上图所示的二叉树时，得到的中序序列为： 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的分支结点。下面对教材中的哈夫曼编码加以补充，以帮助同学们理解。（一）编码方案1.编码和解码 数据压缩过程称为编码。即将文件中的每个字符均转换为一个惟一的二进制位串。 数据解压过程称为解码。即将二
11、进制位串转换为对应的字符。2等长编码方案和变长编码方案 给定的字符集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、)见表。 字符编码问题 - 字符 a b c d e f 频度（单位：千次） 45 13 12 16 9 5 定长编码 000 001 010 011 100 101 变长编码 0 101 100 111 1101 1100 - 根据计算公式： (45*1+13*3+12*3+16*3+9*4+584)*1000=224000整个文件被编码为224000位，比定长编码方式节约了约25的存储空间。 注意： 变长编码可能使解码产生二义性。产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同。 【例】设E、T、W分别编码为00、01、0001，则解码时无法确定信息串0001是ET还是W。3 前缀码方案 对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。 注意： 等长编码是前缀码4最优前缀码平均码长或文件总长最小的前缀编码称为最优的前缀码。最优的前缀码对文件的压缩效果亦最佳。 其中：
