第五章java数据结构树和二叉树.

1第五章树和二叉树5.1树的有关概念5.2二叉树5.3二叉树的遍历5.4遍历的应用5.5线索二叉树5.6树和森林5.7哈夫曼树及应用2第六章树和二叉树本章学习要点：①熟练掌握二叉树的结构特点，了解相应的证明方法；②熟悉二叉树的各种存储结构的特点及使用范围；③熟练掌握各种序遍历的递归和非递归算法，了解遍历过程中“栈”的状态，并能灵活运用遍历算法实现二叉树的其它各种运算；④了解线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握在中序线索化树上找给定结点的前驱和后继的方法；⑤熟悉树的各种存储结构及其特点；⑥学会编写实现树的各种运算的算法；⑦了解最优树的特性，掌握建立最优树和哈夫曼编码的方法36.1树的有关概念5.1树的有关概念1.树的概念2.树的应用3.树的表示4.树的有关术语5树的基本操作45.1树的有关概念1．树的概念树（Tree）是n（n0）个结点的有限集合，在任一棵非空树(n0)中：（1）有且仅有一个称为根的结点。（2）其余结点可分为m（m0）个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFEKLM从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。55.1树的有关概念例：下面的图是一棵树T={A,B,C,D,E,F,G,H,I,J，K，L，M}A是根，其余结点可以划分为3个互不相交的集合：T1={B,E,F，K，L},T2={C,G},T3={D,H,I,J，M}这些集合中的每一集合都本身又是一棵树，它们是A的子树。例如对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11={E，K，L}，T12={F}，T11,T12是B的子树。JIACBDHGFEKLM65.1树的有关概念2．树的应用1）树可表示具有分枝结构关系的对象例1．家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J，K，L，M他们之间的关系可下图所示的树表示：例2．单位行政机构的组织关系：JIACBDHGFEKLM75.1树的有关概念2）树是常用的数据组织形式有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12C85.1树的有关概念3树的表示1）图示表示2）二元组表示3）嵌套集合表示4）凹入表示法（类似书的目录）5）广义表表示（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）)）广义表表示ABEKLFCGDHMJI凹入表示法AEDHJIKLMFGC嵌套集合表示B95.1树的有关概念4树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点(child)：结点的子树的根称为该结点的孩子；双亲结点(parent)：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点(sibling)：同一双亲的孩子结点；堂兄结点(cousin)：其双亲在同一层上的结点；祖先结点:从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙JIACBDHGFEKLM105.1树的有关概念4树的基本术语结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推树的深度：树中结点的最大层数，也称为树的高度结点的度：结点具有的子树个数树的度：树中最大的结点度叶子结点：也叫终端结点，是度为0的结点分枝结点：也叫非终端结点，是度不为0的结点有序树：子树有序的树，如：家族树；最左边的子树的根成为第一个孩子,最右边的称为最后一个孩子无序树：不考虑子树的顺序；森林；互不相交的树的集合；森林和树之间的联系是：一棵树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。JIACBDHGFEKLM115.1树的有关概念5树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1）initate(T)：T树的初始化，置T为空树。包括建树。2）root(T)：求T树的根。3）parent(T,x):求T树中x结点的双亲结点。4）Child(T,x,i)：求T树中x结点的第i个孩子结点。5）right_Sibling(T,x)：求T树中x结点的右兄弟6）insert_Child(y,i,x)：将根为x的子树置为y结点的第i个孩子7）del_child(x,i)：删除x结点的第i个孩子8）traverse(T)：遍历T树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。9）clear(T)：置T为空树125.2二叉树树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树——二叉树。135.2二叉树5.2二叉树一二叉树的概念二二叉树的性质三二叉树的存储结构145.2二叉树一二叉树的概念1二叉树的定义二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠倒——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;AFGEDCB155.2二叉树(a)、(b)是不同的二叉树，(a)的左子树有四个结点，(b)的左子树有两个结点，AFGEDCB(a)AGEDBCF(b)165.2二叉树2．二叉树的基本形态φ(a)空树(b)仅有根(c)右子树空(e)左子树空(d)左、右子树均在3个结点的树具有2种基本形态3个结点的二叉树具有5中基本形态175.2二叉树3．应用举例可以用二叉树表示表达式a+b*(c-d)-e/fedcbfa+*/--185.2二叉树二二叉树性质性质1二叉树第i层上至多2i-1个结点（i=1)证明：(采用数学归纳法)①当i=1时，只有1个根结点。显然21-1=1，命题成立。②假设对所有的j(1≤j＜i)命题成立，即第j层上至多2j-1个结点;③现证明j=i时命题仍然成立。∵由归纳假设知，二叉树的i-1层至多有2i-2个结点又由二叉树的定义知，二叉树每个结点的度至多为2∴第i层上的最大结点数目=2*第i-1层上的最大结点数目=2*2i-2=2i-1故j=i时命题成立从而该命题成立。195.2二叉树性质2深度为k的二叉树至多2k-1个结点（k=1)证明：深度为k的二叉树的结点的最大数目＝每层结点的最大数目之和＝20+21+…＋2k-1＝2k-1206.2二叉树性质3对任何一棵二叉树T，若其终端结点数目为n0,度为2的结点数目为n2，则n0=n2+1。证明：设二叉树T的总结点数目为n,度为1的结点数目为n1，则n=n0+n1+n2(1)又由于二叉树T中，除根结点以外，每个结点刚好有一个分支指向，设B为分支总数，则n=B+1(2)而二叉树的这些分支是由度为1和度为2的结点产生，则B=n1+2n2(3)综上三式，可知n0=n2+1成立。思考如果一棵树有n1个度数为1的结点，n2个度数为2的结点，…，nm个度数为m的结点，则终端结点数n0=？215.2二叉树两种特殊的二叉树满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树；AGFEDCBACBK=3的满二叉树K=2的满二叉树225.2二叉树完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；GAEDCB(c)AEDCB(b)(a)、(b)完全二叉树(c)不是完全二叉树A(a)GFEDCB235.2二叉树下面是两个关于完全二叉树的性质▀性质4具有n个结点的完全二叉树的深度为：trunc(log2n)+1，trunc(x)为取整函数。证明：假设完全二叉树的深度为k,则由性质2和完全二叉树的定义知：2k-1-1＜n≤2k-1，即2k-1≤n＜2k对上式取对数有：k-1≤log2n＜k由于k是整数，故k=trunc（㏒2n）+1245.2二叉树对完全二叉树的结点编号：从上到下，每一层从左到右▀性质5：在一棵有n个结点的完全二叉树中,对于编号为i(1≤i≤n)的结点:1）当i=1，结点i为根结点1）若有左孩子(2i≤n)，则左孩编号为2i2）若有右孩子(2i+1≤n)，则右孩子结点编号为2i+13）若有双亲，则双亲结点编号为trunc(i/2)AFEDCB123456255.2二叉树1二叉树的顺序结构//------二叉树的顺序存储表示--------intMAX_TREE_SIZE100Objecttree[MAX_TREE_SIZE]存储方案：用顺序存储结构存储一棵二叉树时，必须首先对该树中每个结点进行编号，树中各结点的编号应与等深度的满二叉树中对应位置上结点的编号相同。用一组连续的内存单元，按结点的编号顺序依次存储二叉树的元素值。三．二叉树存贮结构265.2二叉树例：用一维数组bt[]存放一棵完全二叉树，将标号为i的结点的数据元素存放在分量bt[i-1]中。存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现的。例如，bt[5]（i=6)的双亲结点标号是k=trunc(i/2)=3,双亲结点所对应的数组分量bt[k-1]=bt[2]顺序结构图示AFEDCB123456下标01234567m-1ABCDEF编号123456275.2二叉树非完全二叉树的顺序结构按完全二叉树的形式补齐二叉树所缺少的那些结点，对二叉树结点编号,将二叉树原有的结点按编号存储到内存单元“相应”的位置上。但这种方式对于畸形二叉树，浪费较大空间。AFGEDCB8167245310AFGEDCB9012345678910m-1ABCDE0F00G28讨论：对于完全二叉树来说，二叉树中的结点的编号完全可以反映出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编号与数组下标建立一一对应关系，所以采用顺序存储结构较好。对于一般的二叉树，则添加一些不存在的“空”结点，使之成为一棵完全二叉树。将其每个结点与完全二叉树上的结点完全对应，此时仍可用顺序存储结构表示这棵二叉树。可能造成空间浪费，最坏的情况是：深度为k且只有k个结点的单支树，需要长为2k-1的数组空间。295.2二叉树2二叉链表二叉链表中每个结点包含三个域：数据域、左指针域、右指针域AFEDCBclassBnodept{intdata;Bnodeptlchild,rchlid;}二叉链表图示∧DAB∧C∧∧E∧∧F∧rchilddatalchild二叉链表结点306.2二叉树AFEDCB3三叉链表（便于找到结点的双亲）三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域classBnodept{intdata;Bnodeptlchild,rchild,parent;}ABDFECparentrchilddatalchild三叉链表结点315.3二叉树的遍历一.二叉树的遍历方法二.遍历的递归算法三.遍历的非递归算法325.3二叉树的遍历遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。如何访问二叉树的每个结点，而且每个结点仅被访问一次？335.3二叉树的遍历一二叉树的遍历方法二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L：遍历左子树T：访问根结点R：遍历右子树约定先左后右,有三种遍历方法：TLR、LTR、LRT，分别称为:先序遍历、中序遍历、后序遍历AFGEDCB345