单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构与算法分析,SCU,数据结构与算法分析,A Practical Introduction toData Structures and Algorithm Analysis,陈 星,第,5,章 二叉树,非线性结构和树,例,:,家中的族谱,能否用线性表来表示,?,树,:,一种简单的非线性结构,数据元素之间具有层次特性。,普通树的结构太复杂,难以计算机实现。因此应用中常限制树,的每个结点只能有最多两个子结点，称为二叉树。,5.1,定义及主要特性,二叉树：由结点的有限集合组成，这个集合或者为空，或者,由一个根结点及两棵不相交的二叉树组成，这两棵二叉树分别称,为这个根的左子树和右子树。这两棵子树的根称为此二叉树根结,点的子结点。,二叉树特点：,(1),、非空二叉树只有一个根结点。,(2),、每个结点最多有两棵子树。,二叉树的一些概念,结点、根结点,父结点、子结点、兄弟结点、表兄弟结点,子树、左子树、右子树,路径、路径的长度,祖先、子孙,结点的深度、层数、树的高度,叶结点、分支结点（或称内部结点）,满二叉树和完全二叉树,满二叉树：,每一个结点或者是一个分支结点，并恰,有两个非空子结点；或者是叶结点。（即二叉树中不存在,只有一个子结点的结点）,完全二叉树：,从根结点起每一层从左到右填充。（即,一棵高度为的完全二叉树除,d-1,层外，每一层都是满的，,且底层叶结点集中在左边的若干位置上）,满二叉树（非完全二叉树）完全二叉树（非满二叉树）,5.1.1,满二叉树定理,定理,5.1,满二叉树定理：,非空满二叉树的叶结点数等于其分支结点数加,1,。,任意二叉树，叶结点数等于有两个子结点的分支结点数加,1,。,？,5.1.1,满二叉树定理,定理,5.1,满二叉树定理：,非空满二叉树的叶结点数等于其分支结点数加,1,。,任意二叉树，叶结点数等于有两个子结点的分支结点数加,1,。,证明：,设非空二叉树中，结点为,n,个（子结点数为,0,1,2,的结点分别为,n0,n1,n2,）,分支（边）数为,m,n=n0+n1+n2 (1),考虑每个结点对应的进入分支，除根结点外，每个结点都有且只有一个父结点，对应一个分支，故有：,m=n-1 (2),考虑每个结点对应的射出分支。每个结点对应的分支数等其子结点个数，故有：,m=n1+2 n2 (3),联立（,1,）（,2,）（,3,）式求解得：,n0,n2,1,定理,5.2,一棵非空二叉树空子树的数目等于其结点数目加,1,。,证明：,设非空二叉树中，结点为,n,个，其中子结点数为,0,1,2,的结点分别为,n0,n1,n2,，有：,n=n0+n1+n2 (1),对二叉树，叶子结点有两个空子树，子结点为,1,的结点,有,1,个空子树，因此二叉树空子树的数目,m,应有：,m=2*n0+n1,（,2,）,根据满二叉树定理可得：,n0=n2+1 (3),代入（,2),式得：,m=n0+n2+1+n1,=n+1,5.1.2,二叉树的抽象数据类型,Elem,void setVal(const Elem,inline BinNode*left()const,return lc;,void setLeft(BinNode*b),lc=(BinNodePtr*)b;,inline BinNode*right()const,return rc;,void setRight(BinNode*b),rc=(BinNodePtr*)b;,bool isLeaf(),return(lc=NULL),；,5.2,周游二叉树,按照一定顺序访问二叉树的结点，称为一次周游或遍历。对,每个结点都进行一次访问并将其列出，称为二叉树的枚举。,二叉树遍历（,Traversals,）的算法是树形结构中其它算法的基,础，实际上是将非线性结构的二叉树转化为线性序列。,遍历一个二叉树就是不重复地访问二叉树中的所有结点。,若加以“先左后右”的限制，二叉树的遍历有三种：,1,、,LDR,：中序遍历（中根遍历，,Inorder,）。左根右,2,、,LRD,：后序遍历（后根遍历，,Preorder,）。左右根,3,、,DLR,：前序遍历（前根遍历，,Postorder,）。根左右,Tree traversals using“flags”,The order in which the nodes are visited during a tree traversal can be easily determined by imagining there is a“flag”attached to each node,as follows:,To traverse the tree,collect the flags:,preorder,inorder,postorder,A,B,C,D,E,F,G,A,B,C,D,E,F,G,A,B,C,D,E,F,G,A B D E C F G,D B E A F C G,D E B F G C A,课堂练习,写出下列二叉树进行前序、中序和后序遍历后得到的结点序列：,1.,对于下图所示的二叉树，它有多少个分支结点，高度为多少，写出它的前序周游和后序周游序列。,2.,若某二叉树的前序周游序列为（,A B D E C F G,），中序周游序列为（,D B E A F C G,），请画出该二叉树。,课堂练习,5.3,二叉树的实现,5.3.1,使用指针实现二叉树,每个结点包含一个数据区和两个指向子结点的指针。,这种方式常称为二叉链表（二重链表）。每个结点包括：,1,、值域。,2,、左指针域（指向左子树）。,3,、右指针域（指向右子树）。,5.3.2,空间代价,结构性开销：为实现数据结构而花费的空间，即那些不用,来存储数据记录的空间。,如果,n,个结点的二叉树，一个指针所占空间为,p,，而一个数据,值所占空间为,d,，则整个二叉树的结构开销为,2pn,。因此结构性,开销所占比例为：,2p/(2p+d),对此基于指针的二叉树（二叉链表），有一半的指针被浪费,在存储,NULL,值上。,如果只是叶结点存储数据，那么结构性开销在全部开销中的,比较取决于二叉树是否“满”。对非满二叉树，结构性开销将占,很大比例。,5.3.3,使用数组实现完全二叉树,完全二叉树，每一层（除底层）是满的，且最底层的结点是,从左到右填充。,对完全二叉树的结点，可以从上到下，从左到右地编号，结,点的位置可以完全由其序号确定。即可以由序号推导出结点在,二叉树中位置。,因此可以用,n,个元素的数组来保存,n,个结点的完全二叉树，,不存在结构性开销。,对完全二叉树，若某结点的序号为,r,，则,其父结点的序号为,其左、右子结点的序号分别为：,2r,1,、,2r+2,Position,0,1,2,3,4,5,6,7,8,9,10,11,Parent,-,0,0,1,1,2,2,3,3,4,4,5,Left Child,1,3,5,7,9,11,-,-,-,-,-,-,Right Child,2,4,6,8,10,-,-,-,-,-,-,-,Left Sibling,-,-,1,-,3,-,5,-,7,-,9,-,Right Sibling,-,2,-,4,-,6,-,8,-,10,-,-,5.4,二叉查找树,无序表进行数据查找的检索时间为,（,n,），数据量大时太慢。,而有序顺序表可以将数据检索时间缩短为,（,logn,），但数据插,入和删除操作时间代价大。,？,能否找到一种记录插入和检索操作都很快的数据结构呢？,答案：二叉查找树（又称二叉排序树、二叉检索树）,二叉查找树：对二叉树中任意一个值为,K,的结点，其左子树中任意一个结点的值都,小于,K,，而右子树中任意一个结点的值都,大于或等于,K,。,特点：将二叉查找树的中序遍历（周游）序列是一个从小到大排列的有序序列。,课堂练习：列出以上二叉查找树中序遍历序列。,二叉查找树的基本操作：,数据查找、结点插入、二叉查找树构建、结点删除,结点查找,：从根结点开始，在二叉查找树中检索值,K,。若结点值为,K,，则检索结束；若,K,小于结点值，则在左子树中检索；若,K,大于结点值，则在右子树中检索。以此类推，一直到,K,被找到或检索到叶结点为止。,结点插入：,采用结点查找方法在二叉查找树中找到新结点的插入位置。,二叉查找树构建：,用结点插入方法将所有元素插入到二叉查找树。,二叉查找树的结点删除,首先通过结点查找找到欲删除的结点。如果该结点：,没有子结点：直接删除（其父结点指向它的指针改为,NULL,）。,有一个子结点：其父结点指向它的指针改为指向其子结点。,有两个子结点：用其右子树中最小值代替该结点。,即从欲删除结点出发至右子树，沿左边的链不断下移，直到没有左边的链可继续下移为止，此时结点即为值最小的结点,(,记为,S),，用,S,的值代替欲删除结点的值，再删除结点,S,。,？为什么用右子树中最小值，而不用左子树中最大值代替欲删除结点的值？,如何删除结点,S,？,二叉查找树的效率分析：,查找、插入、删除的时间代价都取决于树的高度。,当二叉树平衡（即除最后一层外的每层结点数量尽可能为,满，且每个结点的左右子树高度尽可能相同）时，树的高度最,小，约为,logn,。平衡二叉查找树的查找、插入和删除操作的平,均时间代价为,（,logn,）。,如果二叉树完全不平衡，即成一个链表形状，高度为,n,，操,的时间代价为,（,n,）。,创建一棵平衡二叉查找树的时间代价为,（,nlogn,），而创,建一棵完全不平衡二叉树的时间代价为,（,n,2,）。,不论二叉树的形状如何，周游二叉树的时间代价为,(n),。,5.5,堆与优先队列,应用中，常需要找出“最重要”目标。数学上就是查找队列中最大（最小）值问题。,优先队列：按重要性或优先级来组织的队列。,堆：一棵完全二叉树。用数组来实现和存储。,最大值堆：任意一个结点的值大于或等于其任意一个子结点的值。即,堆中最大值在根结点,。,最小堆：任意一个结点的值小于或等于其任意一个子结点的值。即,堆中最小值在根结点,。,堆与二叉查找树的比较：二叉排序树实现了结点的完全排序，而堆只实现了局部排序。,？,讨论！,堆与二叉查找树的比较：,？,堆,二叉查找树,堆与二叉查找树的比较：,？,堆,二叉查找树,二叉查找树实现了结点的完全排序，而堆只实现了局部排序。,堆结构和构造过程的非唯一性。,(a)(4-2)(4-1)(2-1)(5-2)(5-4)(6-3)(6-5)(7-5)(7-6),(b)(5-2),(7-3),(7-1),(6-1),堆的构建,关键操作：假设二叉树根结点的左右子树已是堆，调整该二叉树为堆。,1,、将根结点与其左、右儿子结点比较，若不满足堆的条件，则根结点与左右儿子结点中大者进行交换。即根结点不断地向下层移动。,2,、对交换后的左或右子树重复过程,1,。,3,、直到满足堆的条件或调整到叶结点为止。,堆的构建：对一个二叉完全树，从最后一个分支结点开始，,到根结点，逐个结点地应用上述操作。,堆构建的时间代价分析,堆 二叉查找树,最坏时间复杂度：,(n),(n,2,),平均时间复杂度：,(nlogn),不需移动,移动一层,堆中最大元素的删除,当移去最大元素（根结点）后，将最后一个元素移到根结点，再调 整为堆。,删除最大元素的平均时间代价和最差时间代价：,(logn),5.6 Huffman,编码树,文件存储时，文件中每个字符必须做二进制编码，如何,通过编码压缩文件的存储空间,？,固定长度编码方法：,如：,ASCII,码 每个字符用,8,位二进制编码。,特点：如果每个字符使用频率相等，则固定长度编码是空间效率最高的方法。,变长编码法：,如：,Huffman,编码 出现频率高的字符用较短的编码，而出现频率低的字符用较长的编码。,5.6.1,建立,Huffman,编码树,Huffman,树是一种满二叉树，每个叶结点对应于一个字符，,叶结点的权重