《算法与数据结构》教学课件-第5章 二叉树与树--C语言描述（第2版）张乃孝编著.ppt

5 二叉树和树,5.1 二叉树及其抽象数据类型 5.2 二叉树的周游 5.3 二叉树的实现 5.4 二叉树的应用 5.5 树及其抽象数据类型 5.6 树的实现 5.7 树林,线性结构和非线性结构。 树形结构是以分支关系定义的层次结构，在现实世界中广泛存在，在计算机领域中也有广泛应用。 本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系。,5.1 二叉树及其抽象数据类型,5.1.1 基本概念 5.1.2 主要性质 5.1.3 抽象数据类型,二叉树： 它是结点的有限集合，这个集合或者为空集 或者由一个根及两棵不相交的分别称作这个根 的“左子树”和“右子树”的二叉树组成。 它的每一个结点至多有两棵子树，并且子树 有左右之分，不能随意颠倒。,5.1.1 基本概念,二叉树的基本形态：,左子树,右子树,右子树,左子树,（1）空二叉树,（2）只有一个根结点,（3）有根结点 和左子树,（4）有根结点 和右子树,（5）有根结点 和左，右子树,父结点，左（右）子结点，边 若结点x是二叉树中某一棵子树的根结点，结点y是x的左（右）子树的根，则称x是y的父结点；y是x的左（右）子结点；有序对称作从x到y的边。 例如树t中，c是e的父结点，e是c的子结点，是从c到e的边,兄弟结点 具有同一父结点彼此称作兄弟。 树t中b，c互为兄弟，d，e互为兄弟。,祖先，子孙 若结点y在以结点x为根的一个子树中，且yx，则称x是y的祖先，y是x的子孙。 例如树t中，a是其它各结点的祖先；c是d,e,f的祖先。,路径，路径长度 如果x是y的一个祖先，又有xx0，x1，xny，满足xi（i0，1，n-1）为xi+1的父结点，则称x0，x1，xn为从x到y的一条路径。n称为这条路径的长度。 例如树t中a，c，d，f是从a到f的一条路径，其长度为3。,结点的层数 规定根的层数为0，其余结点的层数等于其父母结点的层数加1。 如t中，0层的结点是a，1层的结点有b，c，3层的结点是f。,二叉树的高度 树中结点的最大层数称为二叉树的高度。 例如树t中，树的深度为3。,结点的度数 结点的非空子树个数叫作结点的度数。 例如t中a,b,c,d,e,f的度数分别为2,0,2,1,0,0,树叶、分支结点 左（右）子树均为空的结点称作树叶；否则称作分支结点。 例如树t中b，e，f都是树叶，其余结点都是分支结点。,满二叉树：如果一棵二叉树的任何结点或者是树叶，或者有两棵非空子树，则此二叉树称作满二叉树。 完全二叉树：如果一棵二叉树只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。完全二叉树不一定是满二叉树。,满二叉树,完全二叉树,扩充二叉树 ： 把原二叉树的结点都变为度数为2的分支结点，也就是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0（树叶）增加两个分支。,新增加的结点用小方框表示，称为外部结点,原来的结点称为内部结点。,外部路径长度e：在扩充的二叉树里从根到每个外部结点的路径长度之和。 内部路径长度i：在扩充的二叉树里从根到每个内部结点的路径长度之和。,性质1. 在非空二叉树的第i层上至多有2i个结点（i0）。 归纳： i=0, 结点数=1=20 . 假设对于j(0j i), 结点数至多有2j . 对于i=j+1, 结点数至多为 2* 2j=2j+1 . 性质2. 深度为k的二叉树至多有2k+1-1个结点（k 0）。 k k m= mi = 2i = 2k+1-1 i=0 i=0 20 + 21 + 22 + 2k,5.1.2 主要性质,性质3. 对任何一棵非空二叉树t，如果叶结点数 为n0，度为2的结点数为n2，则n0=n2+1。 n0+n1+n2 = 所有 结点的度数和+1 = n1+ 2*n2 +1 性质4. 具有n个结点的完全二叉树的深度k为log2n . n=20+21+22+2k-1+mk =2k-1+mk 2k-1n 2k+1-1 2k n 2k+1 k log2n k+1 k= log2n,性质5. 对于具有n个结点的完全二叉树，如果按从上到下和从左到右的顺序对二叉树中的所有结点从0开始到n-1进行编号，则对任意的下标为i的结点，有： 1）如果i=0，则它是根结点，它没有父结点；如果i0, 则它的父结点的下标为 (i-1)/2 ; 2）2i+1 n-1，则下标为i的结点的左子结点的下标为2i1；否则下标为i的结点无左子结点。 3）2i+2 n-1，则下标为i的结点的右子结点的下标为2i2；否则下标为i的结点无右子结点。,性质6 在满二叉树中，叶子结点的个数比分支结点的个数多1。 由于满二叉树中，分支结点度数全部为2；其他结点都是叶子结点。根据性质3， n0=n2+1，可以得到此性质。 性质7 在扩充二叉树中，外部结点的个数比内部结点的个数多1。 由于扩充二叉树都是满二叉树，根据性质6可以得到此性质。 性质8 对任意扩充二叉树，外部路径长度e和内部路径长度i之间满足以下关系：e = i + 2n 其中，n是内部结点的个数。,证明：当n=1时，i=0, e=2, 此等式成立。 设有n个内部结点的扩充二叉树，下式成立。 en=in+2n (1) 对于 n+1 个内部结点的扩充二叉树，去掉一个 作为原来二叉树路径长度为k的内部结点，内部路径长度变为： in=in+1-k (2) 外部路径长度变为：en=en+1-2(k+1)+k= en+1 -k-2 即： en+1= en+k+2 en+1= (in+2n) +k+2= (in+1-k) +2n+k+2= in+1+2(n+1) 代入（1） 代入（2）,a,b,c,e,e,f,5.1.3 抽象数据类型 adt bintree is operations bintree createemptybintree(void) 创建一棵空的二叉树 bintree consbintree(bintreenode root,bintree left,bintree right) 返回一棵二叉树，其根结点是root，左右二叉树分别为left和right,int isnull(bintree t) 判断二叉树t是否为空。 bintreenode root(bintree t) 返回二叉树t的根结点；若为空二叉树，则返回一个特殊值。 bintreenode parent(bintree t,bintreenode p) 返回结点p的父结点；当p为根时，返回一个特殊值。,bintree leftchild (bintree t,bintreenode p) 返回p结点的左子树，当p结点没有左子树时， 返回一个特殊值。 bintree rightchild (bintree t,bintreenode p) 返回p结点的y右子树，当p结点没有右子树时， 返回一个特殊值。 end adt bintree,5.2 二叉树的周游,5.2.1 什么是周游 二叉树的周游(traversing binary tree)： 按某条搜索路径访问二叉树中的所有结点 ，使得每个结点被访问一次且仅被访问一次。,5.2.2 周游的分类 深度优先周游 三种方式： 先根次序 (dlr) 中 根 序 (ldr) 后根次序 (lrd),先根次序： 若二叉树不空，则 （1）访问根结点； （2）先根次序周游左子树； （3）先根次序周游右子树。,访问a 先根次序周游a的左子树 先根次序周游a的右子树,访问a 先根次序周游a的左子树 访问b 先根次序周游b的左子树（访问d） 先根次序周游b的右子树(空操作) 先根次序周游a的右子树 访问c 先根次序周游c的左子树（访问e、g） 先根次序周游c的右子树（访问f、h、i） 先序序列：a b d c e g f h i,中根(对称)次序： 若二叉树不空，则 （1）中根次序周游左子树； （2）访问根结点； （3）中根次序周游右子树。,中根次序周游a的左子树 访问a 中根次序周游a的右子树,中根次序周游a的左子树 中根次序周游b的左子树（访问d） 访问b 中根次序周游b的右子树(空操作) 访问a 中根次序周游a的右子树 中根次序周游c的左子树（访问e、g） 访问c 中根次序周游c的右子树（访问h、f、i） 中序序列：d b a e g c h f i,后根次序： 若二叉树不空，则 （1）后根次序周游左子树； （2）后根次序周游右子树； （3）访问根结点。,后根次序周游a的左子树 后根次序周游a的右子树 访问a,后根次序周游a的左子树 后根次序周游b的左子树（访问d） 后根次序周游b的右子树(空操作) 访问b 后根次序周游a的右子树 后根次序周游c的左子树（访问g、e） 后根次序周游c的右子树（访问h、i、f） 访问c 访问a 后序序列：d b g e h i f c a,广度优先周游 若二叉树的高度为h，则从0到h层逐层如下处理：从左到右逐个访问存在的结点。,对右图所示二叉树进行广度优先搜索，得到： a,b,c,d,e,f,g,h,i,如图所示的二叉树 先序序列为： a b d e h k m n c f g 中序序列为： d b h e m k n a f c g 后序序列为： d h m n k e b f g c a,5.2.3 一个例子 如图所示的二叉树是表达式 (a-b)(c+d)的语法结构图。 先序序列为： -ab+cd 中序序列为： a-bc+d 后序序列为： ab-cd+,5.2.4 周游的抽象算法,递归算法 先根次序 中根次序 后根次序 非递归算法 * 先根次序 中根次序 后根次序 1 2,算法5.1 void preorder( bintree t) if (t=null) return; visit(root(t); preorder(leftchild(t); preorder(rightchild(t); ,理解递归算法： 大事化小 小事化了,根据是数学归纳法,算法证明： 设二叉树结点个数为n，则：,算法5.1 void preorder( bintree t) if (t=null) return; visit(root(t); preorder(leftchild(t); preorder(rightchild(t); ,算法证明： 设二叉树结点个数为n，则： 当n=0时，t=null，算法做空操作，算法功能成立。,算法5.1 void preorder( bintree t) if (t=null) return; visit(root(t); preorder(leftchild(t); preorder(rightchild(t); ,算法证明： 设二叉树结点个数为n，则： 当n=0时，t=null，算法做空操作，算法功能成立。 假设ni时, 算法功能成立，则当n=i时： 访问根,算法5.1 void preorder( bintree t) if (t=null) return; visit(root(t); preorder(leftchild(t); preorder(rightchild(t); ,算法证明： 设二叉树结点个数为n，则： 当n=0时，p=null，算法做空操作，算法功能成立。 假设ni时, 算法功能成立，则当n=i时： 访问根 周游根的左子树,左子树中结点个数i，根据归纳假设算法功能成立,算法5.1 void preorder( bintree t) if (t=null) return; visit(root(t); preorder(leftchild(t); preorder(rightchild(t); ,算法证明： 设二叉树结点个数为n，则： 当n=0时，p=null，算法做空操作，算法功能成立。 假设ni时, 算法功能成立，则当n=i时： 访问根 周游根的左子树 周游根的右子树,右子树中结点个数i，根据归纳假设算法功能成立,算法5.1 void preorder( bintree t) if (t=null) return; visit(root(t); preorder(leftchild(t); preorder(rightchild(t); ,算法5.2 二叉树中序周游的递归算法 void inorder(bintree t) if (t=null) return; inorder(leftchild(t); visit(root(t); inorder(rightchild(t); ,算法5.3 二叉树后根次序周游的递归算法 void postorder(bintree t) if (t=null) return; postorder(leftchild(t); postorder(rightchild(t); visit(root(t); ,广度优先周游 算法5.8 广度优先周游二叉树 void levelorder(bintree t) bintree c,cc; queue q=createemptyqueue(); if(t=null) return; c=t; enqueue(q,c);,while(!isemptyqueue(q) c=frontqueue(q);dequeue(q); visit(c); cc=leftchild(c); if(cc!=null)enqueue(q,cc); cc=rightchild(c); if(cc!=null)enqueue(q,cc); ,5.3 二叉树的实现,5.3.1 顺序表示 5.3.2 链接表示 5.3.3 线索二叉树*,用一组地址连续的存储单元按层次次序依次存储完全二叉树的结点。,5.3.1 顺序表示,a,b,c,g,f,e,d,h,i,j,a b c d e f g h i j,下标 0 1 2 3 4 5 6 7 8 9,对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。,图5.11 一般二叉树及其顺序表示,采用顺序表示，类型声明如下： struct seqbintree /* 顺序树类型定义 */ int maxnum; int n; datatype *nodelist; ； typedef struct seqbintree *pseqbintree;,运算的实现 算法5.9 返回下标为p的结点的父结点的下标 int parent_seq(pseqbintree t,int p) if(p=t-n) return 1; return (p-1)/2; 算法5.10 返回下标为p的结点的左子结点的下标 int leftchild_seq(pseqbintree t,int p) if(p=t-n) return 1; return 2*p+1; ,算法5.11 返回下标为p的结点的右子结点的下标 int rightchild_seq(pseqbintree t,int p) if(p=t-n) return 1; return 2*(p+1); ,5.3.2 链接表示,二叉树的链接表示是指用一个链表来存储一棵二叉树，二叉树中的每一个结点用链表中的一个链结点来存储，最常用的链接表示方式是左-右指针表示法（llink-rlink表示法，也称做二叉链表），这种表示法在每个链结点中除存储结点本身的数据外，再设置两个指针字段：llink和rlink，分别存放结点的左子女和右子女所在链结点的存储地址，当结点的某个子女为空时，则相应的指针为空指针。,struct bintreenode; /* 二叉树中结点 */ typedef struct bintreenode *pbintreenode; struct bintreenode datatype info; /* 数据域 */ pbintreenode llink; /* 指向左子女 */ pbintreenode rlink; /* 指向右子女 */ ; typedef struct bintreenode *bintree;,算法5.12 返回结点p的左子结点的地址 pbintreenode leftchild_link(pbintreenode p) if(p=null) return null; return p-llink; 算法5.13 返回结点p的右子结点的地址 pbintreenode rightchild_link(pbintreenode p) if(p=null) return null; return p-rlink; ,t,a,b ,c, e,f, i , h , g , d ,图5.12(a) 二叉树的二叉链表表示,a ,b ,d ,c,e ,f,i ,h ,g ,图5.12(b) 三叉链表表示,t,二叉树的生成,周游是二叉树各种操作的基础，可以在周游过程中进行各种操作，如可以在周游过程中生成结点，从而建立一棵二叉树。,例：输入字符序列： abdcegfhi 建立如图所示的二叉树，其中，表示空结点。 算法 按先根序列创建二叉树,算法 根据先根序列创建二叉树 int i=0; bintree createrest_btree(char *string) /* 递归创建从根开始的二叉树 */ pbintreenode pbnode; char ch; ch=stringi+; if(ch=) pbnode=null; else pbnode =new struct bintreenode; pbnode-info=ch; pbnode-llink=createrest_btree(string);/构造左子树 pbnode-rlink=createrest_btree(string);/构造右子树 return pbnode; ,算法5.1 void preorder( bintree t) if (t=null) return; visit(root(t); preorder(leftchild(t); preorder(rightchild(t); ,算法5.1 void preorder( bintree t) if (t=null) return; coutinfo; preorder(t-llink); preorder(t-rlink); ,/输出二叉树 void disptree1( bintree p) /先序输出p为根的二叉树 if (p=null) coutinfo; disptree1(p-llink); disptree1(p-rlink); ,算法5.1 void preorder( bintree t) if (t=null) return; coutinfo; preorder(t-llink); preorder(t-rlink); ,void disptree2( bintree t) /以括号表示法d(l,r)输出二叉树t if (t=null) return; coutinfo; if(t-llink!=null|t-rlink!=null) coutllink); coutrlink);cout“)“; ,作业 ： p.166 复习题 1、2、8 p.168 算法题 1 补充题： 证明算法5.2二叉树中序周游的递归算法的正确性。 网络课堂测试：5 二叉树与树（1）,5.4 二叉树的应用,5.4.1 堆与优先队列* 5.4.2 哈夫曼树及其应用,5.4.2 哈夫曼树及其应用,扩充二叉树的外部路径长度： 其中：li为从根到第i个外部结点的路径长度，m为外部结点的个数,扩充二叉树的带权的外部路径长度 其中：wi是第i个外部结点的权值，li为从根到第i个 外部结点的路径长度，m为外部结点的个数。,哈夫曼树 假设有一组（无序）实数w1 , w2 , w3 , wm，现要构造一棵以wi（i = 1,2,，m）为权的m个外部结点的扩充的二叉树，使得带权的外部路径长度wpl最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。,例如以下是带有相同权值5,4,7,2,5的四棵二叉树。,2,4,5,7,5,(a),2,4,5,7,5,(b),2,7,5,4,5,(c),2,4,5,7,5,(d),它们的带权路径长度分别为： (a)wpl=21+74+54+53+42=73 (b)wpl=73+ 43+53+53+21=65 (c)wpl=52+ 52+23+43+72=52 (d)wpl=43+ 23+72+52+52=52 其中(c)和(d)树的带权路径长度为最小。可以验证它们恰为最优二叉树。,在解某些判定问题时，利用赫夫曼树可以得到最佳判定算法。 例如，编制一个将百分制转换成五级分制的程序。通常的算法是： if(a60) b=e; else if(a70) b=d; else if(a80) b=c; else if(a90) b=b; else b=a；,在实际生活中，学生的成绩在五个等级上的分布是不均匀的。假设其分布规律如下表示：,e,d,c,a,b,y,y,y,y,n,n,n,n,0.05,0.15,0.4,0.3,0.1,wpl=3.15,c,b,d,a,e,y,y,y,y,n,n,n,n,0.4,0.3,0.15,0.05,0.1,wpl=2.05,c,e,d,n,n,y,y,y,n,0.4,0.15,0.05,wpl=2.2,赫夫曼最早给出了一个带有一般规律得算法，俗称赫夫曼算法。现以最优二叉树为例叙述如下： (1)根据给定得n个权值w1,w2,wn，构成n棵二叉树的集合f=t1,t2,tn，其中每棵二叉树ti中只有一个带权为wi的根结点，其左右子树均空。 (2)在f中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 (3)在f中删除这两棵树，同时将新得到的二叉树假如f中。 重复(2)、(3)，直到f只含有一棵树为止。,哈夫曼树的构造哈夫曼算法,赫夫曼树的构造过程,设 d=d1, d2 , , dn w=w1, w2 , , wn d为要编码的字符集合，w为d中各种字符出现的频率。 要求：（1）编码总长最短； （2）若di dj , di编码不是dj编码的前缀。,哈夫曼树的应用哈夫曼编码,原文：abaaccbadca,电文：0001000010100100111000,编码,电文长度为22,如果希望电文长度尽可能地短，可以考虑让原文中出现次数多的字符采用尽可能短的编码。,原文：abaaccbadca,电文：00000110000110,编码,电文长度为14,？,前缀编码：若要设计长短不等的字符编码，则必须保证任何一个字符的编码都不是另一个字符的编码的前缀。 按前缀编码翻译电文，一定能唯一地被翻译成原文。 可以利用哈夫曼树的原理来设计二进制前缀编码。,用构造哈夫曼树以完成哈夫曼编码： 把d1,d2, dn 作为外部结点，把w1,w2,.,wn作为外部结点的权，构造哈夫曼树。在哈夫曼树中把从每个结点引向其左子女的边上标上0；把从每个结点引向其右子女的边上标上1。 从根结点到叶子结点的路径上的数字拼接起来就是这个叶子结点字符的编码。,原文：abaaccbadca,电文：01100010101100111100,电文长度为20,5.5 树及其抽象数据类型,树的表示方法：,(c ) 凹入表,（a）树形表示,a,b,c,d,e,f,i,j,g,h,(a(b(d)(e(i)(j)(f)(c(g)(h) (d) 嵌套括号表示法,c,d,e,i,j,f,g,h,a,b,(b) 文氏图,树是包括n(n=0)个结点的有限集t。当t非空时，满足： （1）有且仅有一个特别标出的称为根的 结点； （2）除根结点外，其余结点可分为m（m=0） 个互不相交非空的有限集t1, t2, , tm, 其中 每一个集合本身又是一棵树，称为根的子树 (subtree)。,空树：不包括任何结点的树。,5.5.1 基本概念,在树中也可以定义父结点、子结点、路径、路径长度、结点的度、树的度等概念，与前面二叉树中定义相同。,无序树、有序树 对子树的次序不加区别的树叫作无序树。对子树之间的次序加以区别的树叫作有序树。 例如在图5.24中，按无序树的概念t和t是同一棵树，按有序树的概念则是不同的树，本章讨论的树一般是有序树。,结点的次序 在有序树中可以从左到右地规定结点的次序。按从左到右的顺序，我们可以把一个结点的最左边的子结点简称为最左子结点，或直接称为长子，而把长子右边的结点称为次子。 例如在t中结点b是结点a的长子，结点c是结点a的次子，是结点b的兄弟。,5.5.2 抽象数据类型 adt tree is operations tree createemptytree(void) 创建一颗空树 tree constree(node p, tree t1,.,tree ti) 以p为根，t1,.,ti为子树创建一颗树 int isnull(tree t) 判断树t是否为空树,node root(tree t) 返回树t的根结点。 node parent(node p) 返回结点p的父结点。 tree leftchild(tree t) 返回树t的长子树。 tree rightsibling(tree t) 返回树t的右兄弟树。 end adt tree,5.5.3 树的周游,周游的定义:按某一规律系统的访问树中的所有 结点，并使每个结点恰好被访问一次。 周游的方法：按深度方向和按宽度方向周游。 按深度方向（以右图为例） 先根次序 后根次序,先根次序 (1,2,3,5,8,9,6,10,4,7) （1） 访问根结点； （2）从左到右按先根次序周游根结点的每棵子树。 后根次序 (2,8,9,5,10,6,3,7,4,1) （1）从左到右按后根次序周游根结点的每棵子树; （2）访问根结点。,按宽度方向周游 先访问层数为0的结点，然后从左到右逐个访 问层数为1的结点，依此类推，直到访问完树中 的全部结点。 层次序列（1，2，3，4，5，6，7，8，9，10）,5.6 树的实现,struct partreenode /* 树中结点结构 */ datatype info; /* 结点中的元素 */ int parent; /* 结点的父结点位置 */ ; struct partree struct partreenode nodelistmaxnum; /* 存放树中的结点 */ int n; /* 树中结点的个数 */ ; typedef struct partree *ppartree;,5.6.1 父指针表示法,用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下：,优点：a)容易找到父结点及其所有的祖先； b)能找到结点的子女和兄弟； 缺点：a)没有表示出结点之间的左右次序； b)找结点的子女和兄弟比较费事。,改进方法： 按一种周游次序在数组中存放结点,。常见的一种方法是依次存放树的先根序列，如下图：,(a) (b) 图5.5 一棵树的父指针表示,算法5.6 5.7,5.6.2 树的子表表示法,结点表中的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示。 struct edgenode /* 子表中节点的结构 */ int nodeposition; struct edgenode *link; ; struct chitreenode /* 结点表中节点的结构 */ datatype info; struct edgenode *children; ;,子表表示的树结构定义如下： struct chitree /* 树结构 */ struct chitreenode nodelistmaxnum; int root; /* 根结点的位置 */ int n; /* 结点的个数 */ typedef struct chitree * pchitree;,求某个结点的最左子女运算很容易实现，找到结点的全部子女也很容易，但求某个结点的父母和右兄弟实现起来比较费事。另一个缺点是：合并若干个子树构成一个新树时（createtree_chitree操作）也要考虑多个结