软件技术基础概论 教学课件 作者 吕林涛第4章 树与二叉树.ppt

《软件技术基础概论 教学课件 作者 吕林涛第4章 树与二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*第4章树与二叉树*第四章树与二叉树树形结构是一类重要的非线性结构，其逻辑关系呈现出一对多的关系。树形结构中元素（结点）之间具有明确的层次关系，元素（结点）之间有分支，非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如行政机构或家谱等都可用树来形象地表示。树在计算机领域中也有广泛的应用，例如在编译程序中，用树来表示源程序的语法结构，在数据库系统中用树来组织信息。*本章内容提要:树的基本概念二叉树二叉树的遍历二叉排序树哈夫曼树树和森林第四章树与二叉树*4.1树的基本概念树的概念与定义树的基本术语树的概念与

2、定义*树的概念：现实生活中存在许多用树形结构描述的实际问题。例如，某家族的关系如下：张抗生有三个孩子，即张卫红、张卫兵和张卫华；而张卫兵有两个孩子张明和张丽；张卫华有一个孩子张群。这个家族关系可以很自然的用图右图所示的树形图来描述，它很像一棵倒置的树。从右图可以看出，以张抗生为根的树是一个大家庭，并可以分为张卫红、张卫兵、张卫华为根的三个小家庭，且每个小家庭又形成了一个树形结构。*树的定义树的概念：树是n（n≥0）个结点的有限集合T，当n=0（即T为空）时称为空树；当n＞0时非空。树T满足以下两个条件：（1）有且

3、仅有一个称为根的结点。（2）其余结点可分为m（m≥0）个互不相交的子集T1、T2、…、Tm，其中每个子集Ti本身又是一棵树，并称为根的子树。*4.1树的基本概念树的概念与定义树的基本术语*树的基本术语（1）树的结点包含一个数据元素及若干指向其子树的分支结点拥有子树的个数树内个各结点度的最大值。度为0的结点，又称终端结点度不为0的结点，又称非终端结点结点的子树的根称为该结点的孩子若结点j是结点i的孩子，则结点i就是结点j的双亲同一双亲的孩子之间互称兄弟从根到该结点所经分支上的所有结点均为该结点的祖先以某结点为根的子

4、树中任意结点称为该根的子孙（2）结点的度（3）树的度（4）叶子（5）分支结点（6）孩子（7）双亲（8）兄弟（9）祖先（10）子孙*树的基本术语（11）结点层次从根开始，根为第一层，根的孩子为第二层；若某结点在L层，则其子树的根则在第L+1层树中结点的最大层次若树中每个结点的各个子树从左到右的次序不能互换，则称该树为有序树，否则为无序树森林是m（m≥0）棵互不相交的树构成的集合。删除一棵树的根，就得到由m棵子树构成的森林；反之，给m棵树的森林加上一个根结点，并且这m棵树都是该结点的子树，那么就由森林变为一棵树（12

5、）树的深度（13）有序树或无序树（14）森林*4.2二叉树二叉树的定义二叉树的性质二叉树的存储结构二叉树的定义：二叉树是n（n≥0）个结点的有限集合，它或者是空树（n=0），或者是由一个根结点及两棵互不相交二叉树的定义（1）二叉树不存在度大于2的结点。（2）二叉树每个结点至多有两棵子树且有左、右之分，次序不能颠倒。二叉树任何一个结点的子树都要区分为左、右子树，即使这个结点只有一棵子树时也要明确指出它是左子树还是右子树；而树则无此要求，即树中某个结点只有一棵子树时并不区分左右。（1）不存在度为1的结点，即所有分支结

6、点都有左子树和右子树。（2）所有叶子结点都在同一层上。叶子结点只能出现在最下层和次最下层，且最下层的叶子结点都集中在树的左部。如果完全二叉树中某个结点的右孩子存在，则其左孩子必定存在。此外，在完全二叉树中如果存在度为1的结点，则该结点的孩子一定是结点编号中的最后一个叶子结点。注意：一棵满二叉树必定是一棵完全二叉树，而一棵完全二叉树却未必是一棵满二叉树，（可能存在叶子结点不在同一层上或者有度为一的结点）二叉树的特点：二叉树与树的主要区别：满二叉树的性质：完全二叉树的特点：*4.2二叉树二叉树的定义二叉树的性质二叉树

7、的存储结构性质1：非空二叉树的第i层上最多有2i-1个结点（i≥1）。性质2：深度为k的二叉树至多有2k-1个结点（k≥1）。性质3：在任意非空二叉树中，如果叶子结点（度为0）数为n0，度为2的结点数为n2，则有n0＝n2+1性质4：具有n个结点的完全二叉树的深度为性质5：对一个具有n个结点的完全二叉树按层次自上而下，且每层从左到右的顺序对所有结点从1开始到n进行编号，则对任一序号为i的结点有：（1）若i＞1，则i的双亲结点序号是；若i=1，则i为根结点序号。（2）若2i≤n，则i的左孩子序号是2i，否则i无左孩

8、子。（3）若2i+1≤n，则i的右孩子序号是2i+1；否则i无右孩子。二叉树的性质*4.2二叉树二叉树的定义二叉树的性质二叉树的存储结构1.顺序存储结构二叉树的顺序存储是用一组地址连续的存储单元来存放二叉树中的结点数据。一般是按照二叉树结点自上而下、从左到右的顺序进行存储。二叉树的存储结构实现二叉树存储，不但要存储二叉树中各结点的数据信息，而且还要能够反映出二叉树结点之间