第6章树和二叉树.ppt

第6章 树和二叉树,本章主要内容 树结构广泛存在,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 赫夫曼树及其应用,6.1 树的定义和基本术语,一、树的定义p118 树(tree)是n(n=0)个结点的有限集，在任意一棵非空树中(1)有且仅有一个特定的称为根（root）的结点；（2）当n1时，其余结点棵分为m(m0)个互不相交的有限集t1,t2,tm,其中每一个集合本身又是一棵树，并且称为根的子树（subtree）。 基本术语p120 二、树的表示法p120 三、树的逻辑结构：非线性结构-层次结构 四、树的基本操作：初始化、建树、清空、求树的深度、找双亲、找孩子、插入、删除、遍历等 五、adt示,张源,族普,子树t1,子树t2,子树t3,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,d,h,i,j,m,(从根到结点的)路径：,孩子结点、双亲结点、 兄弟结点、堂兄弟 祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,任何一棵非空树是一个二元组 tree = （root，f） 其中：root 被称为根结点， f 被称为子树森林,森林：,是 m（m0）棵互 不相交的树的集合,a,root,f,(1) 有确定的根 (2) 树根和子树根之间为有向关系,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (开始结点)(无前驱),根结点 (无前驱),最后一个数据元素 (终端结点)(无后继),多个叶子结点 (无后继),其它数据元素 (一个直接前驱、 一个直接后继),其它数据元素 (一个直接前驱、 多个直接后继),树的表示法,1、树型图表示法： 2、嵌套集合表示法： 3、凹入表表示法： 4、广义表表示法：,广义表表示法,数据对象 d：,d是具有相同特性的数据元素的集合。,若d为空集，则称为空树； 否则: (1) 在d中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集t1, t2, , tm, 其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。,数据关系 r：,基本操作：,查 找 类,插 入 类,删 除 类,root(t) / 求树的根结点,查找类：,value(t, cur_e) / 求当前结点的元素值,parent(t, cur_e) / 求当前结点的双亲结点,leftchild(t, cur_e) / 求当前结点的最左孩子,rightsibling(t, cur_e) / 求当前结点的右兄弟,treeempty(t) / 判定树是否为空树,treedepth(t) / 求树的深度,traversetree( t, visit() ) / 遍历,inittree(&t) / 初始化置空树,插入类：,createtree(&t, definition) / 按定义构造树,assign(t, cur_e, value) / 给当前结点赋值,insertchild(&t, &p, i, c) / 将以c为根的树插入为结点p的第i棵子树,cleartree(&t) / 将树清空,删除类：,destroytree(&t) / 销毁树的结构,deletechild(&t, &p, i) / 删除结点p的第i棵子树,6.2 二叉树,本节主要内容,6.2.1 二叉树的定义,6.2.2 二叉树的性质,6.2.3 二叉树的存储结构,6.2.1 二叉树的定义,一、二叉树的定义p121 二、二叉树的基本形态p123 三、二叉树的逻辑结构：非线性结构-层次结构 四、二叉树的基本操作：初始化、建树、清空、求树的深度、找双亲、找孩子、插入、删除、遍历等 五、adtp121122,二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,e,f,由二叉树的定义知:二叉树只有五种基本形态,n,空树,只含根结点,n,n,n,l,r,r,右子树为空树,l,左子树为空树,左右子树均不为空树,6.2.2 二叉树的性质,性质1、在二叉树的第i层上至多有2i-1个结点（i1）。 性质2、深度为k的二叉树至多有2k-1个结点（k1）。 性质3、对任何一棵二叉树t，如果其终端结点数为n0，度为2的结点数为n2，则：n0=n2+1分析 例 满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。p124 完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且，最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。例 注,性质4、具有n个结点的完全二叉树的深度为：,log2n +1,分析：令二叉树的深度为k，从而， 2k-1-1n 2k-1,深度为k-1 的满二叉 树的结点数,深度为k的 满二叉树 的结点数, 2k-1 n 2k, k-1 log2nk, kn k=,log2n +1,性质5、如果对一棵有n个结点的完全二叉树（其深度为log2n+1）的结点按层序编号（从上到下且每层从左至右），则对任一结点i(1in)，有：示,(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲parent(i)是结点i/2。 (2)如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子lchild(i)是结点2i。 (3)若2i+1n，则结点i无右孩子；否则其右孩子rchild(i)是结点2i+1。 注：可以用数学归纳法证明之，学生自己证明，我们用其结论。,1,2,3,4,5,6,7,8,9,10,11,12,对有n个结点的完全二叉树t从上到下且每层从左至右进行1至n的连续编号,观察编号为i的结点的双亲、左孩子、右孩子的编号情况,注：,由完全二叉树的定义有以下结论： （1）叶子结点只可能在层次最大的两层上出现（最下两层）； （2）满二叉树一定是完全二叉树，反之不然； （3）完全二叉树中，若某结点无左孩子，则该结点一定无右孩子； （4）对任一结点，若其右分支下的子孙的最大层次为k，则其左分支下的子孙的最大层次必为k或k+1。,例、判定以下树中，哪些是满二叉树，哪些是完全二叉树。,是：完全二叉树，且是满二叉树,不是完全二叉树,不是完全二叉树,是完全二叉树,例1、设高度为h的二叉树t无度为1的结点，则二叉树t至少有多少个结点？至多有多少个结点？若二叉树t的叶子总数为m，则二叉树t的结点总数为多少？,分析： （1）由于二叉树t无1度结点，从而当从第二层至第h层每层只有两个结点时，t的总结点数最少，而第一层只有树根，从而，t至少有：2(h-1)+1=2h-1个结点； （2）由二叉树的性质2知，t至多有2h-1个结点； （3）设n0、n1、n2、n分别为t的叶子结点数、1度结点数、2度结点数、结点总数，则有：n0=m，n1=0 由二叉树的性质3有：n0=n2 +1，有n2= n0-1 从而，n=n0+n1+n2=n0+0+n0-1=2n0-1=2m -1,分析：,分别用n0、n1、n2表示二叉树t中的度为0、1、2的结点数，依题意知n0=n，又二叉树t中所有非叶子结点都有左、右子树，从而t中无度为1的结点，即n1 =0，由性质3有n2= n0-1= n-1 ，从而二叉树的结点总数为：n0+n1+n2=n+0+n-1=2n-1,用数学归纳法证明之 （1）当n=1时，l1=1，显然有：,（2）设n=m-1时结论成立，即,下面证明n=m时结论成立 不失一般性，设在hi层的叶子结点上加上两个孩子结点，则叶子结点总数加1，此时有：,成立,=,从而结论成立,=1,设n1为二叉树t度为1的结点数，n为结点总数，则有：n=n0+n1+n2 考察二叉树的分支数： 除了根结点外，其余每个结点都有一个分支进入，设b为分支总数，则n=b+1。由于这些分支是由度为1或2的结点发出的，所以有b=n1+2n2，于是得： n=n1+2n2+1 于是有： n0+n1+n2=n1+2n2+1 化简得： n0=n2 +1,分析：,6.2.3 二叉树的存储结构二种,一、顺序存储结构：p126 优、缺点 二、链式存储结构：p126 1、结点结构：示 2、 c语言形式描述p127,二叉树的二叉链表存储表示 -定义结点结构,用c语言形式描述为:,即,typedef struct bitnode telemtype data; struct bitnode *lchild,*rchild; bitnode,*bitree;,有了存储结构，便可以讨论基本操作的实现了，进入下一节内容,（c）,二叉树的顺序存储结构,对于完全二叉树，可对其结点按层序从上到下每层从左到右依次进行0至n-1的连续编号，并用一数组进行存储：将编号为i的结点存储于下标为i的存储单元中。,（d）,对于非完全二叉树，可先为其添加若干虚结点，将其补充为完全二叉树后，再按完全二叉树的方式进行顺序存储。,单支树,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况,左指针域,右指针域,数据域,存储指向左 孩子的指针,存储指向右 孩子的指针,存储结点 本身信息,左指针域,右指针域,数据域,双亲指针域,三叉链表树结点结构,lchild,data,rchild,示,二叉链表树结点结构,示意图见p127,二叉链表树直观示意图,t,a,b,d,e,g,h,i,c,f,注,二叉链表树t为空的条件:t= =null,注：在含n个结点的二叉链表树中有n+1个空链域,分析： 设n0、n1、n2、n分别为t的叶子结点数、1度结点数、2度结点数、结点总数，则有： n=n0+n1+n2， n0=n2 +1 又，在二叉链表树中，每个叶子结点提供两个空链域，每个1度结点提供一个空链域，而2度结点不提供空链域，从而， 空链域数= 2n0+n1=(n0+n1+n2)+(n0-n2 )=n +1,对完全二叉树较为适用，它存储简单、访问方便，但对于一般的二叉树在空间上浪费较大,二叉树的顺序存储结构的优、缺点：,6.3 遍历二叉树和线索二叉树,本节主要内容:,6.3.1 遍历二叉树,6.3.2 线索二叉树,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次,问题的提出,“访问”的含义可以很广，如：输出结点的信息等,6.3.1 遍历二叉树,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题,对“二叉树”而言，可以有三条搜索路径,1先上后下的按层次遍历 2先左（子树）后右（子树）的遍历 3先右（子树）后左（子树）的遍历,设 访问根结点 记作 v 遍历根的左子树 记作 l 遍历根的右子树 记作 r 则可能的遍历次序有 前序 vlr 逆前序 vrl 中序 lvr 逆中序 rvl 后序 lrv 逆后序 rlv 层次遍历：从上到下，从左到右,该六种次序可分为两类,介绍前三种,1、二叉树的遍历：p128p129 -前序、中序、后序、层次遍历例 中序非递归算法 2、二叉链表树的建立p131 按先序生成树：生成根结点、建左子树、建右子树。算法 3、例题。 4、表达式的二叉树表示法： （对其进行遍历则得到相应的前缀、中缀、后缀表示法）p129,分析：对于每一棵二叉树，对其进行先序、中序、后序遍历得到该树的先序、中序、后序序列，反之，由二叉树的先序、中序、后序序列中的任意两个序列，便可以唯一地确定一棵二叉树 下面以先序、中序序列为例进行说明,例1、已知一棵二叉树t的先序和中序序列如下： 先序序列：abhfdeckg 中序序列：hbdfaekcg 试作出该二叉树t,二叉树的先序序列：,二叉树的中序序列：,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列 中序序列,让学生自己读下页的求t的过程,前序序列abhfdeckg 中序序列hbdfaekcg,例2：一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树（西安电子科技术大学2000年硕士研究生招生试题） 先序： b f iceh g； 中序：d kfia ejc ； 后序： k fbhj g a；,分析：将所求的二叉树记为t,先序： b f iceh g； 中序：d kfia ejc ； 后序： k fbhj g a；,对二叉树t进行先序遍历时，第一个被访问的结点一定是t的根，而后序遍历时最后一个被访问的结点一定是t的根，由所给的后序序列知t根为a，即先序序列中的第一个空应填a；,a,对二叉树t进行中序遍历时，根结点将中序序列分为两部分：其中，根结点的前面部分为二叉树的左子树的中序序列，后面部分为二叉树的右子树的中序序列。从而，t的左子树中序序列为： d kfi，t的右子树中序序列为： ejc ；,由的结论知，t的先序序列中从第二个结点开始的长度为5的子列（b f i）为t的左子树先序序列，其后的长度为5的子列（ceh g）为t的右子树先序序列；, 同理，t的后序序列中从第一个结点开始的长度为5的子列（ k fb）为t的左子树后序序列，其后的长度为5的子列（hj g ）为t的右子树后序序列；,重复上述过程便可求得该问题的解： 先序序列中依次填：adkj 中序序列中依次填：bhg 后序序列中依次填：diec,例3、试分别找出满足下列条件的所有二叉树 （1）前序序列和中序序列相同； （2）中序序列和后序序列相同； （3）前序序列和后序序列相同。,分析：（1）为空或任一结点均无左子树的非空二叉树；（2）为空或任一结点均无右子树的非空二叉树；（3）为空或仅有一个结点的二叉树；,例4、试设计四个算法，分别计算： （1）二叉树中结点个数； （2）二叉树的深度； （3）二叉链表树中各结点的层次数 （4）二叉链表树的叶结点数。 （最后一问为中科院计算所1997研究生招生试题）,例：遍历以下各树，写出各结点被访问的次序序列,先序：a、b、d、h、i、e、j、k、c、f、l、m、g、n、o 中序：h、d、i、b、j、e、k、a、l、f、m、c、n、g、o 后序：h、i、d、j、k、e、b、l、m、f、n、o、g、c、a 层次：a、b、c、d、e、f、g、h、i、j、k、l、m、n、o,试给出先序、中序、后序遍历以下各树时结点被访问的次序序列,6.4 树和森林,本节主要内容:,6.4.1 树的存储结构,6.4.2 森林与二叉树的转换,6.4.3 树和森林遍历,6.4.1 树的存储结构,一、双亲表示法 利用双亲的唯一性-顺序存储 1、结点结构：,数据域,双亲结点位置域,2、形式描述p135,3、优、缺点：找根、双亲特别方便，只需要常量时间，但找孩子结点需搜寻数组,二、孩子表示法p135136,三、孩子兄弟表示法 p136示,二叉链表作树的存储结构,左指针域,右指针域,数据域,指向该结点的第一个孩子结点,指向其下一个兄弟结点,结点本身的信息,firstchild,data,nextsibling,二叉链表树结点结构,示,t,a,b,d,e,g,h,i,c,f,r,树的孩子兄弟表示法,1、树转换为二叉树方法 2、森林转换为二叉树方法 3、二叉树转换为森林方法,6.4.2 森林与二叉树的转换,树转换为二叉树,方法与步骤： 1、在所有的兄弟结点之间加一连线 2、对每一个结点，除了保留与其最左边的一个孩子的连线外，去掉该结点与其它孩子的连线 3、将所得图形顺时针旋转450得到所求的二叉树例 本质：右兄弟作右孩子,例、将以下树转换为相应的二叉树,t1,例、将以下树转换为相应的二叉树,森林转换为二叉树,方法与步骤： 1、依次将各树转换为二叉树 2、将各树的根彼此视为兄弟，将森林转换为二叉树例,例、将以下森林转换为相应的二叉树,分析：（1）先将各树依次转换为二叉树，得,（2）将各树的根彼此视为兄弟，得二叉树如下：,二叉树转换为森林,方法与步骤： 1、若结点y 的左孩子是x ，则把x的右孩子、右孩子的右孩子、，都与y用线连起来（右孩子还原为右兄弟）； 2、去掉所有双亲到右孩子的连线例,例、将以下二叉树转换为相应的森林,t1,t3,t2,6.4.3 树和森林遍历,一、树的遍历p138 1、先根遍历：先访问根结点，然后依次先根遍历根的各子树例。 2、后根遍历：先依次后根遍历每棵子树，然后再访问根结点例。,二、森林的遍历p139 1、先序遍历：依次先序遍历森林中的各树2、中序遍历：依次中序遍历森林中的各树例,例、遍历树,t1的先序序列：a、b、e、k、l、f、c、g、d、h、m、i、j,t1的后序序列: k、l、e、f、b、g、c、m、h、i、j、d、a,例、遍历以下森林f,先序序列：a、b、e、k、l、f、c、g、d、h、m、 i、j、m、n、q、o、p、r、s、u、v、w、t,中序序列: k、l、e、f、b、g、c、m、h、i、j、 d、a、q、n、o、p、m、u、v、w、s、t、r,推导的规则(根据森林与二叉树之间转换规则可知):,森林的先序和中序遍历与其对应的二叉树的先序与中序遍历得到的结果是相同的。 同理，树的先根和后根遍历可借用二叉树的先序和中序遍算法实现之。,6.6 赫夫曼树及其应用,本节主要内容：,6.6.1 赫夫曼树,6.6.2 赫夫曼编码,例：编制一个将百分制转化为五分制的程序。,if(a60) b=“bad”; else if(a70) b=“pass”; else if(a80) b=“general”; else if(a90) b=“good”; else b=“excellent”;,设计的程序是否是最优的呢？,表一、学生成绩在五个等级上的分布情况,假设现有10000个输入数据，则需要进行31500次比较,6.6.1 赫夫曼树,一、基本术语：p144 结点间路径、路径长度、树的路径长度、结点的带权路径长度、树的带权路径长度、赫夫曼树（最优二叉树）例,二、赫夫曼树的构造算法p145 构造算法 例 性质,wpl=38,wpl=36,wpl=43,wpl=46,wpl=35,例、计算如下图所示的二叉树的带权路径长度,哈夫曼树中，权值大的结点离根最近,赫夫曼算法,根据给定的n个权值w1, w2 ,wn ，构成n棵二叉树的集合f=t1,t2 ,tn ，其中每棵二叉树ti中只有一个权为wi的根结点,其左右子树均空。 在f中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在f中删除这两棵树，同时将新得到的二叉树加入f中。 重复(2) 和(3)，直到f只含一棵树为止，这棵树便是赫夫曼树。,例、试构造出有5个叶结点，且权值分别为：6，7，5，9，3的赫夫曼树。,分析：,（1）初态,6,9,7,5,3,8,（2）,13,（3）,（4）,30,17,（5）,赫夫曼树的性质,由赫夫曼树的构造算法知，赫夫曼树具有以下性质：,1、赫夫曼中无度为1的结点； 2、含n个叶结点的赫夫曼树共有2n-1个结点。,最优m叉树,一、定义：在所有含n个叶子结点、并带相同权值的m叉树中，带权路径长度wpl最小的树称为“最优m叉树”，亦称为“赫夫曼树” (huffman tree),二、构造算法：以构造最优三叉树为例讲解 例、试构造出有9个叶结点，且权值分别为：7，4，2，9，3，15，1，11，21的最优三叉树。,分析：,（1）初态,（2）,6,（3）,17,（4）,（5）,73,最优三叉树,注：1、对于含n个叶结点的最优三叉树有以下情况：若n=2m-1，则可直接按上述方式构造，对于其它情况需补充虚结点，具体如何补，请各位同学自己考虑；,6.6.2 赫夫曼编码,设给出一段报文 cast cast sat at a tasa 字符集合是 c, a, s, t ，各个字符出现的频度(次数)是 w 2, 7, 4, 5 若给每个字符以等长编码 a : 00 t : 10 c : 01 s : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36,若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度 a : 0 t : 1 c : 01 s : 10 它的总编码长度为 7*1+5*1+( 2+4 )*2 = 24 比等长编码的情形要短,字符集合是 c, a, s, t ，各个字符出现的频度(次数)是 w 2, 7, 4, 5 ,无法翻译：“0101”,任何一个字符的编码都不是同一 字符集中另一个字符的编码的前缀,a : 0 b : 10 c : 110 d : 111,前缀编码,如何得到使电文总长最短的前缀编码呢？,假设每种字符在电文中出现的次数为wi，其编码长度为li，则电文总长为 wi * li 。 对应到二叉树上，若置wi为叶子结点的权值， li为从根到叶子结点的路径长度。则wi * li恰为二叉树的带权路径长度。 因此，设计电文总长最短的二进制前缀编码问题，就转化为以n种字符出现的频率为权，设计一棵赫夫曼树的问题。,利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短p146,以各字符出现概率2,7,4,5为各叶结点权值，建立赫夫曼树，得赫夫曼编码(不等长编码),a:0 t:10 c:110 s:111,总编码长度为 7*1+5*2+(2+4)*3=35 总编码长度正好等 于赫夫曼树的带 权路径长度wpl,例、已知某电文中共出现10种不同的字母，每个字母出现的频率分别为：a：8，b：5，c：3，d：2，e：5，f：23，g：9，h：11，i：2，j：35，现在对这段电文用三进制编码（即码字由0，1，2组成），问电文编码的总长度至少有多少位？请画出相应的图。,分析：,以n=10个字母的频率为权的最优三叉树如下：,0,0,0,0,1,1,1,1,2,2,2,2,2,1,得对应字母的最优前缀码如下: a:01,b:212,c:210,d:2111,e:00,f:22,g:02,h:20,i:2112,j:1 从而，所给电文编码总长度至少为: 82+53+33+24+72+232+92+112+24 +351=191位,对所得的三叉树的左分枝标识0，右分枝标识为2，其它分枝标识为1,一、赫夫曼树和赫夫曼编码的存储结构p147,二、赫夫曼编码算法p147,type struct unsigned int weight; unsigned int parent,lchild,rchild; htnode,*huffma