《数据结构-第6章-数和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构-第6章-数和二叉树.ppt（117页珍藏版）》请在三一办公上搜索。
1、1,数据结构：树,2,3,4,第六章 树和二叉树,5,课前思考,家族谱系图,一对多关系,6,徐海学院计算机系,7,概述,树型结构是一类重要的非线性结构树是以分支关系定义的层次结构树的应用人类社会的族谱社会组织结构在编译程序中的语法树在数据库系统中，可用树来组织信息,8,树的定义,树是由n（n0）个结点组成的有限集合,若n=0，称为空树；,有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；,递归定义子树,9,树基本操作（P119）：,10,树的基本术语,结点：包含一个元素及若干指向其子树的分支，大写字母表示,度：一个结点包含子树的数目，称为该结点的度A:3,B:2,F:0,叶
2、子：度为0的结点，称为叶子结点或树叶，也叫终端结点(J,K,L)。,11,树的基本术语,孩子结点：若结点X有子树，则子树的根结点为X的孩子结点A:B,C,D,双亲结点：若结点A有子女B，则A为B的双亲结点。,祖先结点：从根结点到该结点所经过分枝上的所有结点为该结点的祖先，M的祖先结点为：H,D,A,12,树的基本术语,子孙结点：某一结点的子女及子女的子女都为该结点子孙。A:C,G,兄弟结点：具有同一个双亲的结点，称为兄弟结点。E，F,分枝结点：除叶子结点外的所有结点，为分枝结点，也叫非终端结点.C,13,树的基本术语,层数：根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加
3、1。,树的高度（深度）：树中结点所处的最大层数称为树的高度。,14,有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。无序树若一棵树中所有子树的次序无关紧要，则称为无序树。森林（树林）若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。删去一棵非空树的根结点，树就变成身森林；反之,若增加一个根结点,让森林中每一棵树的根结点都变成它的子女,森林就成为一棵树,15,树与线性结构的区别,16,结点A的度：3结点B的度：2结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D结点B的孩子：E，F,结点I的双亲：D结点L的双亲：E,结点
4、B，C，D为兄弟结点K，L为兄弟,树的度：3,结点A的层次：1结点M的层次：4,树的深度：4,结点F，G为堂兄弟结点A是结点F，G的祖先,17,练习1,列出下图所示树的叶结点、分支结点和每个结点的层次。,18,徐海学院计算机系,19,什么是二叉树？,每个结点最多有两个孩子,度=2,有序树（分左右）,20,一个典型的二叉树,21,练习,试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。,22,回顾 树的基本特点、基本术语,一个三层的二叉树最多有几个节点、最少有几个节点。,23,有一棵树的括号表示为A(B,C(E,F(G),D)，回答下面的问题：1、这棵树的根结点是多少2、这棵树的叶子结
5、点是什么3、结点C的度是多少4、这棵树的度是多少5、这棵树的深度是多少6、结点C的孩子结点是哪些7、结点C的双亲结点是谁,24,若一棵度为4的树中度为1、2、3、4的结点个数分别为4、3、2、2，则该树叶子结点的个数是多少？总结点个数是多少？,25,二叉树的性质1,归纳法证明,26,二叉树的性质2,27,二叉树的性质3,n=n0+n1+n2 1,n=n1+2n2+1 2,n0=n2+1,28,两种特殊形态的二叉树,满二叉树,29,两种特殊形态的二叉树,完全二叉树,如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 n的结点一一对应，则称这棵二叉树为完全二叉树
6、。,30,实例,31,二叉树的性质4,3.3=3 3.3=4,根据性质2和完全二叉树性质：2k-1 1n 2k 1或 2k-1 n 2k k-1 log2n k,表明：若 log2n 是整数，则等于 k-1，若 log2n 不是整数，则它大于 k-1 而小于 k。log2n 表示仅取 log2n 的整数部分，舍去它的小数部分。,32,二叉树的性质5,性质5 如果将一棵有n个结点的完全二叉树从上到下，从左到右对结点编号1，2，n，并简称编号为i的结点为 i(1in)，则有如下结论成立：,(1)如果 i=1，则编号为 i 的结点是二叉树的根，无双亲；如果 i1，则其双亲结点 parent(i)的编
7、号是 i/2。,如果 2in，则编号为 i 的结点无左孩子（编号为 i 的结点为叶子结点）；否则其左孩子结点 lChild(i)的编号是 2i。,(3)如果 2i+1n，则编号为 i 的结点无右孩子；否则其右孩子结点 rChild(i)的编号是结点 2i+1，左孩子为2i,33,34,练习,1、具有100个结点的完全二叉树的深度为(从1层开始计数)()A.6 B.5 C.4 D.72、二叉树第i（i=1）层上至多有（）结点。A.2i B.2i C.2i-1 D.2i-1 3、将一棵有50个结点的完全二叉树按层编号(从1开始)，则对编号为25的结点x，该结点（）A.无左、右孩子 B.有左孩子，无
8、右孩子C.有右孩子，无左孩子 D.有左、右孩子,35,回顾,二叉树的5个性质某一层上的最大结点数为：K深度的二叉树最多结点数为：n0=n2+1n结点完全二叉树深度：n结点完全二叉树任一结点i有：,2i-1,2k-1,log2n+1,双亲 i/2,左孩子2i,右孩子 2i+1,36,4.二叉树的存储结构,顺序存储结构链式存储结构 二叉链表 三叉链表 线索链表,37,二叉树的顺序存储结构,/二叉树的顺序存储表示#define MAX_TREE_SIZE 100 typedef TElemType SqBiTree MAX_TREE_SIZE；/0号单元存储根结点SqBiTree bt；,38,完全
9、二叉树的数组表示,表示方法：对完全二叉树所有得结点按照层次次序自顶向下，同一层次自左向右顺序编号1,2,n,得到一线性序列，并把此序列放入到一维数组中。这种方法可以很容易的找到一个结点的双亲、兄弟、子女（性质5）。比如结点C,39,一般二叉树的树组表示,若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。如图给出了顺序存贮形式。,40,41,设二叉树的顺序存储结构如下：,根据其存储结构，画出该二叉树。,42,二叉树的存储结构链式存储结构,适用范围：一般的二叉树，并且如果在一棵树中进行添加删除时，要移动许多结点。,43,二叉链表,44,与单链表类似,整个二叉树可以
10、以一个指向根结点的指针(表头指针)表示,45,/基本操作的原型Status CreateBiTree(BiTree,46,也可以有类似于双向链表的结构-三叉链表,47,二叉链表和三叉链表,48,三叉链表,49,三叉链表结构图,50,可以证明,在含有n个结点的二叉链表中有n+1个空链域。,51,徐海学院计算机系,52,何为遍历二叉树,按某种顺序 访问 一次所有结点,读取数据修改数据,必须先左后右DLR前序遍历LDR中序遍历LRD后序遍历,53,先序遍历,定义如下,若二叉树为空，则空操作;否则（1）访问根结点（2）前序遍历左子树;（3）前序遍历右子树;,A B D E G H C F I J,54
11、,前序遍历动画演示,55,中序遍历,定义如下,若二叉树为空，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树,D B G E H A C I J F,56,中序遍历动画演示,57,后序遍历,定义如下,若二叉树为空，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。,D G H E B J I F C A,58,后序遍历动画演示,59,前序遍历算法实现-递规算法,voidPreorder(BiTree T，void(*visit)(BiTree)/先序遍历以T为根指针的二叉树if(T)/T=NULL时，二叉树为空树，不做任何操作visit(T)
12、;/通过函数指针*visit 访问根结点Preorder(T-Lchild,visit);/先序遍历左子树Preorder(T-Rchild,visit);/先序遍历右子树/if,60,a+b*(c-d)-e/f,61,练习,先序遍历序列：中序遍历序列：后序遍历序列：,ABDGCEFH BGDAECFHGDBEHFCA,62,经典题：写出三个结点的二叉树的前序、中序、后序遍历的序列,前序后序决定层次，中序决定左右,63,画出和下列已知序列对应的二叉树,二叉树的前序访问序列为:EBADCFHGIKJ 二叉树的中序访问序列为:ABCDEFGHIJK2.二叉树的中序访问序列为:DCBGEAHFIJK
13、 二叉树的后序访问序列为:DCEGBFHKJIA,64,写出前、中、后序遍历,65,画出和下列已知序列对应的二叉树,前：A B E F C D G H中：F E B A D C G H,后：F E B D H G C A中：F E B A D C G H,66,线索二叉树,问题？,如何保存在遍历过程中得到的前驱和后继信息？,n个结点有 n+1 个链域的值为NULL,好好利用NULL,67,线索二叉树的结构如下：,0 lchild 域指示结点的左孩子 ltag=1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 rtag=1 rchild 域指示结点的后继,以这种结构构成的
14、二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫线索化。,68,中序线索二叉树,a+b*c d e/f,69,中序线索链表,在二叉树的线索链表上添加了一个头结点。P134。,70,如何在中序线索树中找结点的后继、前趋？结点的后继：应该是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。,71,结点的前趋：若其左标志为“1”，则左链为线索，指示其前驱，否则遍历左子树时的最后访问的一个结点（左子树最右下的结点）为其前驱。,72,什么时候采用线索链表做存储结构？程序中所用二叉树需
15、要经常遍历或查找结点在遍历所得线性序列中的前驱和后继时。,73,徐海学院计算机系,74,树的存储结构1-双亲表示法,顺序存储结构constMAX_TREE_SIZE=100;typedef struct/结点结构 ElemType data;int parent;/双亲位置域PTNode;typedef struct/树结构PTNode nodesMAX_TREE_SIZE;intr,n;/根的位置和结点数PTree;,data,parent,75,双亲表示法示例,data,parent,利用唯一双亲的性质适用于：PARENT(T,x),76,孩子表示法多重链表,同构：树中每个结点除了数据域而
16、外，还有d个域，分别存放结 点的每个孩子结点的位置。其中d是树的度，即树的各个结点的 最大度。这种存储结构的缺点是，浪费存储空间。一棵具有n个 结点的度为k的树中必有n(k-1)+1个空链域。,异构：若树的每个结点除了数据域而外，仅仅存储各自的孩子 结点的位置，则每个结点将是异构的。虽然这样可以节约 存储空间，但是操作麻烦。,77,2 树的孩子表示法,typedef structCTNode/孩子结点intchild;structCTNode*next;*ChildPtr;typedef struct ElemType data;/结点的数据元素ChildPtr firstchild;/孩子链
17、表头指针CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;intn,r;/结点数和根结点的位置CTree;,J,78,孩子表示法示例,适用于：求孩子的操作,J,79,J,为了方便我们可以,80,4 二叉链表表示法（孩子兄弟表示法）,以二叉链表做树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点(fchild 和nsibling)Typedef struct CSNode ElemType data;Struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,81,访问结点x的
18、第 i 个孩子，则只要从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走i-1步，则可以找到第 i 个孩子。如果为每个结点增设一个PARENT域，则同样能方便实现PARENT（T,x）操作。,82,树和二叉树的对应,83,练习,画出此树的 双亲表示、孩子链表表示、二叉链表表示法。,84,森林与二叉树的转换,森林是树的有限集合。,从树的二叉链表表示定义知道：任何一棵和树对应的二叉树的右子树必空。若将森林中第二棵树的根结点看成第一棵树的根结点的兄弟，则可以导出森林和二叉树的对应关系。,如何存储一片森林？,85,森林和二叉树的对应：,86,二叉树转换成森林,
19、87,练习,88,森林和树的遍历,树的遍历：（1）先根遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；（2）后根遍历：先依次后根遍历每棵子树，然后访问根结点。,树的先根序列为：ABCDE树的后根序列为：BDCEA,当以二叉链表作为树的存储结构时，树的先根遍历和后根遍历分别 对应二叉树的先序遍历和中序遍历算法。,89,森林的遍历：（1）先序遍历森林：若森林非空，则可按下述规则遍历之：,（2）中序遍历森林：若森林非空，则可按下述规则遍历之：,访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一树之后剩余的树构成的森林。,中序遍历第一棵树中根结点的子树森林；访问森林
20、中第一棵树的根结点；中序遍历除去第一树之后剩余的树构成的森林。,90,森林的先序遍历和中序遍历分别对应二叉树的先序和中序遍历。,91,徐海学院计算机系,92,赫夫曼树,路径长度 定义：在树中从一个结点到另一个结点之间的分支构成了这两个结点间的路径，路径上的分支条数称为它的路径长度。树的路径长度 等于从树的根结点到树中各个结点的路径长度之和。,1,2,3,7,6,5,4,8,93,1,2,3,7,6,5,4,8,1,2,3,7,6,5,4,8,二叉树(a),二叉树(b),可以得到：a的路径长度PL=13，b的路径长度PL=14。为什么分支数相同、结点数相同，而路径长度不同？,94,赫夫曼树带权路
21、径长度WPL,什么是权？若将树中叶子结点赋给一个有着某种含义的数值，则这个数值称为该叶子结点的权。假定一个有n个权值的集合w1,w2wn，其中wi=0。若T是一棵有n个叶子结点的二叉树，并且将权值w1,w2wn分别赋给T的n个叶结点，则我们称T是权值为w1,w2wn的扩充二叉树。带权值的称为外结点，不带权值的称为内结点。,95,树的带权路径长度,树的带权路径长度规定为所有叶子结点的带权路径长度之和，其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。,WPL=,在权值为w1,w2wn的扩充二叉树中，其WPL最小的扩充二叉树称为最优二叉树。,96,判断哪棵树
22、是最优二叉树,97,4,5,7,2,4,5,7,2,5,2,4,7,上图中的3棵二叉树都是权值为7,5,2,4的扩充二叉树 a的带权路径长度WPL为：36；b的为46，c的为35。由此可见，带权路径长度最小的扩充二叉树不一定是完全二叉树。直观的看：带权路径长度最小的二叉树应是权值大的外结点离根最近的扩充二叉树，这就是赫夫曼树。,（a）,（b）,（c）,98,解某些判定问题，利用赫夫曼树可以得到最佳判定算法,例如，编制一个程序实现从百分制到五级分制的转换。,if(a60)b=“bad”;else if(a70)b=“pass”;else if(a80)b=“general”;else if(a9
23、0)b=“good”;else b=“excellent”;,99,a60,不及格,Y,N,a70,及格,Y,N,a80,中等,Y,N,a80,良好,Y,N,良好,100,中等,Y,N,a80,a70,Y,N,a60,及格,Y,a90,优秀,N,良好,Y,N,不及格,101,最优树的构造方法 赫夫曼算法,(1)根据给定的 n 个权值w1,w2,wn，构成 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为 Wi的根结点，其左右子树均空。(2)在 F 中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值
24、之和。(3)在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。重复(2)和(3)，直到 F 只含一棵树为止。这棵树便是所求的赫夫曼树。,102,动画演示,103,练习,给定权值集合15,03,14,02,06,09,16,17构造相应的赫夫曼树，并计算他的带权路径长度。,104,赫夫曼树的应用赫夫曼编码,用途：电报通讯,假设需传送的电文为ABACCDA,A:00、B:01、C:10、D:11,00010010101100，总长14位,根据出现的频率进行简化 A:0、B:00、C:1、D:01,“000011010”，总长为9位,问题出现了：0000，什么含义？,105,解决方案,假设有
25、一棵如右图所示的二叉树，其四个叶子结点分别表示A、B、C和D四个字符，且约定左分支表示字符0，右分支表示字符1，则以由从根到叶子的路径上的分支表示的字符组成的字符串作为该叶子结点字符的编码。,106,比如：,假设电文总只有5个字符，且在电文中出现的频率分别为：5/29，6/29，2/29，9/29，7/29 则所构造的最优前缀编码如下图所示。,107,练习,假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5，25，3，6，10，11，36，4。试为这8个字母设计不等长的huffman编码，并给出该电文的总编码数。,108,采用动态
26、分配的顺序存储表示存储赫夫曼树数组的大小为2n-1的一维数组,/赫夫曼树和赫夫曼编码的存储表示 typedef struct unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树 typedef char*HuffmanCode;/动态分配数组存储赫夫曼编码表,109,void HuffmanCoding(HuffmanTree,110,/从叶子到根逆向获得每个字符的赫夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);ch=(ch
27、ar*)malloc(n*sizeof(char);/分配求编码的工作空间 cd n-1=“0”;/编码结束符 for(I=1;I=n;+i)/逐个字符求赫夫曼编码 start=n-1;/从叶子到根逆向求编码 for(c=I,f=HTi.parent;f!=0;c=f,f=HTf.parent;)if(HTf.lchild=c)cd-start=“0”;else cd-start=“1”;/为第i个字符编码分配空间 HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,111,基础习题总结,1.已知一棵树边的集合为,，请画出这棵树，并回答下列问题
28、：(1)哪个是根结点?(2)哪些是叶子结点?(3)哪个是结点 G 的双亲?(4)哪些是结点 G 的祖先?(5)哪些是结点 G 的孩子?(6)哪些是结点E的子孙?(7)哪些是结点 E 的兄弟?哪些是结点F的兄弟?(8)结点 B 和 N 的层次号分别是什么?(9)树的深度是多少?(10)以结点 C 为根的子树的深度是多少?,112,2、已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，试求该树的叶子结点数目,解答：设有nk个度为k的分支结点，n0个度为0的分支结点各点度数总和为：n=k*nk+1,最后计算得到叶节点个数为n-(n-1)/k。,113,3、描述满足下列条件的二叉树
29、形态：（1）先序遍历序列与中序遍历序列相同；（2）后序遍历序列与中序遍历序列相同；（3）先序遍历序列与后序遍历序列相同；,解答：先序遍历DLR，中序遍历LDR，后序遍历LRD；（1）各结点均无左孩子；（2）各结点均无右孩子；（3）只有一个根节点,114,4、画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列,115,5、将森林转换为相应的二叉树,116,6、假设用于通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这 8 个字母设计哈夫曼编码,117,练习2,如果一棵树有n1个度为1的结点,有n2个度为2的结点,nm个度为m的结点,试问有多少个度为0的结点?试推导之。,总结点数 n=n0+n1+n2+nm总分支数 e=n-1=n0+n1+n2+nm-1=m*nm+(m-1)*nm-1+2*n2+n1则有,
