数据结构第4章树.ppt

教学目标1、知识目标1）掌握树的基本概念；2）掌握二叉树、满二叉树、完全二叉树的概念，掌握二叉树的性质；3）掌握二叉树的存储结构、二叉树的遍历及算法；4）了解树、森林与二叉树的转换及树的存储结构；5）掌握哈夫曼树的构造过程。2、能力目标1）具有恰当的选择二叉树作为数据的逻辑结构和存储结构的能力；2）具有应用二叉树解决实际问题的能力。3、素质目标养成良好的完成工作任务、团队合作、良好沟通、创新思维和解决问题的能力。,2,4.1 树的概念 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。树结构在客观世界中是大量存在的，在计算机领域中也有着广泛的应用，如在编译程序中，用树来表示源程序的语法结构；在数据库系统可用树来组织信息。1、树的递归定义：树是n(n0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m0)个互不相交的有限子集Tl，T2，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。,6,6,6,6,6,6,2、树的表示 1）树形图表示：结点用圆圈表示，结点名字写在圆圈旁或圆圈内，子树与其根之间用无向边来连接。2）嵌套集合表示法：用集合的包含关系描述树结构。3）凹入表表示法：类似于书的目录。3、树结构的基本术语1）结点的度结点的度：一个结点拥有子树的个数称为该结点的度。树的度：该树中结点的最大度数称为该树的度。叶子结点：度为零的结点称为叶子或终端结点。分支结点：度不为零的结点称分支结点或非终端结点。即除叶子结点外的结点均为分支结点。内部结点：除根结点之外的分支结点统称为内部结点。开始结点：根结点又称为开始结点。,2）结点之间的关系孩子结点：树中某个结点的子树的根称为该结点的孩子结点。双亲结点：孩子结点的根称为该结点的双亲。兄弟结点：同一个双亲的孩子互称为兄弟结点。堂兄弟：在后面介绍。祖先和子孙：在后面介绍。3）路径路径或道路：若树中存在一个结点序列k1,k2,kj,使得ki是ki+1的双亲(1ij)，则称该结点序列是从kl到kj的一条路径或道路。路径的长度：指路径所经过的边的数目。注意：若一个结点序列是路径，则在树的树形图表示中，该结点序列自上而下地通过路径上的每条边。从树的根结点到树中其余结点均存在一条惟一的路径。,祖先和子孙：若树中结点k到ks存在一条路径，则称k是ks的祖先，ks是k的子孙。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。约定：结点k的祖先和子孙不包含结点k本身。4）结点的层数和树的深度 结点的层数：根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。堂兄弟：双亲在同一层的结点互为堂兄弟。树的深度：树中结点的最大层数称为树的深度。注意：也有将树根的层数定义为0的。5）有序树和无序树 若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树；否则称为无序树。若不特别指明，一般讨论的树都是有序树。,6）森林 森林是m(m0)棵互不相交的树的集合。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。4、树型结构的逻辑特征 树型结构的逻辑特征可用树中结点之间的父子关系来描述：1）树中任一结点都可以有零个或多个直接后继结点，但至多只能有一个直接前驱结点。2）树中只有根结点无前驱，它是开始结点；叶结点无后继，它们是终端结点。3）祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。4）有序树中，同一组兄弟结点从左到右有长幼之分。对这一关系加以延拓，规定若k1和k2是兄弟，且k1在k2的左边，则kl的任一子孙都在k2的任一子孙的左边，那么就定义了树中结点之间的横向次序。,4.2 二叉树 二叉树是树型结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。一、二叉树的定义 1、二叉树的递归定义 二叉树是n(n0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。2、二叉树的五种基本形态 二叉树可以是空集；可以有空的左子树或右子树；或者左、右子树皆为空。二叉树的五种基本形态如图所示。,3、二叉树不是树的特例 1）二叉树与无序树不同 无序树中每个结点可以有多棵子树，即使只有两棵子树也无左右之分；二叉树中，每个结点最多只能有两棵子树，并且有左右之分。2）二叉树与度数为2的有序树不同 在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序；而在二叉树中，即使是一个孩子也有左右之分。例 下图中(a)和(b)是两棵不同的二叉树，它们同右图中的普通树(作为有序树或无序树)很相似，但却不等同于这棵普通树。若将这三棵树均看做普通树，则它们就是相同的了。二叉树并非是树的特殊情形，它们是两种不同的数据结构。,二、二叉树的性质性质1 二叉树第i层上的结点数目最多为2i-1(i1)个。性质1的证明可采用数学归纳法。性质2 深度为k的二叉树至多有2k-1(k1)个结点。性质2由性质1可以得到。性质3 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。两种特殊的二叉树1、满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点：每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层。,12,证明：假设树非空，用数学归纳法证明：当i=1时，因为第1层上只有一个根结点，而2i-1=20=1。所以命题成立。假设对所有的j(1ji)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有22i-2=2i-1个结点，故命题成立。,12,证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点和2度结点数(分别记为n0,n1,n2)之和：n=n0+n1+n2 另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：nl+2n2，而树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：n=n1+2n2+1 综合以上两个式子得到：n0=n2+1 即在二叉树中叶子结点数比度为2的结点数多1个。,证明：由性质1，第i层至多有2i-1个(1ik)结点，所以深度为k的二叉树的结点总数至多为 20+21+2k-1=2k-1个。,12,13,2、完全二叉树 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。完全二叉树特点：1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树是一棵完全二叉树。3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。4）深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。性质4 具有n个结点的完全二叉树的深度为lgn+1或lg(n+1)，其中方括号表示取整数部分。,证明：设所求完全二叉树的深度为k。由完全二叉树特点知：深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数n2k-1-1。另一方面，由性质2知：深度为k的二叉树至多有2k-1(k1)个结点，因此，n2k-1，即：2k-1-ln2k-1，由此可推出：2k-1n2k，取对数后有：k-1lgnk 又因k-1和k是相邻的两个整数，故有k-1=lgn 由此即得：k=lgn+1。另外，由2k-1-ln2k-1得2k-1n+12k，两边再取对数便可得到：k=lg(n+1)。,三、二叉树的存储结构1、顺序存储结构：把二叉树所有结点按照一定的线性次序存储到一片连续存储单元中。结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。(1)完全二叉树的存储结构完全二叉树结点的编号编号方法：在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右给所有结点编号，开始结点的编号为1，这样能得到一个反映整个二叉树结构的线性序列。编号特点：完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是ki(1in)，则有：,若i1，则ki的双亲编号为i/2；若i=1，则ki是根结点，无双亲。若2in，则ki的左孩子的编号是2i；若2in，则ki无左孩子，因此也无右孩子，即ki必定是叶子。因此完全二叉树中编号in/2的结点必定是叶结点。若i为奇数且不为1，则ki是结点ki/2的右孩子，ki的左兄弟的编号是i-1；若i=1或i为偶数，则ki无左兄弟。若i为偶数且小于n，则ki是结点ki/2的左孩子，ki的右兄弟的编号是i+1；若i=n或i为奇数，则ki无右兄弟。由此可知，完全二叉树中结点的编号序列，完全反映了结点之间的逻辑关系。,完全二叉树的顺序存储 将完全二叉树中所有结点按编号顺序依次存储在一个向量bt0n中。其中：bt1n用来存储结点，bt0不用或用来存储结点数目。说明：完全二叉树的顺序存储结构既简单又节省存储空间；按这种方法存储的完全二叉树，向量元素bti的下标i就是对应结点的编号。(2)一般二叉树的顺序存储具体方法将一般二叉树添上一些“虚结点”，使其成为完全二叉树；为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号；将结点按编号存入向量对应分量，其中“虚结点”用表示。,例如：设完全二叉树共有26个结点，存放在向量bt026中。则bt15的双亲结点是bt7；bt15是bt7的右孩子；bt15的左兄弟是bt14；bt15无孩子结点，是叶结点。,二叉树的顺序存储结构的优缺点：优点是存储结构简单；缺点是可能浪费大量的存储空间。在最坏的情况下，一个深度为k的且只有k个结点的右单支树，需要2k-1个结点的存储空间，浪费了2k-1-k个存储空间。例如：三个结点的右单支树。二叉树顺序存储结构的描述#define MAXSIZE 50/设置二叉树的最大结点数typedef char DataType;/定义结点类型typedef struct/定义二叉树结构 DataType btMAXSIZE;/存放二叉树的结点 int num;/存放二叉树的结点数 SeqBT;注：如果使用元素bt0存放二叉树的结点数，成员num可省略或不定义结构而只定义数组。,2、链式存储结构(1)结点的结构：二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构如图：(2)结点的类型说明typedef char DataType;/定义结点数据域类型typedef struct node/定义结点结构 DataType data；struct node*lchild，*rchild；/左右孩子指针 BinTNode；/结点类型 typedef BinTNode*BinTree；/*定义新类型BinTree为指向BinTNode类型结点的指针类型，用于定义指向根结点的指针*/,(3)二叉链表（二叉树的常用链式存储结构）在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root，就构成了二叉树的链式存储结构，并将其称为二叉链表。说明：一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。(4)带双亲指针的二叉链表 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。,证明：因为二叉树中结点总数n等于0度结点数n0、1度结点数n1和2度结点数n2之和：n=n0+n1+n2 由二叉树的性质3：n0=n2+1，所以，n1+2n2=n-1。而在二叉链表中，度为1的结点有一个指针域不空，度为2的结点的两个指针域都不空，即n个结点的二叉链表中共有n1+2n2个指针域不空，即n-1个指针域不空，分别指向左右孩子。因此，其余的n+1个指针域为空。,19,4.3 二叉树的遍历 二叉树遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。遍历：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。一、遍历方案1、遍历方案：由于二叉树中每个结点可能有两个后继结点，所以遍历二叉树存在多条遍历路线。从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：1）访问结点本身(N)；2）遍历该结点的左子树(L)；3）遍历该结点的右子树(R)。以上三种操作有六种遍历方案：NLR、LNR、LRN、NRL、RNL、RLN。由于前三种次序与后三种次序对称，所以只讨论先左后右的前三种次序。,2、三种遍历的命名前(先)序遍历NLR：访问结点的操作发生在遍历其左右子树之前，又称为先根遍历。中序遍历LNR：访问结点的操作发生在遍历其左右子树之中(间)，又称为中根遍历。后序遍历LRN：访问结点的操作发生在遍历其左右子树之后，又称为后根遍历。3、遍历规则及算法(1)中序遍历的递归算法 若二叉树非空，则依次执行如下操作：遍历左子树；访问根结点；遍历右子树。(2)先序遍历的递归算法 若二叉树非空，则依次执行如下操作：访问根结点；遍历左子树；遍历右子树。(3)后序遍历得递归算法 若二叉树非空，则依次执行如下操作：遍历左子树；遍历右子树；访问根结点。,/*用二叉链表作为存储结构的中序遍历算法*/void InOrder(BinTree T)if(T)/如果二叉树非空 InOrder(T-lchild)；/遍历左子树 printf(c，T-data)；/访问根结点 InOrder(T-rchild);/遍历右子树,/*用二叉链表作为存储结构的先序遍历算法*/void PreOrder(BinTree T)if(T)/如果二叉树非空 printf(c，T-data)；/访问根结点 PreOrder(T-lchild)；/遍历左子树 PreOrder(T-rchild);/遍历右子树,/*用二叉链表作为存储结构的后序遍历算法*/void PostOrder(BinTree T)if(T)/如果二叉树非空 PostOrder(T-lchild)；/遍历左子树 PostOrder(T-rchild);/遍历右子树 printf(c，T-data)；/访问根结点,21,21,22,二、遍历序列1、中序序列：中序遍历二叉树时，按对结点的访问次序形成的结点序列称为中序序列。2、先序序列：先序遍历二叉树时，按对结点的访问次序形成的结点序列称为先序序列。3、后序序列：后序遍历二叉树时，按对结点的访问次序形成的结点序列称为后序序列。三、二叉链表的构造1、基本思想 基于先序遍历构造二叉链表，即以二叉树的先序序列为输入构造二叉链表。注：先序序列中须加入虚结点以示空指针的位置。如：前例右图带虚结点的先序序列为：ABDGCEHF。2、构造算法,/*以二叉树的先序序列为输入构造二叉链表*/*假设虚结点输入时以空格字符表示*/void CreateBinTree(BinTree*T)/构造二叉链表。T是指向根指针的指针char ch；if(ch=getchar()=)*T=NULL;/读入空格，将相应指针置空else/读入非空格*T=(BinTNode*)malloc(sizeof(BinTNode);(*T)-data=ch；CreateBinTree(/构造右子树注意：调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。,四、二叉链表的基本操作二叉树的基本操作包括：遍历二叉树、计算二叉树深度、计算所有结点总数、计算叶子结点数、计算双孩子结点个数、计算单孩子结点个数等。说明：以下操作均用二叉链表作为存储结构。1、计算二叉树深度算法步骤：如果二叉树BT为空，返回0，否则执行；分别计算BT的左右子树的深度；如果左子树深度大，返回左子树深度+1，否则返回右子树深度+1。2、计算双孩子结点个数算法步骤：如果二叉树BT为空，返回0；如果左右子树至少有一个为空，返回左子树双孩子结点数与右子树双孩子结点数之和；如果左右子树都不空，返回左子树双孩子结点数与右子树双孩子结点数之和+1。,/*二叉链表作为存储结构计算二叉树深度算法*/int BinTreeDepth(BinTNode*BT)int leftdep,rightdep;/分别记录左右子树深度 if(BT=NULL)return(0);else leftdep=BinTreeDepth(BT-lchild);rightdep=BinTreeDepth(BT-rchild);if(leftdeprightdep)return(leftdep+1);elsereturn(rightdep+1);,23,23,/*二叉链表作为存储结构计算双孩子结点数算法*/int twosoncount(BinTNode*BT)if(BT=NULL)return(0);else if(BT-lchild=NULL|BT-rchild=NULL)return(twosoncount(BT-lchild)+twosoncount(BT-rchild);else if(BT-lchild!=NULL,4.4 线索二叉树 用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左右孩子结点的指针域，所以从任一结点出发只能直接找到该结点的左右孩子结点，而无法直接找到该结点在某种遍历序列中的前驱和后继结点。一、线索二叉树的概念1、定义 n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针，这种附加的指针称为“线索”。把加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。注意：线索链表解决了找结点在某种遍历序列中的前驱和后继结点困难的问题。,25,25,25,2、线索链表的结点结构 线索链表中的结点结构为其中，左标志ltag为0表示lchild是指向该结点的左孩子的指针，左标志ltag为1表示lchild是指向该结点的前驱结点的左线索；右标志rtag为0表示rchild是指向该结点的右孩子的指针，右标志rtag为1表示rchild是指向该结点的后继结点的右线索。3、线索二叉树和线索链表的图形表示中序线索二叉树和中序线索链表先序线索二叉树和先序线索链表后序线索二叉树和后序线索链表说明：实线表示指针，虚线表示线索。线索二叉链表中，结点是叶结点的充要条件为：左、右标志均是1。,二、二叉树的线索化1、线索化和线索化实质 将二叉树变为线索二叉树的过程称为线索化。按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指针。2、二叉树的中序线索化 分析：算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前驱或中序后继结点间的线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前驱，而*p是*pre的后继。线索链表的描述 将二叉树按中序线索化的算法,线索链表的描述typedef enum Link，Thread PointerTag；/枚举值Link和Thread分别为0，1typedef struct node DataType data；PointerTag ltag，rtag；/左右标志 struct node*lchild，*rchild；BinThrNode；线索二叉树的结点类型typedef BinThrNode*BinThrTree；BinThrNode*pre=NULL；/全局量,26,将二叉树按中序线索化的算法void InorderThreading(BinThrTree p)/将二叉树p中序线索化if(p)/p非空时，当前访问结点是*p InorderThreading(p-lchild)；/左子树线索化/以下直至右子树线索化之前相当于遍历算法中访问结点的操作 p-ltag=(p-lchild)?Link：Thread；/左指针非空时左标志为Link(即0)，否则为Thread(即1)p-rtag=(p-rchild)?Link：Thread；if(pre)/若*p的前驱*pre存在 if(pre-rtag=Thread)/若*p的前驱右标志为线索 pre-rchild=p；/令*pre的右线索指向中序后继 if(p-ltag=Thread)/*p的左标志为线索 p-lchild=pre；/令*p的左线索指向中序前驱/完成处理*pre的线索 pre=p；/令pre是下一访问结点的中序前驱 InorderThreeding(p-rehild)；/右子树线索化/endif,27,三、线索二叉树的运算1、查找某结点*p在指定次序下的前驱和后继结点(1)在中序线索二叉树中，查找结点*p的中序后继结点 在中序线索二叉树中，查找结点*p的中序后继结点分两种情形：若*p的右子树为空(即p-rtag为Thread)，则p-rchild为右线索，即右孩子指针直接指向*p的中序后继。若*p的右子树非空(即p-rtag为Link)，则*p的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是*p的右子树中“最左下”的结点，即*p的中序后继结点。查找结点*p的中序后继结点的算法,27,查找结点*p的中序后继结点的算法BinThrNode*InorderSuccessor(BinThrNode*p)/在中序线索树中找结点*p的中序后继，设p非空 BinThrNode*q；if(p-rtag=Thread)/*p的右子树为空 return p-rchild；/返回右线索所指的中序后继 else q=p-rchild；/从*p的右孩子开始查找 while(q-ltag=Link)q=q-lchild；/左子树非空时，沿左链往下查找 return q；/当q的左子树为空时，它就是最左下结点/end if,28,(2)在中序线索二叉树中，查找结点*p的中序前驱结点 中序是一种对称序，故在中序线索二叉树中查找结点*p的中序前驱结点与找中序后继结点的方法完全对称。具体情形如下：若*p的左子树为空，则p-1child为左线索，即左孩子指针直接指向*p的中序前驱结点；若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。该结点是*p的左子树中“最右下”的结点，它是*p的左子树中最后一个中序遍历到的结点，即*p的中序前驱。查找结点*p的中序前驱结点的算法注意：对于非线索二叉树，仅从*p出发无法找到其中序前驱(或后继)，而必须从根结点开始中序遍历。线索二叉树中的线索使得查找中序前驱和后继变得简单有效。,28,查找结点*p的中序前驱结点的算法BinThrNode*Inorderpre(BinThrNode*p)/在中序线索树中找结点*p的中序前趋，设p非空BinThrNode*q；if(p-ltag=Thread)/*p的左子树为空 return p-lchild；/返回左线索所指的中序前趋else q=p-lchild；/从*p的左孩子开始查找 while(q-rtag=Link)q=q-rchild；/右子树非空时，沿右链往下查找 return q；/当q的右子树为空时，它就是最右下结点/end if,29,(3)在后序线索二叉树中，查找指定结点*p的后序前驱结点在后序线索二叉树中，查找指定结点*p的后序前驱结点的具体规律是：若*p的左子树为空，则p-lchild是前驱线索，即左孩子指针直接指向其后序前驱结点。若*p的左子树非空，则p-lchild不是前驱线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历结点。当*p的右子树非空时，*p的右孩子必是其后序前驱。当*p无右子树时，*p的左孩子必是其后序前驱。,(4)在后序线索二叉树中，查找指定结点*p的后序后继结点在后序线索二叉树中，查找指定结点*p的后序后继结点的具体规律是：若*p是根，则*p是该二叉树后序遍历过程中最后一个访问到的结点，*p的后序后继为空。若*p是其双亲的右孩子，则*p的后序后继结点就是其双亲结点。若*p是其双亲的左孩子，但*P无右兄弟，*p的后序后继结点是其双亲结点。若*p是其双亲的左孩子，但*p有右兄弟，则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点，它是该子树中“最左下的叶结点”。,30,30,2、遍历线索二叉树：遍历某种次序的线索二叉树，只要从该次序下的开始结点出发，反复找到结点在该次序下的后继，直至终端结点。遍历中序线索二叉树算法分析：中序序列的终端结点的右线索为空，所以do语句的终止条件是p=NULL。该算法的时间复杂性为O(n)。因为是非递归算法，常数因子上小于递归的遍历算法。因此，若对一棵二叉树要经常遍历，或查找结点在指定次序下的前驱和后继，则应采用线索链表作为存储结构为宜。以上介绍的线索二叉树是全线索树（即左右线索均要建立）。许多应用中只要建立左右线索中的一种。若在线索链表中增加一个头结点，令头结点的左指针指向根，右指针指向其遍历序列的开始或终端结点会更方便。,遍历中序线索二叉树的算法void TraverseInorderThrTree(BinThrTree p)/遍历中序线索二叉树 if(p)/树非空 while(p-ltag=Link)p=p-lchild；/从根往下找最左下结点，即中序序列的开始结点 do printf(“c”，p-data)；/访问结点 p=InorderSuccessor(p)；/找*p的中序后继 while(p);/endif,4.5 树和森林一、树、森林到二叉树的转换1、将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树。转换方法：加线：在所有兄弟结点之间加一连线；去线：对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线；调整：按树的层次进行调整，将原来的右兄弟变成其右孩子，原来的无兄弟结点变成左孩子。说明：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。,2、将一个森林转换为二叉树转换方法：树转换为二叉树：将森林中的每棵树转换为二叉树；连接根结点：再将各二叉树的根结点视为兄弟从左至右连在一起；调整：按树的层次进行调整，将原来的右兄弟变成其右孩子，原来的无兄弟结点变成左孩子。3、二叉树到树、森林的转换转换方法：加线：在左孩子结点的双亲与左孩子结点的右孩子、右孩子的右孩子等等之间加一连线；去线：去掉所有双亲与右孩子之间的连线；调整：按树的层次进行调整，将原来根结点的右孩子、右孩子的右孩子等等变成森林中树的根，其它结点的右孩子、右孩子的右孩子等等变成兄弟。,33,33,33,二、树的存储结构1、双亲链表表示法 该表示法用向量表示结点，并用一个整型量parent指示其双亲的位置，称为指向其双亲的指针。双亲链表向量表示的描述#define MaxTreeSize 100/定义向量空间的容量typedef char DataType；/定义结点数据域类型typedef struct/定义结点 DataType data；/定义结点数据域 int parent；/双亲指针，指示双亲的位置 PTreeNode；typedef struct/定义链表 PTreeNode nodesMaxTreeSize;int n；/结点总数 PTree；PTree T；/T是双亲链表注意：若T.nodesi.parent=j，则T.nodesi的双亲是T.nodesj。,2、孩子链表表示法 该表示法为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。孩子链表表示的描述#define MaxTreeSize 100/定义向量空间的容量typedef char DataType；/定义结点数据域类型typedef struct CNode/孩子链表结点 int child；/孩子结点在向量中对应的序号 struct CNode*next；CNode；typedef struct DataType data；/存放树中结点数据 CNode*firstchild；/孩子链表的头指针 PTNode；typedef struct PTNode nodesMaxTreeSize；int n，root；/n为结点总数，root指出根在向量中的位置 CTree；CTree T；/T为孩子链表表示注意：当结点T.nodesi为叶子时，其孩子链表为空，即T.nodesi.firstchild=NULL。,3、孩子兄弟链表表示法(1)结点的结构：与二叉链表类似，在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示。(2)孩子兄弟链表表示的描述typedef char DataType;/定义结点数据域类型typedef struct node/定义结点结构 DataType data;struct node*leftmostchild,*rightsibling;CSTNode;/结点类型 CSTNode*T;/指向树的开始结点的指针注意：这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。,三、树的遍历 设树T的根结点是R，根的子树从左到右依次为T1，T2，Tk。树的遍历分为先序遍历和后序遍历两种。1、树T的先序遍历规则 若树T非空，则 访问根结点R；依次先序遍历根R的各子树T1，T2，Tk。2、树T的后序遍历规则 若树T非空，则依次后序遍历根R的各子树T1，T2，Tk；访问根结点R。说明：前序遍历一棵树恰好等价于前序遍历该树对应的二叉树；后序遍历一棵树恰好等价于中序遍历该树对应的二叉树。,4.6 哈夫曼树及其应用一、哈夫曼树的有关概念1、树的路径长度：从根结点到树中每一结点的路径长度之和称为树的路径长度。说明：在结点数目相同的二叉树中，完全二叉树的路径长度最短。2、树的带权路径长度结点的权：赋予树中某结点的一个有某种意义的实数，称为该结点的权。结点的带权路径长度：结点到树根之间路径长度与该结点上权的乘积，称为结点的带权路径长度。树的带权路径长度：树中所有叶结点的带权路径长度之和，称为树的带权路径长度，亦称为树的代价。记为：，n表示叶子结点的数目，wi和li表示叶结点ki的权值和根到ki之间的路径长度。,3、哈夫曼树：在权为wl,w2,wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为哈夫曼树或最优二叉树。说明：叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树；哈夫曼树中，权越大的叶子离根越近；哈夫曼树的形态不唯一，但WPL值相同且最小。二、哈夫曼树的构造1、哈夫曼算法 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，故称其为哈夫曼算法。基本思想：(1)根据给定的n个权值wl,w2,wn构成n棵二叉树的森林F=T1,T2,Tn，其中每棵二叉树Ti中都只有一个权值为wi的根结点，其左右子树均空；,(2)在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时，可以从中任选两棵)，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左，谁右无关紧要)，将这两个孩子的权值之和作为新树根的权值；(3)对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。用哈夫曼算法构造哈夫曼树的过程：给定4个叶子结点a,b,c和d，分别带权7,5,2和4。用哈夫曼算法构造哈夫曼树的过程如图。说明：初始森林中的n棵二叉树，每棵树是一个孤立的结点，它们既是根，又是叶子n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。哈夫曼树是严格的二叉树，没有1度的分支结点。,三、哈夫曼算法的实现1、哈夫曼树结点的结构 哈夫曼树的结点用一个大小为2n-1的向量来存储，每个结点包含权值域weight、指示左右孩子结点在向量中下标的整型量lchild和rchild、指示双亲结点在向量中下标的整型量parent。结点结构如图。2、哈夫曼树的描述#define n 100/叶子数目#define m 2*n-1/树中结点总数typedef struct/定义结点类型 float weight;/定义权值域 int lchild,rchild,parent;/定义左右孩子及双亲指针 HTNode;typedef HTNode HuffmanTreem;/定义HuffmanTree为新的类型标识符，用该标识符定义的变量是具有HTNode类型的含有m个元素的向量。,注意：因为C数组的下界为0，故用-1表示空指针。树中某结点的lchild、rchild和parent不等于-1时，它们分别是该结点的左、右孩子和双亲结点在向量中的下标。这里设置parent域有两个作用：其一是使查找某结点的双亲变得简单；其二是可通过判定parent的值是否为-1来区分根与非根结点。3、哈夫曼树T算法实现的步骤(1)初始化：将T0m-1中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。(2)输入：读入n个叶子的权值存于向量的前n个分量(即T0 n-1)中。它们是初始森林中n个孤立的根结点上的权值。(3)合并：对森林中的树共进行n-1次合并，所产生的新结点依次放人向量T的第i个分量中(nim-1)。每次合并分两步：,在当前森林T0 i-1的所有结点中，选取权最小和次小的两个根结点Tp1和Tp2作为合并对象，这里0p1，p2i-1。将根为Tp1和Tp2的两棵树作为左右子树合并为一棵新的树，新树的根是新结点Ti。具体操作：(i)将Tp1和Tp2的parent置为i;(ii)将Ti的lchild和rchild分别置为p1和p2;(iii)新结点Ti的权值置为Tp1和Tp2的权值之和。说明：合并后Tpl和Tp2在当前森林中已不再是根，因为它们的双亲指针均已指向了Ti，所以下一次合并时不会被选中为合并对象。4、哈夫曼树T算法实现的程序初始化函数;输入权值函数;选择两个权最小的根结点函数;建立哈夫曼树函数。,/*哈夫曼树初始化函数*/void InitHuffmanT