数据结构第五章-21.ppt

1、5.5 线 索 树,对二叉树进行某种遍历，可以得到一个线性有序的序列。 例如对某二叉树的中序遍历结果: K,D,H,B,G,E,A,X,M,C,F 该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。,想得到一个结点的前驱或后继结点，每次总是从根开始遍历。 无论是采用递归方式，还是非递归方式，遍历算法中一定包含着堆栈空间。,2.线索的方法存储结构,中序遍历: A的前驱是， B的前驱是; E的前驱是； D的前驱是；,一个结点N如果有左子树，则该结点的前驱就是其左子树中最右的子孙P。 这个子孙结点的右链接域一定为空。,E H G K,中序遍历: H的前驱是D， G的前驱是B; X的前驱是A,一个

2、结点N如果没有左子树，则该结点的前驱就是其所有祖先中,最接近它的“右倾”祖先P。 这个结点N的左链接域本身就是空 。,思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？ 我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。,用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。,这就是线索二叉树（Threaded Binary Tree）,线索二叉树的实现,规 定：,1）若结点有左子树，则Lchild指向其左孩子； 否则，Lchild指向其直接前驱(即线索)；,2）若结点有右子树，则Rchild指向其右孩子； 否则，Rchild指向其直接后

3、继(即线索) 。,如何区别？,约定:,当flag域为0时,表示正常情况;,当flag域为1时,表示线索情况.,前驱(后继),左(右)孩子,为区别两种不同情况，特增加两个标志域：,图5.5.5 中序线索树,D, B, E, A, C, F,NULL,NULL,有关线索二叉树的几个术语：,线索链表： 线 索： 线索二叉树： 线 索 化：,用含flag的结点样式所构成的二叉链表 指向结点前驱和后继的指针 加上线索的二叉树 对二叉树以某种次序遍历使其变为线索二叉树的过程,线索化过程就是在遍历过程中修改空指针的过程： 将空的Lchild改为结点的直接前驱； 将空的Rchild改为结点的直接后继。 非空指

4、针呢？仍然指向孩子结点（称为“正常情况”）,例：【考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。,解:因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线。,二叉线索树的结点结构定义,typedef struct EType data; BinaryTreeNode*LChild; boolLflag; BinaryTreeNode*RChild; boolRflag; BinaryTreeNode；,二叉线索树的遍历,二叉线索树的各种遍历规则仍是原来的规则，不同的是，由于有了线索，所以在遍历时，将利用线索去追踪后

5、继结点，而不再利用堆栈方式或递归方式使用额外的栈空间。 在遍历时，只需要后继线索就可以了，所以，右线索相对更重要。 后序线索树不同与前序和中序线索树,前序二叉线索树的遍历,void ThreadPreOrder(BinaryTreeNode *BT) /前序二叉线索树的遍历 BinaryTreeNode *p=BT; while (p) cout data Lflag) p = p -LChild; else p = p-RChild; ,中序二叉线索树的遍历InOrderThread,中序二叉线索树的遍历思想是： 从当前结点指针开始，查找以该结点为根的子孙中最左子孙（向左查找）； 访问该结点

6、； 将指针指向被访问结点的右链接域所指的结点。如果被访问结点的右链接域是后继（Rflag为true），则转B步骤；否则，是一个右子树的根，则转A步骤；,BinaryTreeNode*p=BT; bool flag; while ( !p ) while (!p -Lflag) /查找一棵子树的最左子孙 p = p - LChild; flag=true; while (flag ,二叉树转化为二叉线索树,二叉树转化为中序二叉线索树 P:当前访问结点， q:指向其前驱结点。 另设一个堆栈，以非递归方式遍历二叉树。算法结束的条件是堆栈和p同时为空。 B)“走过”p左子树上的所有结点，直到左子树为空

7、。如果某结点无左孩子，则将该结点的左链接域的指针作为线索指向其前驱q，并将q指向这个无左孩子的结点；转C步骤。 C)退栈，直到找到下一个可以“访问”的结点，并用p指向该结点；如果p的前驱（q指向）的右链接域为空，则将q的右链接域作为线索指向p。转B步骤。,3。中序二叉树线索树中结点的插入,将一个由T指针指向的新结点插入到二叉线索树中，作为S所指的结点左孩子或S所指的结点右孩子。 如果S原来已经存在左子树（或右子树），就将原来的左子树（或右子树）作为新结点T的左孩子（或右孩子）。 线索树的插入问题中，将S结点与T结点链接在一起是件简单的事情，关键问题是要改变各结点的线索和对应的线索标志。,中序线

8、索树中插入的新结点T作为S的左孩子,If:S结点无左孩子 新结点T的各值的变化： T-RChild = S； T-LChild = S-LChild。 链接域标志的变化： T-Lflag = 1；T-Rflag = 1 S结点各个值的变化 S-LChild = T； S-Lflag = 0或false。,If:S结点有左孩子 /找S左子树中的最右子孙 q = T- LChild; while (!q- Rflag) q = q- RChild; q- RChild =T;,5.6 一般树的表示和遍历,typedef struct TreeNodeEType data; TreeNode*son

9、; TreeNode*next; TreeNode；,树和森林与二叉树的转换,转换步骤： step1: 将树中同一结点的兄弟相连;,加线,抹线,旋转,树如何转为二叉树？,孩子兄弟表示法,step2: 保留结点的最左孩子连线，删除其它孩子连线；,step3: 将同一孩子的连线绕左孩子旋转45度角。,方法：加线抹线旋转,树转二叉树举例：,兄弟相连,长兄为父,孩子靠左,特点是根结点没有右孩子！,二叉树怎样还原为树？,要点：逆操作，把所有右孩子变为兄弟！,5.6.2 二叉树、一般树及森林的关系,兄弟相连 长兄为父 头树为根 孩子靠左,A,二叉树如何还原为森林？,要点：把最右边的子树变为森林，其余右子树

10、变为兄弟,5.6.3 一般树的遍历概念,树的遍历:,例如：,前序序列：,后序序列：,a b c d e,b d c e a,前序 、后序,前序遍历 访问根结点； 依次前序遍历根结点的每棵子树。,后序遍历 依次后序遍历根结点的每棵子树； 访问根结点。,树没有中序遍历,树若采用“先转换，后遍历”方式，结果是否一样？,d e c b a,a b c d e,b d c e a,1. 树的先序遍历与二叉树的先序遍历相同； 2. 树的后序遍历相当于二叉树的中序遍历；,结论：,树的先序序列：a b c d e 树的后序序列：b d c e a,5.6.4 一般树的运算,一般树以二叉树形式存储时，一般树的大

11、部分的运算可以用二叉树的算法来实现，如一般树的前序遍历、后序遍历、结点的个数等。 一般树二叉树形式存储下结点的度。 一般树二叉树形式存储下层次遍历,2。一般树二叉树形式存储下层次遍历,void TreeLevelOrder (TreeNode *T) /求按层次遍历一般树 Queue Q; Enqueue( ,typedef struct TreeNodeEType data; TreeNode*son; TreeNode*next; TreeNode；,树的应用一（族谱）,树的应用二：利用树型结构的搜索算法模拟因特网域名的查询,5.7.1 分类二叉树,分类二叉树又可以称为二叉排序树或二叉搜索

12、树。 在大量数据的处理中，为了便于数据查找，对输入的数据采用分类二叉树的方式存储，从而可以大大提高查找的效率，其时间效率是O(nlog2n)。 按中序遍历一棵分类二叉树，其结果是一个按某一特征值（关键字）排序的线性序列。,定义：,设key1, key2, keyn是一个数据集合中数据元素的对应关键字，按下列原则建立的二叉树称为分类二叉树。 (1)每个元素有一个关键字，并且没有任意两个元素有相同的关键字。 (2)根结点的左子树的关键字（如果存在）小于根结点的关键字。 (3)根结点的右子树的关键字（如果存在）大于根结点的关键字。 (4)根结点的左右子树也都是分类二叉树。,数据集合的关键字：15，2

13、3，12，8，13，9，25，21，18,如何使中序遍历的结果按关键字降序排列呢？,15，23，12，8，13，9，25，21，18,2 分类二叉树运算1）分类二叉树中数据元素的查找,while (p) if (SearchKey data.key) p = p-LChild; else if (SearchKey p-data.key) p = p-RChild; else x = p-data; return true; ,2。将结点插入到分类二叉树中,插入算法与查找算法的一个显著区别是： 查找中，如果找到，则成功。 在插入时也要查找，是当查找失败时，说明找到了插入点； 查找成功时，说明有

14、相同的数据元素出现，这在分类二叉树中是不允许的，即插入失败。,while (p) parent = p; if (x.key data.key) p = p-LChild; else if (x.key p-data.key) p = p-RChild; else return false;/重复出现，即相等值结点出现 ,/ 找到插入点，为x申请一个空间填入其值，并将该结点连接至 parent,BinaryTreeNode *q = new BinaryTreeNode; q -data = x; If (BT)/ 原树非空 if (x.key data.key) parent -LChild

15、 = q; else parent -RChild = q; else / 插入到空树中 BT = q; return true; ,删除分类二叉树中的结点,删除结点x的三种情况： x是叶子结点； x只有一个非空子树； x有两个非空子树,堆排序,1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德(Robert WFloyd)和威廉姆斯(JWilliams)在1964年共同发明了著名的堆排序算法( Heap Sort ),1 堆树的定义,最大树：所谓最大树就是每个结点的值都大于或等于其子结点（如果存在）值。 最小树：所谓最小树就是每个结点的值都小于或等于其子结点（如果存在）值

16、。 堆树简称为堆，是一棵二叉树。堆有如下特征： 如果一棵顺序二叉树本身又满足最大树的条件，则这棵顺序二叉树就是最大堆； 如果一棵顺序二叉树本身又满足最小树的条件，则这棵顺序二叉树就是最小堆。,一般树 ，最大树,二叉树 ，最小树,顺序二叉树 最大堆,？,2 堆树的意义,顺序二叉树的高度最小，具有n个结点的顺序二叉树的高度是log2n。如果在这棵树中按分枝查找，搜索的次数可以达到最少； 顺序二叉树以顺序存储方式存储时，空间不会造成浪费，节省了动态存储方式下链接域的空间耗费。 利用数组下标，可以用公式来表达顺序二叉树中各结点之间的逻辑关系。,堆排序-数据排序的一种经典方法,先将堆顶元素（最大结点）移

17、到结果数据存储空间，再从堆中余下的结点（左子树或右子树）中选出一个最大结点，移到堆顶，即将堆中余下的结点重新“调整”为一个新堆. 将堆顶结点移到结果数据存储空间的下一个空间位置，如此下去，直到所有的结点都被移到结果数据存储空间。,如何构造一个初始堆树? 有了初始堆，在排序时，当移走根结点时，对余下的树又如何再“调整”为一棵新堆?,移去该结点？,1.初始化一个非空的最大堆,一个顺序二叉树以顺序存储方式存储时，就是连续地存储在数组元素空间中. 第一个元素位置存放的是顺序二叉树的根结点， 最后一个数组元素位置存放的是顺序二叉树中最下面一层中最右的结点。,每个数据在逻辑上关联的数据不一定是接下来的数组

18、空间中的数据. i:左孩子2*i;右孩子2*i+1,临时存放数据元素,24,5,堆：比较交换结点i，2*i及2*i+1,构造初始堆,首先将所有的叶子结点（最底层结点）看成为若干个子堆(只有一个结点) N的子树已经是子堆，则新的根结点是N和它的子树（一个或两个）根结点的值中最大的结点值。,构造N所指结点为根的堆算法思想：,A.先将N所指结点的值复制到一个工作空间中临时存放。 B.再将N所指结点的孩子中，值较大的与工作空间中的值比较： 1) 如果工作空间中值更大，新堆已经形成，就将工作空间中的值存放到N所指的位置，结束。 2）如果某个孩子的结点值更大，则将这个值存放到这个孩子双亲的结点位置，即N位

19、置。此时，工作空间中的结点还未找到存放位置，再将上移的孩子结点位置作为N所指的新位置，转到B步骤。,for (int i = HeapSize/2; i = 1; i-) /从最后一个结点的根开始，直到第一个结点 1)i= HeapSize/2=10/2=5，heap5=72 2)i- -;i=5 ; heap4=53 .,1,2,3,4,5,6,7,8,9,10,0,最大堆调整(1),最大堆调整(2),初始化一个非空的最大堆算法,for (int i = HeapSize/2; i = 1; i-) /从最后一个结点的根开始，直到第一个结点 heap0 = heapi; / 将i结点值复制到

20、工作空间heap0中 int son = 2*i;/ son的双亲结点是heap0的目标位置， / son首先指向i的左孩子,while (son = heapson) / 大孩子再与工作空间中结点值再比较 break; /工作空间中值大，找到heap0的目标位置 heapson /2 = heapson; / 将大孩子上移至双亲位置 son * = 2;/ son下移一层到上移的结点（大孩子）位置 heapson /2 = heap0;/heap0存放到目标位置,4.堆排序,不必再开辟另一个结果存储区，只要将删除的堆顶结点存放到当前堆的最后一个叶子结点空间中就可以。,49,25,25*,21

21、,16,08,0,1,2,3,4,5,08,25,25*,16,21,49,0,2,5,4,3,1,49 25 21 25* 16 08,08 25 21 25* 16 49,交换 0 号与 5 号对象, 5 号对象就位,初始最大堆,基于初始堆进行堆排序,08 16 21 25* 25 49,25,25*,08,21,16,49,0,1,2,3,4,5,16,25*,08,25,21,49,0,2,5,4,3,1,25 25* 21 08 16 49,16 25* 21 08 25 49,交换 0 号与 4 号对象, 4 号对象就位,从 0 号到 4 号 重新 调整为最大堆,25*,16,08

22、,21,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,25* 16 21 08 25 49,08 16 21 25* 25 49,交换 0 号与 3 号对象, 3 号对象就位,从 0 号到 3 号 重新 调整为最大堆,21,16,25*,08,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,21 16 08 25* 25 49,08 16 21 25* 25 49,交换 0 号与 2 号对象, 2 号对象就位,从 0 号到 2 号 重新 调整为最大堆,16,08,25*,21,25,49,0,

23、1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,16 08 21 25* 25 49,08 16 21 25* 25 49,交换 0 号与 1 号对象, 1 号对象就位,从 0 号到 1 号 重新 调整为最大堆,利用分类二叉树查找及堆排序实现学生成绩管理,堆排序算法,void HeapSort(EType a, int n) / 利用堆对a1:n 数组中的数据排序 heap = a; MaxHeapInit (heap, int n); EType x; for (int i = n-1; i = 1; i-) MaxHeapDelete (heap, ,St

24、atus MaxHeapDelete (EType a, EType ,while (son = heapson) break; heapi = heapson; / 孩子上移 i = son; / 下移根结点指针，继续比较 son = son * 2; heapi = heap0; return OK; ,5.7.3 树的路径长度和哈夫曼树（Huffman）,树的路径长度 1)简单路径长度:从树中一个结点到另一个结点之间的分枝构成这两个结点之间的路径。 2)树的简单路径长度:是指从树的根结点到每个结点的路径长度之和。 3) 加权路径长度:树中的每个叶子结点有权值，即每个叶子结点的大小不同（重

25、要性不同），那么从叶子到根结点之间的长度，就是叶子的权值与叶子到根结点之间路径长度（分枝数）的乘积。,1*2+2*3+3*3=17,1*2+2*4+3*2=16,结论:如果结点数相同，则顺序二叉树是具有最小简单路径长度的二叉树。,6*3+4*3+2*2+3*2=40,2*3+3*3+6*2+4*2=35,结论:结点的权值大的结点更接近根结点，树的加权路径长度就相对更小。,实际应用:情报检索，信息编码,数据元素的信息或信息存放的地址存入叶结点之中，分枝结点仅仅用于检索判断条件。 不同的信息具有不同的检索频率，检索频率高的信息就是检索概率大的信息，概率就是一个权值。 实际检索时，检索频率高的信息应

26、该检索判断的次数尽可能的少，即大权值的结点如果更接近根结点，检索树的检索效率就越高，也就是树的加权路径长度越小。,2.哈夫曼树及构成算法,哈夫曼树又称为最优二叉树: 有n个结点，它们分别具有不同的权值，将这n个结点作为叶结点可以构造出m种不同的二叉树，这些二叉树具有不同的加权路径长度，则其中加权路径长度最小的二叉树称为最优二叉树或哈夫曼树。 Huffman常译为赫夫曼、霍夫曼、哈夫曼等,(a) 原始堆,6,2,3,4,3,9,6,2,3,3,4,9,最小堆,删除2，3后的堆,(k) 删除11，16后的堆,(l) 插入27后的堆,27,图5.7.14 利用堆构造哈夫曼树的过程,检索判断,检索判断,2，3，3，4，6,9,构造哈夫曼树.,6,9,2，3，3，4，5,6,9,2，3，3，4，5,6,7,9,2，3，3，4，5,6,7,9,11,16,27,3 哈夫曼编码,一种文本压缩算法，是根据符号在一段文字中的相对出现频率不同，来压缩编码。是通信中最经典的压缩编码,symbol（符号