数据结构第6章树和二叉树ppt课件.ppt

《数据结构第6章树和二叉树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树6.1树的定义和基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用1树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。26.1树的定义和基本术语一、树的定义树(Tree)

2、是n(n>=0)个结点的有限集，n=0时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)当n＞1时，除根以外的其它结点划分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为根的子树(Subtree)。3ABCDEFGHIJKLA举例：树的抽象数据类型定义P.1184二、树的表示1.直观表示法2.嵌套集合3.凹入表示4.广义表表示GCABDHIJEKFLA*****************B****************E****

3、**********F**************K************L************C****************G**************D****************H**************I**************J**************(A(B(E,F(K,L)),C(G),D(H,I,J)))ABCDEFGHIJKL5三、基本术语结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的子树数结点的层次：从根开始定义起，根为第一层，根的孩子为第二层

4、终端结点(叶子)：度为０的结点非终端结点(分支结点)：度不为０的结点内部结点：除根结点外，分支结点也称为内部结点。6孩子：结点的子树的根双亲：兄弟：同一个双亲的孩子之间互称兄弟祖先：从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中任一结点都称为该结点的子孙。堂兄弟：其双亲在同一层的结点互为堂兄弟。7孩子：结点的子树的根双亲：兄弟：同一个双亲的孩子之间互称兄弟祖先：从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中任一结点都称为该结点的子孙。堂兄弟：其双亲在同一层的结点互为堂兄弟。8树的度：树

5、内各结点的度的最大值树的深度/高度：树中结点的最大层次有序树：若树中结点的各子树从左向右是有次序的（即不能互换）无序树：若树中结点的各子树从左向右是没有次序（即能互换）森林：是m（m≥0）棵互不相交的树的集合。96.2二叉树6.2.1二叉树的定义定义：二叉树是n(n>=0)个元素的有限集合，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。二叉树：度不大于2的有

6、序树10二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，这是二叉树与树的最主要的差别。二叉树的5种基本形态：(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树二叉树的5种形式116.2.2二叉树的性质性质1：二叉树的第i层至多有2i-1个结点(i>=1)。采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20=1,命题成立。现假定对所有的j，1<=j

7、。由归纳假设可知，第i－1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×2i-2＝2i-1。命题得到证明。12性质2：深度为k的二叉树至多有2k－1个结点（k>=1).深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数：2i-1∑(第i层上的最大结点数）=∑2i-1=2k–113性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。设二叉树中度为1的结点数为n

8、1，二叉树中总结点数为n，则有：结点总数n＝n0＋n1＋n2分支数n-1=n1+2n2两式联立，即得n0＝n2＋1思考：若包含有n个结点的树中只有叶子结点和度为k的结点，则该树中有多少叶子结点？n=n0+nkn-1=knkn0=n-(n-1)/k14下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。可以对满二叉树的结点进行连续编号，约定根结点编号