数据结构课件 树和二叉树

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

1、第六章树和二叉树6.1树的定义和基本概念6.2二叉树6.2.1树的定义和基本术语6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换16.4.3树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码2树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界里是大量存在的，例如家谱、行政组织机构都可用树形象地表

2、示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。36.1树的定义和基本术语定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为根的子树(Subtree)。4树的基本概念：结点(node)——表示树中的元素，

3、包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点称为叶子或终端结点。非终端结点——度不为0的结点称为非终端结点或分支结点。5孩子(child)——结点子树的根称为该结点的孩子。相应地，该结点称为孩子的双亲。双亲(parents)——若结点X有子女Y，则X为Y的双亲结点。兄弟(sibling)——同一个双亲的孩子之间互称兄弟。6子孙结点——以某结点为根的子树中的任一结点都称为该结点的子孙。结点的祖先是从根到该结点所经分支上的所有结点。树的度——一棵树中最大的结点度数

4、结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……7深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合有序树——若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。无序树——若一棵树中所有子树的次序无关紧要，则称为无序树。8ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄

5、弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先96.2二叉树二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。106.2.1二叉树的定义定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。11二叉树结点的子树要区

6、分左子树和右子树。图6.8列出二叉树的5种基本形态，图6.8(C)和图6.8（d）是不同的两棵二叉树。(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树图6.8二叉树的5种形式126.2.2二叉树的性质二叉树具有下列重要性质：性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20=1,命题成立。现在假定对所有的j，1<=j

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

8、树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2(6-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：N＝B＋1。15由于这些分支都是由度为1和2的结点射出的，所有有：B＝n1+2*n2N＝B＋1＝n1＋2×n2＋1（6－