数据结构树-2课件

5.5线

索

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

中序遍历:A的前驱是————，B的前驱是————;E的前驱是————；D的前驱是————；图5.5.1二叉树ABCEFGHDKXMY一个结点N如果有左子树，则该结点的前驱就是其左子树中最右的子孙P。这个子孙结点的右链接域一定为空。EHGK中序遍历:H的前驱是D，G的前驱是B;X的前驱是A图5.5.1二叉树ABCEFGHDKXMY一个结点N如果没有左子树，则该结点的前驱就是其所有祖先中,最接近它的“右倾”祖先P。这个结点N的左链接域本身就是空。线索二叉树的实现规定：1）若结点有左子树，则Lchild指向其左孩子；否则，Lchild指向其直接前驱(即线索)；2）若结点有右子树，则Rchild指向其右孩子；否则，Rchild指向其直接后继(即线索)。如何区别？约定:当flag域为0时,表示正常情况;当flag域为1时,表示线索情况.前驱(后继)左(右)孩子为区别两种不同情况，特增加两个标志域：各1bitLflagLChilddataRChildRflag图5.5.5中序线索树A00B00C10∧D11E11F1∧1D,B,E,A,C,FNULLNULL图5.5.6二叉树ABEFHKNMDC图5.5.7二叉树前序遍历线索树ABMCKDNFHE图5.5.8二叉树中序遍历线索树ABMFNHKECD图5.5.9二叉树后序遍历线索树ABMDKHNFCE有关线索二叉树的几个术语：线索链表：线索：线索二叉树：线索化：用含flag的结点样式所构成的二叉链表指向结点前驱和后继的指针加上线索的二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程线索化过程就是在遍历过程中修改空指针的过程：将空的Lchild改为结点的直接前驱；将空的Rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）二叉线索树的结点结构定义typedefstruct{ EType data;BinaryTreeNode *LChild;bool Lflag;BinaryTreeNode *RChild;bool Rflag;}BinaryTreeNode；前序二叉线索树的遍历

voidThreadPreOrder(BinaryTreeNode*BT){//前序二叉线索树的遍历BinaryTreeNode*p=BT;while(p){cout<<p->data<<"";if(!p->Lflag) p=p->LChild;else p=p->RChild;}}BinaryTreeNode *p=BT;bool flag;while(!p){while(!p->Lflag) //查找一棵子树的最左子孙 p=p->LChild;flag=true;while(flag&&!p){cout<<p->data<<""; //访问结点p=p->RChild; //查找p的右子树的根或后继结点if(!p->Rflag) //p结点存在右子树时，为强制退出作准备flag=p->Rflag;}}二叉树转化为二叉线索树二叉树转化为中序二叉线索树P:当前访问结点，

q:指向其前驱结点。另设一个堆栈，以非递归方式遍历二叉树。算法结束的条件是堆栈和p同时为空。B) “走过”p左子树上的所有结点，直到左子树为空。如果某结点无左孩子，则将该结点的左链接域的指针作为线索指向其前驱q，并将q指向这个无左孩子的结点；转C步骤。C) 退栈，直到找到下一个可以“访问”的结点，并用p指向该结点；如果p的前驱（q指向）的右链接域为空，则将q的右链接域作为线索指向p。转B步骤。3。中序二叉树线索树中结点的插入

将一个由T指针指向的新结点插入到二叉线索树中，作为S所指的结点左孩子或S所指的结点右孩子。如果S原来已经存在左子树（或右子树），就将原来的左子树（或右子树）作为新结点T的左孩子（或右孩子）。线索树的插入问题中，将S结点与T结点链接在一起是件简单的事情，关键问题是要改变各结点的线索和对应的线索标志。中序线索树中插入的新结点T作为S的左孩子

If:S结点无左孩子新结点T的各值的变化：

T->RChild=S；

T->LChild=S->LChild。链接域标志的变化：

T->Lflag=1；T->Rflag=1S结点各个值的变化S->LChild=T；S->Lflag=0或false。

F

←最接近S结点的“右倾”祖先PSTS结点的最右子孙→

(b)S有左子树

T

PSIf:S结点有左孩子//找S左子树中的最右子孙q=T->LChild;while(!q->Rflag)q=q->RChild;q->RChild=T;

5.6一般树的表示

和遍历

ABCDEFGHIJK图5.6.1一棵树A∧BCDE∧FG∧H∧IJK∧图5.6.2一棵树存储结构typedefstructTreeNode{ EType data; TreeNode *son; TreeNode *next;}TreeNode；树和森林与二叉树的转换转换步骤：step1:将树中同一结点的兄弟相连;加线抹线旋转树如何转为二叉树？孩子—兄弟表示法step2:保留结点的最左孩子连线，删除其它孩子连线；step3:将同一孩子的连线绕左孩子旋转45度角。二叉树怎样还原为树？abeidfhgc要点：逆操作，把所有右孩子变为兄弟！

abdefhgicABCDEFGHJIABCDEFGHJIABCDEFGHJI5.6.2二叉树、一般树及森林的关系兄弟相连长兄为父头树为根孩子靠左A5.6.3一般树的遍历概念

树的遍历:例如：abdec前序序列：后序序列：abcdebdcea前序、后序前序遍历访问根结点；依次前序遍历根结点的每棵子树。后序遍历依次后序遍历根结点的每棵子树；访问根结点。树没有中序遍历树若采用“先转换，后遍历”方式，结果是否一样？abdec先序遍历：后序遍历：中序遍历：decbaabdecabcdebdcea1.树的先序遍历与二叉树的先序遍历相同；2.树的后序遍历相当于二叉树的中序遍历；结论：树的先序序列：abcde树的后序序列：bdcea5.6.4一般树的运算

一般树以二叉树形式存储时，一般树的大部分的运算可以用二叉树的算法来实现，如一般树的前序遍历、后序遍历、结点的个数等。一般树二叉树形式存储下结点的度。一般树二叉树形式存储下层次遍历

树的应用一（族谱）树的应用二：利用树型结构的搜索算法模拟因特网域名的查询5.7.1分类二叉树

分类二叉树又可以称为二叉排序树或二叉搜索树。在大量数据的处理中，为了便于数据查找，对输入的数据采用分类二叉树的方式存储，从而可以大大提高查找的效率，其时间效率是O(nlog2n)。

按中序遍历一棵分类二叉树，其结果是一个按某一特征值（关键字）排序的线性序列。定义：设key1,key2,…,keyn是一个数据集合中数据元素的对应关键字，按下列原则建立的二叉树称为分类二叉树。(1)每个元素有一个关键字，并且没有任意两个元素有相同的关键字。(2)根结点的左子树的关键字（如果存在）小于根结点的关键字。(3)根结点的右子树的关键字（如果存在）大于根结点的关键字。(4)根结点的左右子树也都是分类二叉树。数据集合的关键字：

｛15，23，12，8，13，9，25，21，18｝

15(a)1523(b)152312(c)1523128(d)152312813(e)1523128139(f)152312813925(g)15231281392521(h)1523128139252118(i)1523128139252118如何使中序遍历的结果按关键字降序排列呢？

｛15，23，12，8，13，9，25，21，18｝2分类二叉树运算

1）分类二叉树中数据元素的查找

while(p) if(SearchKey<p->data.key) p=p->LChild; else if(SearchKey>p->data.key) p=p->RChild; else { x=p->data; returntrue;}图5.7.2查找结点1815231281392521182。将结点插入到分类二叉树中

插入算法与查找算法的一个显著区别是：查找中，如果找到，则成功。在插入时也要查找，是当查找失败时，说明找到了插入点；查找成功时，说明有相同的数据元素出现，这在分类二叉树中是不允许的，即插入失败。图5.7.3插入新结点22152312813925211822←插入结点while(p){ parent=p; if(x.key<p->data.key) p=p->LChild; else if(x.key>p->data.key) p=p->RChild; else returnfalse;//重复出现，即相等值结点出现}//找到插入点，为x申请一个空间填入其值，并将该结点连接至parent BinaryTreeNode*q=newBinaryTreeNode; q->data=x; If(BT){//原树非空 if(x.key<parent->data.key) parent->LChild=q; else parent->RChild=q; } else//插入到空树中 BT=q; returntrue;}删除分类二叉树中的结点删除结点x的三种情况：x是叶子结点；x只有一个非空子树；x有两个非空子树(a)删除左叶子

x

←被删结点p指向(b)删除根结点且只有一个孩子x

←被删结点p指向←新根(c)删除非根结点且只有一个孩子x

←被删结点p指向图5.7.4删除一个左右子树非空的结点x

x最小

(d)

最大←被删结点p最大或最小其中一个结点替换x堆排序1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(RobertW．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法(HeapSort)1堆树的定义

最大树：所谓最大树就是每个结点的值都大于或等于其子结点（如果存在）值。最小树：所谓最小树就是每个结点的值都小于或等于其子结点（如果存在）值。堆树简称为堆，是一棵二叉树。堆有如下特征：如果一棵顺序二叉树本身又满足最大树的条件，则这棵顺序二叉树就是最大堆；如果一棵顺序二叉树本身又满足最小树的条件，则这棵顺序二叉树就是最小堆。图5.7.5最大树或最小树52305052417581252301755230505241755230524175(d)(a)(b)(c)(e)20一般树，最大树

二叉树

，最小树

顺序二叉树最大堆

？

2堆树的意义

顺序二叉树的高度最小，具有n个结点的顺序二叉树的高度是log2n。如果在这棵树中按分枝查找，搜索的次数可以达到最少；顺序二叉树以顺序存储方式存储时，空间不会造成浪费，节省了动态存储方式下链接域的空间耗费。利用数组下标，可以用公式来表达顺序二叉树中各结点之间的逻辑关系。堆排序--数据排序的一种经典方法

先将堆顶元素（最大结点）移到结果数据存储空间，再从堆中余下的结点（左子树或右子树）中选出一个最大结点，移到堆顶，即将堆中余下的结点重新“调整”为一个新堆.将堆顶结点移到结果数据存储空间的下一个空间位置，如此下去，直到所有的结点都被移到结果数据存储空间。5230524175移去堆顶52304175如何构造一个初始堆树?有了初始堆，在排序时，当移走根结点时，对余下的树又如何再“调整”为一棵新堆?移去该结点？

1.初始化一个非空的最大堆

一个顺序二叉树以顺序存储方式存储时，就是连续地存储在数组元素空间中.第一个元素位置存放的是顺序二叉树的根结点，最后一个数组元素位置存放的是顺序二叉树中最下面一层中最右的结点。15221235479555624715836916106211121238052361662553812127952415每个数据在逻辑上关联的数据不一定是接下来的数组空间中的数据.i:左孩子2*i;右孩子2*i+1临时存放数据元素245堆：比较交换结点i，2*i及2*i+1构造初始堆

首先将所有的叶子结点（最底层结点）看成为若干个子堆(只有一个结点)N的子树已经是子堆，则新的根结点是N和它的子树（一个或两个）根结点的值中最大的结点值。

构造N所指结点为根的堆算法思想：A.

先将N所指结点的值复制到一个工作空间中临时存放。B.

再将N所指结点的孩子中，值较大的与工作空间中的值比较：1)

如果工作空间中值更大，新堆已经形成，就将工作空间中的值存放到N所指的位置，结束。2）如果某个孩子的结点值更大，则将这个值存放到这个孩子双亲的结点位置，即N位置。此时，工作空间中的结点还未找到存放位置，再将上移的孩子结点位置作为N所指的新位置，转到B步骤。for(inti=HeapSize/2;i>=1;i--)//从最后一个结点的根开始，直到第一个结点1)i=HeapSize/2=10/2=5，heap[5]=722)i--;i=5;heap[4]=53…..123456789100最大堆调整(1)最大堆调整(2)初始化一个非空的最大堆算法

for(inti=HeapSize/2;i>=1;i--){//从最后一个结点的根开始，直到第一个结点heap[0]=heap[i];//将i结点值复制到工作空间heap[0]中

intson=2*i; //son的双亲结点是heap[0]的目标位置， //son首先指向i的左孩子

while(son<=HeapSize){//找左右孩子中较大结点if(son<HeapSize&&heap[son]<heap[son+1]) son++;//son<HeapSize时，存在右孩子，如左孩子小于右孩子，son指向右孩子if(heap[0]>=heap[son])//大孩子再与工作空间中结点值再比较 break;//工作空间中值大，找到heap[0]的目标位置heap[son/2]=heap[son];//将大孩子上移至双亲位置son*=2;//son下移一层到上移的结点（大孩子）位置}heap[son/2]=heap[0]; //heap[0]存放到目标位置4.堆排序

不必再开辟另一个结果存储区，只要将删除的堆顶结点存放到当前堆的最后一个叶子结点空间中就可以。

492525*211608012345082525*16214902543149252125*160808252125*1649交换0号与5号对象,5号对象就位初始最大堆基于初始堆进行堆排序0816

21

25*

25

492525*082116490123451625*082521490254312525*210816491625*210825

49交换0号与4号对象,4号对象就位从0号到4号重新调整为最大堆25*1608212549012345081625*25214902543125*16210825

4908162125*

25

49交换0号与3号对象,3号对象就位从0号到3号重新调整为最大堆211625*082549012345081625*25214902543121160825*

25

49081621

25*

25

49交换0号与2号对象,2号对象就位从0号到2号重新调整为最大堆160825*212549012345081625*25214902543116082125*

25

490816

21

25*

25

49交换0号与1号对象,1号对象就位从0号到1号重新调整为最大堆利用分类二叉树查找及堆排序实现学生成绩管理

堆排序算法voidHeapSort(ETypea[],intn){//利用堆对a[1:n]数组中的数据排序heap=a; MaxHeapInit(heap,intn); ETypex;for(inti=n-1;i>=1;i--){MaxHeapDelete(heap,&x);heap[i+1]=x;}}StatusMaxHeapDelete(ETypea[],EType&x){//插入x到最大堆中Heap=a;if(HeapSize==0)returnERROR; //堆空x=heap[1]; //最大结点存放到xheap[0]=heap[HeapSize--]; //最后一个结点存放到heap[0]，调整堆中元素的个数inti=1,son=2*i;

while(son<=HeapSize){if(son<HeapSize&&heap[son]<heap[son+1])son++;if(heap[0]>=heap[son])break;heap[i]=heap[son]; //孩子上移i=son; //下移根结点指针，继续比较son=son*2;}heap[i]=heap[0];returnOK;}5.7.3树的路径长度和哈夫曼树（Huffman）树的路径长度1)简单路径长度:从树中一个结点到另一个结点之间的分枝构成这两个结点之间的路径。2)树的简单路径长度:是指从树的根结点到每个结点的路径长度之和。

3)加权路径长度:树中的每个叶子结点有权值，即每个叶子结点的大小不同（重要性不同），那么从叶子到根结点之间的长度，就是叶子的权值与叶子到根结点之间路径长度（分枝数）的乘积。AEIHDGFBC图5.7.10一棵二叉树AEIHDGFBC图5.7.11一棵顺序二叉树1*2+2*3+3*3=17

1*2+2*4+3*2=16

结论:如果结点数相同，则顺序二叉树是具有最小简单路径长度的二叉树。图5.7.13一棵带权二叉树EIHF2364图5.7.12一棵带权二叉树EIHF64236*3+4*3+2*2+3*2=40

2*3+3*3+6*2+4*2=35结论:结点的权值大的结点更接近根结点，树的加权路径长度就相对更小。

实际应用:情报检索，信息编码数据元素的信息或信息存放的地址存入叶结点之中，分枝结点仅仅用于检索判断条件。不同的信息具有不同的检索频率，检索频率高的信息就是检索概率大的信息，概率就是一个权值。实际检索时，检索频率高的信息应该检索判断的次数尽可能的少，即大权值的结点如果更接近根结点，检索树的检索效率就越高，也就是树的加权路径长度越小。

2.哈夫曼树及构成算法哈夫曼树又称为最优二叉树:有n个结点，它们分别具有不同的权值，将这n个结点作为叶结点可以构造出m种不同的二叉树，这些二叉树具有不同的加权路径长度，则其中加权路径长度最小的二叉树称为最优二叉树或哈夫曼树。Huffman常译为赫夫曼、霍夫曼、哈夫曼等(a)原始堆623439623346233499(b)初始化堆236439233642336499最小堆删除2，3后的堆349653496523(d)插入5后的堆3465922L↓33R↓5523D↓346933469(c)删除2，3后的堆34963496(e)删除3，4后的堆5695696952333L↓44R↓7734D↓4569(f)插入7后的堆5679569769523734(g)删除5，6后的堆679797997345L↓66R↓11D↓523523116(h)插入11后的堆791179119734523116(i)删除7，9后的堆91111169734115231167L↓99R↓16D↓734(j)插入16后的堆11161116523116169734(k)删除11，16后的堆16973411L↓16R↓27D↓52311627523116169734(l)插入27后的堆272727523116169734图5.7.14利用堆构造哈夫曼树的过程检索判断检索判断{2，3，3，4，6,9}构造哈夫曼树.27523116169734{2，3，3，4，5,6,9}{2，3，3，4，5,6,7,9}{2，3，3，4，6,9}{2，3，3，4，5,6,7,9,11}{2，3，3，4，5,6,7,9,11,16}{2，3，3，4，5,6,7,9,11,16,27}3哈夫曼编码一种文本压缩算法，是根据符号在一段文字中的相对出现频率不同，来压缩编码。是通信中最经典的压缩编码symbol（符号）

code（编码）A010B100C000D111ABACCDA:21bitsymbol（符号）

code（编码）A00B01C10D11ABACCDA:14bit信息ABACCDA字母B和D只出现过一次，字母A则出现过三次。如果能使字母A的位数比字母B和字母D的位数少。整个信息编码长度将大大地减少.symbol（符号）

co