数据结构树学习教案.pptx

数据结构数据结构(sh j ji u)树树第一页，共25页。2 2第第第第6 6章章章章 树和二叉树（树和二叉树（树和二叉树（树和二叉树（Tree&Binary Tree Tree&Binary Tree）6.1 树的基本知识6.2 二叉树6.3 遍历(bin l)二叉树和线索二叉树6.4 树和森林6.5 赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个(du)直接后继（1:n）第1页/共25页第二页，共25页。3 36.1 树的基本知识1.树的定义2.若干术语(shy)3.逻辑结构4.存储结构5.树的运算第2页/共25页第三页，共25页。4 41.1.树的定义树的定义树的定义树的定义(dngy)(dngy)注1：过去许多书籍中都定义树为 n1，曾经有“空树不是树”的说法(shuf)，但现在树的定义已修改。注2：树的定义具有递归性，即树中还有树。由一个(y)或多个(n0)结点组成的有限集合T，有且仅有一个(y)结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。第3页/共25页第四页，共25页。5 52.2.若干若干若干若干(rugn)(rugn)术语术语术语术语即上层的那个结点(直接(zhji)前驱)parent即下层结点的子树 (直接(zhji)后继)child同一双亲下的同层结点（孩子之间互称兄弟）sibling即双亲位于同一层的结点（但并非同一双亲）cousin即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根 叶子 森林(snln)有序树无序树即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。第4页/共25页第五页，共25页。6 62.2.若干若干若干若干(rugn)(rugn)术术术术语（续）语（续）语（续）语（续）即树的数据元素结点挂接的子树数（有几个直接(zhji)后继就是几度，亦称“次数”）结点(ji din)结点(ji din)的度结点(ji din)的层次终端结点(ji din)分支结点(ji din)树的度树的深度(或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子除树根以外的结点（也称为内部结点）所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）问：右上图中的结点数 ；树的度 ；树的深度1334第5页/共25页第六页，共25页。7 7树的表示法有几种树的表示法有几种树的表示法有几种树的表示法有几种(j(j zhn)zhn)：图形(txng)表示法嵌套集合表示法广义表表示法目录表示法左孩子右兄弟表示法树的抽象数据类型定义参见(cnjin)教材P118-119第6页/共25页第七页，共25页。8 8图形图形图形图形(txng)(txng)表表表表示法：示法：示法：示法：教师学生其他人员99级2000级2001级2002级三峡(sn xi)大学电气学院计算机系电子系自控系叶子(y zi)根子树第7页/共25页第八页，共25页。9 9广义广义广义广义(gungy)(gungy)表表示法表表示法表表示法表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)根作为由子树森林组成(z chn)的表的名字写在表的左边ABCGEIDHFJMLK第8页/共25页第九页，共25页。1010左孩子左孩子左孩子左孩子(hi zi)(hi zi)右兄弟表右兄弟表右兄弟表右兄弟表示法示法示法示法A AB BC CD DE EF FGGH HI IJ JK KL LMM数据左孩子 右兄弟ABCGEIDHFJMLK第9页/共25页第十页，共25页。1111 树的抽象数据类型定义树的抽象数据类型定义树的抽象数据类型定义树的抽象数据类型定义(dngy)(dngy)ADT Tree数据(shj)对象D:数据(shj)关系R:基本操作 P：ADT Tree若D为空集，则称为(chn wi)空树；/允许n=0若D中仅含一个数据元素，则 R为空集；其他情况下的 R存在二元关系：root 唯一 /关于根的说明 DjDk=/关于子树不相交的说明 /关于数据元素的说明D是具有相同特性的数据元素的集合。/至少有15个第10页/共25页第十一页，共25页。12123.3.树的逻辑树的逻辑树的逻辑树的逻辑(lu j)(lu j)结结结结构构构构 (特点特点特点特点)：一对多（一对多（一对多（一对多（1:n1:n1:n1:n），有多个直接后继（如家谱树、），有多个直接后继（如家谱树、），有多个直接后继（如家谱树、），有多个直接后继（如家谱树、目录目录目录目录(ml)(ml)(ml)(ml)树等等），但只有一个根结点，树等等），但只有一个根结点，树等等），但只有一个根结点，树等等），但只有一个根结点，且子树之间互不相交。且子树之间互不相交。且子树之间互不相交。且子树之间互不相交。4.树的存储(cn ch)结构 讨论1：树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。第11页/共25页第十二页，共25页。1313讨论讨论讨论讨论3 3：树的链式存储方案：树的链式存储方案：树的链式存储方案：树的链式存储方案(fng n)(fng n)应该怎样制定？应该怎样制定？应该怎样制定？应该怎样制定？可规定为：从上至下、从左至右将树的结点依次存入内存。可规定为：从上至下、从左至右将树的结点依次存入内存。可规定为：从上至下、从左至右将树的结点依次存入内存。可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷重大缺陷重大缺陷重大缺陷(quxin)(quxin)(quxin)(quxin)：复原困难（不能唯一复原就没有实用价值）。：复原困难（不能唯一复原就没有实用价值）。：复原困难（不能唯一复原就没有实用价值）。：复原困难（不能唯一复原就没有实用价值）。讨论(toln)2：树的顺序存储方案应该怎样制定？可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。第12页/共25页第十三页，共25页。1414解决思路：先研究最简单(jindn)、最有规律的树，然后设法把一般的树转化为这种简单(jindn)的树。二叉树二叉树讨论(toln)4：计算机如何实现各种不同进制的运算？实现思路：先研究最简单、最有规律的二进制运算(yn sun)规律，然后设法把各种不同进制的运算(yn sun)转化二进制运算(yn sun)。讨论5：树的存储可否借鉴这种思路呢？第13页/共25页第十四页，共25页。15155.5.树的运算树的运算树的运算树的运算(yn sun)(yn sun)要明确：要明确：要明确：要明确：1.1.普普普普通通通通树树树树（即即即即多多多多叉叉叉叉树树树树）若若若若不不不不转转转转化化化化为为为为二二二二叉叉叉叉树树树树，则则则则运运运运算算算算很难实现。很难实现。很难实现。很难实现。2.2.二二二二叉叉叉叉树树树树的的的的运运运运算算算算仍仍仍仍然然然然是是是是插插插插入入入入、删删删删除除除除、修修修修改改改改、查查查查找找找找、排排排排序序序序等等等等，但但但但这这这这些些些些操操操操作作作作必必必必须须须须(bx)(bx)建建建建立立立立在在在在对对对对树树树树结结结结点能够点能够点能够点能够“遍历遍历遍历遍历”的基础上！的基础上！的基础上！的基础上！（遍遍遍遍历历历历指指指指每每每每个个个个结结结结点点点点都都都都被被被被访访访访问问问问且且且且仅仅仅仅访访访访问问问问一一一一次次次次，不遗漏不重复）。不遗漏不重复）。不遗漏不重复）。不遗漏不重复）。本章(bn zhn)重点：二叉树的表示和实现第14页/共25页第十五页，共25页。16166.2 6.2 二叉树二叉树为何要重点为何要重点为何要重点为何要重点(zhngdin)(zhngdin)(zhngdin)(zhngdin)研究每结点最多只有两个研究每结点最多只有两个研究每结点最多只有两个研究每结点最多只有两个“叉叉叉叉”的树？的树？的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。可以证明，所有树都能转为唯一对应的二叉树，不失一般性。可以证明，所有树都能转为唯一对应的二叉树，不失一般性。可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1.二叉树的定义(dngy)2.二叉树的性质3.二叉树的存储结构（二叉树的运算(yn sun)见6.3节）第15页/共25页第十六页，共25页。17171.1.1.1.二叉树的定义二叉树的定义二叉树的定义二叉树的定义(dngy)(dngy)(dngy)(dngy)定义：是n（n0）个结点的有限集合(jh)，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1：2）基本特征:每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒（有序树）。基本形态：问：具有问：具有(jyu)3(jyu)3个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？5种/2种第16页/共25页第十七页，共25页。18182.2.2.2.二叉树的性质二叉树的性质二叉树的性质二叉树的性质(xngzh)(xngzh)(xngzh)(xngzh)(3+2)(3+2)(3+2)(3+2)讨论1：第i层的结点(ji din)数至多是多少？性质1:在二叉树的第i层上至多(zhdu)有2i-1个结点（i0）。性质2:深度为k的二叉树至多有2 2k k-1-1个结点（k0）。2i-1个提问：第i层上至少有 个结点？1讨论2：深度为k的二叉树，至多有多少个结点？2k-1提问：深度为k时至少有 个结点？k第17页/共25页第十八页，共25页。1919讨论讨论讨论讨论3 3 3 3：二叉树的叶子：二叉树的叶子：二叉树的叶子：二叉树的叶子(y zi)(y zi)(y zi)(y zi)数和度为数和度为数和度为数和度为2 2 2 2的结点数之间有关系吗？的结点数之间有关系吗？的结点数之间有关系吗？的结点数之间有关系吗？性质3:对于任何一棵二叉树，若2度的结点(ji din)数有n2个，则叶子数（n0）必定为n21（即n0=n2+1）证明：证明：二叉树中全部结点数二叉树中全部结点数n nn0+n1+n2(n0+n1+n2(叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数)又又二叉树中全部结点数二叉树中全部结点数n nB+1(B+1(总分支数根结点总分支数根结点)（除根（除根(ch gn)(ch gn)结点外，每个结点必有一个直接前趋，即一个分支）结点外，每个结点必有一个直接前趋，即一个分支）而而 总分支数总分支数B=n1+2n2 (1B=n1+2n2 (1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个)三式联立可得：三式联立可得：n0+n1+n2=n1+2n2+1,n0+n1+n2=n1+2n2+1,即即n0=n2+1n0=n2+1实际意义：叶子数实际意义：叶子数2 2度结点数度结点数1 1ABCGEIDHFJ第18页/共25页第十九页，共25页。2020满二叉树：一棵深度满二叉树：一棵深度满二叉树：一棵深度满二叉树：一棵深度(shnd)(shnd)(shnd)(shnd)为为为为k k k k 且有且有且有且有2k-12k-12k-12k-1个结点的二叉个结点的二叉个结点的二叉个结点的二叉树。树。树。树。（特点：每层都（特点：每层都（特点：每层都（特点：每层都“充满充满充满充满”了结点）了结点）了结点）了结点）完全二叉树：深度(shnd)为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度(shnd)为k 的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树深度为4的完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？因为它们在顺序存储方式(fngsh)下可以复原！完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。这其实是顺序顺序二叉树二叉树的含义。第19页/共25页第二十页，共25页。2121对于两种特殊形式的二叉树（满二叉树和完全二叉树），对于两种特殊形式的二叉树（满二叉树和完全二叉树），对于两种特殊形式的二叉树（满二叉树和完全二叉树），对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别还特别还特别还特别(tbi)(tbi)(tbi)(tbi)具备以下具备以下具备以下具备以下2 2 2 2个性质：个性质：个性质：个性质：性质(xngzh)4:具有n个结点的完全二叉树的深度必为log2n1证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号(bin ho)相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即：2k-1-1n2k-1 或2k-1n2k，三边同时取对数，于是有：k-1log2nk 因为k是整数，所以k=log2n+1第20页/共25页第二十一页，共25页。2222性质5:对完全二叉树，若从上至下、从左至右编号(bin ho)，则编号(bin ho)为i 的结点，其左孩子编号(bin ho)必为2i，其右孩子编号(bin ho)必为2i1；其双亲的编号(bin ho)必为i/2（i1 时为根,除外）。证明：对于第k层的中编号为i的元素，在第k层中前面有xi-2k-1个元素在第k层中后面有y2k-11x个元素，则其左孩子编号是：i+y+2x+1=i+2k-1-1-x+2x+1=i+2k-1+x=i+2k-1+i-2k-1=2i则其右孩子编号是：i+y+2x+2=2i1对于左右(zuyu)孩子，其双亲节点编号必然为i/2 (2i+1)/2=2i/2=i第21页/共25页第二十二页，共25页。23233.深度为9的二叉树中至少(zhsho)有 个结点。)9 )8 )912.深度(shnd)为k 的二叉树的结点总数，最多为 个。)k-1 )log2k )k )k课堂练习：1.树中各结点的度的最大值称为树的 。)高度(god)层次 )深度 )度课堂讨论：课堂讨论：课堂讨论：课堂讨论：二叉树是不是树的特殊情况？答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。：满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。第22页/共25页第二十三页，共25页。2424课堂课堂课堂课堂(ktng)(ktng)讨论：讨论：讨论：讨论：Q2:设一棵完全二叉树具有1000个结点(ji din)，则它有 个叶子结点(ji din)，有 个度为2的结点(ji din)，有 个结点(ji din)只有非空左子树，有 个结点(ji din)只有非空右子树。48948810Q1：为什么要研究满二叉树和完全二叉树这两种特殊形式？A1：因为只有(zhyu)这两种形式可以实现顺序存储！由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。A2：易求出总层数和末层叶子数。总层数k=log2n1=10;且前9层总结点数为29-1=511(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。第23页/共25页第二十四页，共25页。2525请注意叶子结点总数末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。分析(fnx)：末层的489个叶子只占据了上层的245个结点（489/2)上层（k=9)右边的0度结点数还有29-1-245=11个！另一法：可先求2度结点数,再由此得到叶子总数。首先，k-2层的28-1（255）个结点肯定都是2度的（完全(wnqun)二叉）另外，末层叶子（刚才已求出为489）所对应的双亲也是度2，（共有489/2244个）。所以，全部2度结点数为255(k-2层)244(k-1层)=499个；总叶子数2度结点数1=500个。第i层上的满结点(ji din)数为2i-1所以，全部叶子数489(末层)11(k-1层)=500个。度为2的结点叶子总数1=499个。有奖征集：有没有更简单的求解方法？第24页/共25页第二十五页，共25页。