2-4树与二叉树(4h)教学内容.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2_4树与二叉树(4h),内容提要,1.树的定义,2.树的基本概念,结点、结点度、根、支、叶结点,子结点、父结点、兄弟结点,树的度、路径、长度、深度,森林、有序、无序,内容提要,3.二叉树,二叉树的定义,二叉树的性质（每层结点个数、总结点数）,二叉树的存储结构:顺序存储、记录数组结构(结点、左子、右子)、链式存储结构（二叉链表三叉链表）,4.特殊二叉树,满二叉树（性质）、完全二叉树（性质）、平衡二叉树、,二叉排序树）,5.二叉树的遍历操作,（前序、中序、后序）,6.树的存储结构:,数组实现方法,（双亲表示法）、链表实现方式（孩子表,示法）、二叉链表实现方式（孩子兄弟表示法）,7.树、森林与二叉树的转换,2.4.1 树的基本概念,南京理工大学,信息学院,经管院,计算机学院,自动化学院,2101,2102,2103,张三,李四,王五,理学院,树形结构是以,分支关系,来定义的层次结构。在客观世界中树形结构广泛存在，并应用于：,人类社会的,族谱、家谱、行政 区域,划分管理；,各种,社会组织机构,；,在计算机领域中，用树表示,源程序的语法结构,；,在OS中，,文件系统、目录,等组织结构也是用树来表示的。,线性结构,树型结构,第一个数据元素,(无前驱),根结点,(无前驱),最后一个数,据元素(无后继),多个叶子结点,(无后继),其它数据元素,(一个前驱、,一个后继),其它数据元素,(一个前驱、,多个后继),一、树的定义1（逻辑结构）,树是一种数据结构：,Tree=（D，R）,其中：,D 是具有相同特性的n个数据元素的集合；,R 是D上逻辑关系的集合，且满足：,在D中存在唯一的称为根的数据元素，没有前件；,D中其余数据元素都有且只有一个前件；,D中所有元素，或有若干个互不相同的后件（子树），或无后件（叶结点）；,则称Tree为树。,树的定义2（递归结构）,树是一个或多个结点组成的有限集合T，有一个,特定结点称为根,，其余结点分为m（m,0）个互不相交的集合T1，T2，,Tm。每个集合又是一棵树，被称为这个根的子树。,树是一种递归结构，可以包含一个结点，该结点包含不相交的树的指针（即子树）。,二、树的表示形式,1.一般形式,2.嵌套形式,3.凹入形式,4.广义表形式,1.一般形式,A,(a),(,a)只有根结点的树,A,B,C,D,E,F,K,L,G,H,I,J,M,(b),(b)一般的树,2.嵌套形式,A,C,G,B,F,E,K,L,M,H,D,J,I,树的表示,(凹入形式),A,B,E,K,L,C,D,F,G,H,I,J,M,树的表示,(广义表形式),(,A,(,B,(,E,(,K,L,),F,),C,(,G,),D,(,H,(,M,),I,J,),),),第一层,第二层,第三层,第四层,二、基本术语,结点,：,包括一个数据元素及若干个指向其它子树 的分支；例如，A，B，C，D等。,叶结点,：,无后件结点为叶结点；如K，L，M。,根结点,：,无前件的结点为根；例如，A结点。,子结点,：,某结点后件为该结点的子结点；例如，,结点A的子结点为B，C，D。,父结点,：,某结点的前件称为该结点的父结点；例 如子结点C，B，D的父结点为A。,基本术语续,兄弟结点：,同一父亲的孩子之间互为兄弟结点 （Sibling）；H，I，J互为兄弟。,路径：,结点的序列n1，n2，,nk(K,1)是一条路径。,长度,：,长度等于路径中结点数-1。,结点度,：,结点拥有的子树数数目；例如，A的度为3。,树的度,：,树中结点的最大度数；上述树的度为3。,子树,：,以某结点的一个子结点为根构成的树称为该 结点的一棵子树。,基本术语续,高度,：,从一结点到叶结点的最长路径为该结点的高度；例如，结点A到M的高度为4。,深度,：,从根结点到某结点的路径为该结点的深度；M的深度为4。,树的深度,：,树的最大层次称为树的深度。,森林,：,0棵或多棵互不相交的树的集合。对树中每个 结点而言，其子树的集合即为森林。,有序,：,如果将树中结点的各子树看成从左至右是有顺序的（即不能互换），则称该树为有序树。否则，称为无序树。,例：,用树结构来表示算术表达式,用树来表示算术表达式的原则如下,：,表达式中的每一个运算符在树中对应一个结点，称为运算符结点。,运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。,运算对象中的单变量均为叶子结点。,例如：,a*（bcd）e*h-g*f（s，t，xy）,2.4.2 二叉树及其基本性质,定义一：,二叉树是另一种树形结构：,Binary_Tree=(D,R),其中：D 是具有相同性质的数据元素的集合；,R 是在D上某个两元关系的集合，且满足：,D,中存在唯一称为根的数据元素，没有前件；,D,中其余元素都有且仅有一个前件；,每个结点至多只有两个子树,；,D中元素，或有两个互不相交后件，或无后件；,左、右子树分别又是一棵二叉树,。,一、定义,定义二,n个结点的集合（n,0）,T 的度,2,所有子树都有左、右之分,（次序不能任意颠到）,二叉树不一定是树,二叉树可以为空；而树则不能为空；,二叉树的结点最多只有两个直接后件,二叉树的结点的子树分左子树和右子树，而树则无此区分。,二叉树是有序树 二叉树的度1,则结点i父结点的编号为i/2(取整)。,（2）完全二叉树,特点:叶结点只可能出现在层次最大的两层上.,深度为k的二叉树T，每层结点数目若满足：,第i层(1,i k-1)上的结点个数均为2,i-1,;,第k层从右边连续缺若干个结点(即只能从右至左不间断缺少);,称这样的树为,完全二叉树,。,O,O,O,O,O,O,（a）完全二叉树,O,O,O,O,O,（b）非完全二叉树,完全二叉树的性质,设完全二叉树的结点,总数为n,，深度为k，某结点编号为i（1,i n），则有：,若i1,则结点i的双亲结点的编号为i/2;,若2*i n,则结点i 的左子结点的编号为2*i,否则,结点i为叶结点;,若2*i+1 n,则结点i 的右子结点的编号为2*i+1,否则,结点i为叶结点.,同理,完全二叉树也可以采用一维树组作为存储结构,且方法完全同满二叉树,只不过n 2,k,-1 罢了,.,i 父结点：int(I/2),，,左子结点：2*i,n,，右子结点：2*i+1,n,（3）二叉排序树定义一,二叉排序树,或者是空二叉树；,或者是：,左子树上所有结点的值均小于根结点的值；,右子树上所有结点的值均大于等于根结点的值；,左、右子树本身又是一棵二叉排序树。,最后一句话可否去掉？,区别与有序树,二叉排序树定义（二）,X是二叉排序树T中的一个结点；,所有的左后裔,小于,X；,所有的右后裔,大于等于,X；,T可以为空树,；,T称为二叉排序树。,10,4,7,12,14,18,14,（a）二叉排序树,14,14,18,4,10,12,13,7,（b）非二叉排序树,2.4.3 二叉树的存储结构 一、顺序存储（一维数组）,用数组存放,存储描述为：,#define MAXSIZE 100；,typedef TElemType SBTreeMAXSIZE；,SBTree bt；,查找不便。,a1 a2 a3 a4 .an,满二叉树存储举例,1,4,3,2,4,7,6,1 2 3 4 4 6 7,1 2 3 4 4 6 7,第i个结点就存放在第i个位置上；,第i个结点（i1)的父结点就存放在第 i/2个位置;,第i个结点（i,2,k-1,-1)的左子结点就存放在第2*i的个位置;右子存放在第2*i+1位置.,二、记录数组结构,存储结构描述:,#define MAXSIZE 100;,typedef struct SBNode,TElemType data;,int Lchild,Rchild;,SBNode;,typedef struct,SBNode nodesMAXSIZE;,SBTree;,举例,1 2 6,2 3 4,3 0 4,4 0 0,4 0 0,6 0 0,结点 左子 右子,1,2,6,3,4,4,特点:,找子方便,找父结点不便,.,三、二叉链表存储结构,data,leftp,rightp,左指针 数据 右指针,A,B,C,D,E,F,G,A,B,D,C,E,F,G,特点:,找子易,找父难.,四、三叉链表存储结构,左指针 数据 父结点 右指针,parent,data,rightp,A,B,C,D,E,F,G,leftp,特点:,找子、找父都易,。,C,A,B,D,E,G,F,2.4.4 二叉树的遍历,遍历（Traversing）是树形结构的一种重要运算，,即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次,。,遍历的方法很多，常用的有：,前序法（PreOrder）,中序法（InOrder）,后序法（PostOrder）,一、前序法（PreOrder）,方法描述：,从根结点a开始访问，,接着访问左子结点b，,最后访问右子结点c。,即：,根,左子,右子,a,b,c,A 访问根结点,B 先序遍历左子树,C 先序遍历右子树,二、中序法（InOrder）,方法描述：,从左子结点b开始访问，,接着访问根结点a，,最后访问右子结点c。,即：,根,左子,右子,a,b,c,A 中序遍历左子树,B 访问根结点,C 中序遍历右子树,三、后序法（PostOrder）,方法描述：,从左子结点b开始访问，,接着访问右子结点c，,最后访问根结点a。,即：,根,左子,右子,a,b,c,A 后序遍历左子树,B 后序遍历右子树,C 访问根结点,二叉树的遍历举例,o,o,o,o,o,o,o,o,o,A,B,C,D,E,F,G,H,I,前序遍历序列：,中序遍历序列：,后序遍历序列：,A B D E G C F H I,D B G E A C H F I,D G E B H I F C A,四、二叉树遍历算法,二叉链表描述,struct tnode,intdata；,struct tnode*lchild，*rchild；,；,typedef struct tnode TNODE;,定义,结点,数据类型,二叉树遍历算法,1.递归、前序法程序,头指针为BT的二叉树的前序遍历。,PROCEDURE PRETRAV(BT),IF(BT0)THEN,OUTPUT(V(BT);,PRETRAV(L(BT);,PRETRAV(R(BT),RETURN,前序遍历二叉树的序列为：,A B C D E F,A,B,C,D,E,F,二叉树遍历算法,1.递归、前序法程序,void preorder_t(TNODE*root),if(root!=NULL),printf(“%d n”,root-data);,if(root-lc!=NULL),preorder_t(root-lc);,if(root-rc!=NULL),preorder_t(root-rc);,前序遍历二叉树的序列为：,A B C D E F,A,B,C,D,E,F,二叉树,遍,历算法,（递归、前序法程序验证）,打印A,取A,.左子(B),打印B,取B,.左子(C),打印C,取C,.左子(空),取C,.右子(空),取B,.右子(D),打印D,取D,.左子(E),打印E,取E,.左子(空),取E,.右子(空),取D,.右子(F),打印F,取F,.左子(空),取F,.右子(空),取A,.右子(空),结束,A,B,C,D,E,F,A,B,C,D,E,F,2.,非递归算法,-前序法,算法步骤:,step1 初始化,置栈为空(top=-1),工作变量p指向root;,step2 p非空(p!=NULL),或栈非空(top!=-1)循环;,step3 p非空循环;访问p,(打印p-data),;,step4 当前元素进栈,p取p-lc,(进左子树),;,执行step3；,step4 p为空，栈非空，则出栈，,p取p-rc,（进右子树）,返回step2.,#define N m,void preorder_t(TNODE*root),TNODE*p,*stackN;int top=-1;,p=root;,while(p!=NULL)|(top!=-1),while(p!=NULL),printf(“%dn”,p-data);,/访问节点,top+;stacktop=p;,/进栈,p=p-lc;,/进左子树,if(top!=-1),p=stacktop;top-;,/出栈,p=p-rc;,/进右子树,A,B,C,D,E,F,二叉树,遍,历算法,（非递归、前序法程序验证）,打印A,A进栈，取A,.左子(B),打印B,B进栈，取B,.左子(C),打印 C,C 进栈，,取C,.左子(空),C 退栈，,取C,.右子(空),B 退栈，,取 B,.右子(D),打印 D,D进栈，取D,.左子(E),打印E,E进栈，取E,.左子(空),E退栈，取E.右子(空),D退,栈，取D,.右子(F),打印F,F进栈，取F,.左子(空),F退栈，取F.右子(空),A退,栈，取A,.右子(空),结束,F,E,D,C,B,A,A,B,C,D,E,F,2.5.5树的应用,一、表达式树,在计算机中对表达式进行分析和计算是一项重要的任务；,表达式可以用有序树表示；,树处理不方便，可以转化为二叉树处理；,转化原则：,有序树T的结点与二叉树BT的结点一一对应；,有序树T中某个结点N的第一个子结点N1,在二叉树BT中为对应结点N的左子结点；,其他子结点，在二叉树BT中被依次链接成一串起始于N1的右子结点。,表达式线性化,将表达式用有序树表示；,将表达式树转化为二叉树；,对对应的二叉树进行中序遍历，其遍历序列即为表达式的,波兰,表达式；,前序遍历为波兰表达式。,表达式处理规则,分析：,每个叶结点为运算对象；,每个非叶结点为运算符；,每个子树对应一个子表达式。,见运算数入栈,见运算符，取两个栈顶元素运算后再压栈；,直到处理结束。,表达式树应用举例,（,6）遇-，a+b*（c-d）,和e/f出栈，运算后再压栈,。,（6）,a+b*（c-d）-e/f,（2）,c-d,b,a,（2）遇-，c d 出栈，,运算后再压栈；,（3）,b*（c-d）,a,（3）遇*，（c-d）和 b 出栈，,运算后再压栈；,（5）,e/f,a+b*（c-d）,（5）遇/，f e 出栈，,运算后再压栈；,（1）,（1）a b c d 入栈,d,c,b,a,a+b*（c-d）,（4）,（4）,（4）遇+，b*（c-d）和a出栈，运算后再压栈,；,a+b*（c-d）,f,e,二、Huffman(哈夫曼）树,（1）Huffman树的定义,（2）构造Huffman树,（3）Huffman编码,（4）Huffman编码的译码,1.Huffman树的定义,Huffman树也称为最优树，是一类带权路径最短的二叉树。,树的带权路径长度定义为：,WPL =w,k,L,k,k=1,n,其中：,n 是树中叶结点的个数,w,i,是第i个结点的权值,L,i,是第i个结点的路径长度,Huffman树举例,以下有三棵树：,（a）,a,b,c,d,7,4,2,4,WPL,a,=7x2+4x2+2x2+4x2,=34,（b）,a,c,b,d,7,4,2,4,WPL,b,=7x3+4x3+2x1+4x2,=43,（c）,a,b,c,d,7,4,2,4,WPL,c,=,7x1+4x2+2x3+4x3,=33,事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。,应用举例,由统计规律可知，考试成绩的分布符合正态分布：,-1,1,0,分数 059 60 69 70 79 80 89 90 100,比例数 0.06 0.14 0.40 0.30 0.10,根据正态分布规律，在,60,89分之间的同学占84%，而不及格和优秀成绩的同学是少数。,将百分制转换成五分制,判定树比较：,a60?,a70?,a80?,a90?,不及格,及格,中等,良好,优秀,Y,Y,Y,Y,N,N,N,N,不及格,中等,(A),a80?,a70?,a90?,a60?,优秀,良好,中等,及格,不及格,Y,Y,Y,N,N,N,N,Y,Y,(B),若输入1万个数据，按A的判定过程进行操作，约需比较3.2万次，而按B比较,则仅需2.2万次。,2.构造Huffman树,构造Huffman树算法步骤：,1）将n个带权值w,i,（in）的结点构成n棵二叉树的集合T=T,1,，T,2,，T,n,，每棵二叉树只有一个根结点。,2）在T中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；,3）在T中删除这两棵树，将新构成的树加入到T中；,4）重复2）、3）步的操作，直到T中只含一棵树为止，该树就是Huffman树。,构造Huffman树举例,以权值分别为7，4，2，4的结点a、b、c、d构造Huffman树。T=a b c d,c,d,T,3,2,4,6,b,T,3,T,2,6,4,10,b,T,2,6,4,10,c,d,2,4,17,a,T,2,7,10,T,1,6,17,a,7,T,1,b,T,3,T,2,4,10,17,a,7,T,1,b,4,10,c,d,2,6,4,（d）T=T,1,（c）T=a T,2,（b）T=a b T,3,（a）T=a b c d,代入T,2,代入T,3,代入T,1,3.Huffman编码,编码：用二进制数的不同组合来表示字符的方法。,前缀编码：,一种非等长度的编码,(任一个字符的编码都不是另一个字符编码的前缀)。,a,0,b,0,1,c,d,0,1,1,编码：A（0）,B（10）,C（110）,D（111）,方法约定：,1）左分支为0,2）右分支为1,3）由叶到根路径上字符组成的二进制串就是该叶结点的编码。,Huffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按,二进制前缀编码的方式,构成的编码为Huffman编码。,Huffman编码举例,在某系统的通信联络中可能出现8种字符，其频率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，设权值分别为5，29，7，8，14，23，3，11，n=8，其Huffman树为：,8,1,0,0,0,0,0,0,0,1,1,1,1,1,1,5,3,7,14,29,11,23,42,58,100,Huffman编码为：,A 5 0110,B 29 10,C 7 1110,D 8 1111,E 14 110,F 23 00,G 3 0111,H 11 010,4.Huffman编码存储结构,由于Huffman树中没有度为1的结点，则n个叶结点的Huffman树共有2n-1个结点。例如，4个叶结点的Huffman树，共有7个结点。因此可以用长度为2n-1的一维数组存放。,求Huffman编码：,从根到叶的编码,。因此要知道每个结点的父结点。,0,0,0,0,0,0,0,1,1,1,1,1,1,1,5,3,7,8,14,29,11,23,42,58,100,Huffman编码为：,A 5 0110,B 29 10,C 7 1110,D 8 1111,E 14 110,F 23 00,G 3 0111,H 11 010,5.Huffman编码的译码,从Huffman编码树上不难看出，,代码全部在叶结点上,，根据Huffman编码，就能求出相应的字符。该过程称为“译码”。,译码是根据,从根到叶,的Huffman编码求相应的字符。因此要知道每个结点的左右子结点。,例如，根据“1111”，就能求出对应的字符是“8”。,5,3,0,0,0,0,0,0,0,1,1,1,1,1,1,1,7,8,14,29,11,23,42,58,100,作业,在某系统的通信联络中可能出现10种字符（A-I），其频率分别为0.04、0.15、0.07、0.08、0.14、0.21、0.02、0.12、0.16、0.09。试建立其Huffman树并给出其Huffman编码。,总结,1.树的定义,2.树的基本概念,3.二叉树,4.特殊二叉树,5.二叉树的遍历操作,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,