数据结构与算法5讲解

《数据结构与算法5讲解》由会员分享，可在线阅读，更多相关《数据结构与算法5讲解（61页珍藏版）》请在金锄头文库上搜索。

1、第5章 树和二叉树 （4课时）,图5-1 树的树形图表示,5.1 树的基本概念,树是由n（n0）个结点组成的有限集T。当n=0时，称为空树；当n0时，集合T须满足如下条件： 有且仅有一个没有前驱的结点，该结点称为树的根结点； 将根节点去除后，其余结点可分为m（m0）个互不相交的子集T1、T2、Tm，其中每个子集Ti（i=1, 2, , m）又是一棵树，并称其为根的子树。 可以看到，树的定义采用的是递归定义方式，即一棵非空的树由根节点和去除根节点后得到的若干棵规模更小的子树构成，而每一棵子树又是由该子树的根节点和去除该子树根节点后得到的若干棵更小的子树构成。例如，图5-1所示的树可以看作是由根节

2、点A和3棵子树T1、T2、T3（结点集合分别为D1=B, E, F, I、D2=C, G和D3=D, H, J, K, L）构成；子树T1又可以看作是由根节点B和两棵子树T11、T12（结点集合分别为D11=E、D12=F, I）构成。,5.1 树的基本概念,树形图表示法因其直观性强而成为树的最常用的表示形式，图5-1即是采用树形图表示法表示的树。除树形图表示法之外，还有三种常用的表示形式： 1.嵌套集合表示法 嵌套集合表示法是通过集合包含的形式体现结点之间的关系，后继结点集合包含在前驱结点集合中。例如，采用嵌套集合表示法可将图5-1所示的树表示为图5-3所示的形式。,5.1 树的基本概念,2

3、.凹入表表示法 凹入表表示法是利用书的目录形式表示结点之间的关系，后继结点位于前驱结点的下一层目录中。例如，采用凹入表表示法可将图5-1所示的树表示为图5-4所示的形式。 3.广义表表示法 广义表表示法是利用广义表的多层次结构来表示树，后继结点位于前驱结点的下一层次。例如，采用广义表表示法可将图5-1所示的树表示为图5-5所示的形式。,5.1 树的基本概念,5.1 树的基本概念,2.结点的层和树的深度 树的根结点所在的层为第1层，其余结点的层等于其前驱结点的层加1；树中 各结点的层的最大值称为树的深度。,1.度和树的度 一个结点的后继的数目称为该结点的度；树中各结点度的最大值称为树的度。,3.

4、分支、路径、路径长度和树的路径长度 从一个结点到其后继结点之间的连线称为一个分支；从一个结点X到另一个结点Y所经历的所有分支构成结点X到结点Y的路径；一条路径上的分支数目称为路径长度；从树的根结点到其他各个结点的路径长度之和称为树的路径长度。,5.1 树的基本概念,5.结点间的关系 在树中，一个结点的后继结点称为该结点的孩子，相应地，一个结点的前驱结点称为该结点的双亲，即一个结点是其孩子结点的双亲、其双亲结点的孩子。 同一双亲的孩子结点之间互称为兄弟，不同双亲但在同一层的结点之间互称为堂兄弟。 从树的根结点到某一个结点X的路径上经历的所有结点（包括根结点但不包括结点X）称为结点X的祖先，以某一

5、结点X为根的子树上的所有非根结点（即除结点X外）称为结点X的子孙。,4.叶子结点、分支结点和内部结点 树中度为0的结点称为叶子结点（或终端结点），度不为0的结点称为分支结点（或非终端结点），除根结点以外的分支结点也称为内部结点。,5.1 树的基本概念,5.1 树的基本概念,二叉树是一种特殊的树型结构，在实际应用中有着十分重要的意义。比如，在通信、数据压缩等领域有着广泛应用的哈夫曼树就是采用二叉树的结构；在数据库中可以选择使用二叉树结构管理数据等。本节主要介绍二叉树的定义和一些基本性质。,5.2二叉树及其基本性质,对二叉树中的结点可以按照“自上而下、自左至右”的顺序进行连续编号（称为顺序编号法）

6、，即从根结点开始将其编号为1；除第一层外其余各层第一个结点的编号等于上一层最后一个结点的编号加1。图5-8所示的就是3棵深度为3、采用顺序编号法表示的二叉树：,5.2二叉树及其基本性质,图5-8 采用顺序编号法表示的树,5.2二叉树及其基本性质,1.二叉树 与树一样，二叉树的定义也采用递归定义方式。 二叉树是由n（n0）个结点组成的有限集T。当n=0时，称为空二叉树；当n0时，集合T须满足如下条件： 有且仅有一个没有前驱的结点，该结点称为二叉树的根结 将根节点去除后，其余结点可分为两个互不相交的子集T1、T2，其中每个子集Ti（i=1, 2）又是一棵二叉树，并分别称为根结点的左子树和右子树。,

7、5.2二叉树及其基本性质,二叉树共有5种基本形态，如图5-7所示。,5.2二叉树及其基本性质,图5-7 二叉树的基本形态,2.满二叉树和完全二叉树 满二叉树是指除了最后一层的结点为叶子结点外其它结点都有左、右两棵子树的二叉树。例如，图5-8（a）是一棵满二叉树；图5-8（b）中的结点3缺少右子树，图5-8（c）中的结点2缺少右子树、结点3缺少左子树，因此它们都不是满二叉树。 完全二叉树是指其结点与相同深度的满二叉树中的结点编号完全一致的二叉树。对于深度为k的完全二叉树，其前k-1层与深度为k的满二叉树的前k-1层完全一样，只是在第k层上有可能缺少右边若干个结点。显然，满二叉树必然是完全二叉树，

8、而完全二叉树不一定是满二叉树。例如，图5-8（a）既是满二叉树也是完全二叉树；图5-8（b）与图5-8（a）中的满二叉树相比只是在最后一层上缺少右边的一个结点，因此是一棵完全二叉树；而图5-8（c）则不是完全二叉树。,5.2二叉树及其基本性质,5.2二叉树及其基本性质,二叉树具有以下几个基本性质。 性质1：在二叉树的第i层上至多有2i-1个结点（i1）。 性质2：深度为k的二叉树至多有2k-1个结点。 性质3：在二叉树中，若度为0的结点（即叶子结点）数为n0，度为2的结点数为n2，则n0=n2+1。 性质4：具有n个结点的完全二叉树其深度为log2n+1（其中log2n表示不大于log2n的最

9、大整数）。 性质5：采用顺序编号的完全二叉树具有如下性质： （1）若一个分支结点的编号为i，则其左子树的根结点（即左孩子结点）编号为2*i，右子树的根结点（即右孩子结点）编号为2*i+1； （2）反之，若一个非根结点的编号为i，则其双亲结点的编号为i/2（其中i/2表示不大于i/2的最大整数）。,5.3 二叉树的抽象数据类型和表示方式,5.3 二叉树的抽象数据类型和表示方式,2.二叉树顺序表示的实现 由于顺序表示非完全二叉树时空间利用率较低，因此，二叉树的顺序表示在实际中应用不多。下面主要围绕二叉树的创建和删除这两个最基本的操作介绍二叉树顺序表示的实现。 二叉树顺序表示的类模板描述如下： 【描

10、述5-1】二叉树顺序表示的类模板描述。 分析：在类模板中，需设置以下成员变量：一维数组m_pElement用于存储二叉树中各结点的值，数组类型由二叉树结点的值的类型决定；整型变量m_nMaxSize用于存储二叉树中的最大结点数；一个bool型一维数组m_pbUsed，用于表示结点状态，若某个结点不存在（如图5-9（b）中的结点4和结点5），则m_pbUsed中相应元素的值为false，否则相应元素的值为true。,5.3 二叉树的抽象数据类型和表示方式,3.二叉树顺序表示代码复用示例 【例5-1】基于二叉树顺序表示的C+实现代码，完成如下操作： 创建图5-9（b）所示的二叉树，其中每一个结点保

11、存一个字符信息，并通过逐层遍历输出各结点的值。 将以结点C为根结点的子树删除，并通过逐层遍历输出各结点的值。 清空二叉树中的元素。 分析：对于由简单数据元素构成的二叉树，一般可以直接使用C+语言提供的基本数据类型来描述数据元素，本例中可直接使用char类型。,5.3 二叉树的抽象数据类型和表示方式,5.3 二叉树的抽象数据类型和表示方式,1.二叉树的链式表示 在二叉树的链式表示中，结点之间的关系通过指针来体现。根据一个结点中指针域数量的不同，二叉树的链式表示又可以分为二叉链表表示和三叉链表表示。图5-10是一个用二叉链表表示法存储二叉树的例子。由于二叉树中每个结点最多有两个孩子，因此在一个结点

12、中设置两个指针域leftchild和rightchild分别指向其左孩子和右孩子，数据域data用于存放每个结点中数据元素的值。,5.3 二叉树的抽象数据类型和表示方式,分析：创建二叉树的方式有多种，这里采用基于队列的层次创建方式。其创建步骤如图5-13所示。,5.3 二叉树的抽象数据类型和表示方式,图5-11是一个用三叉链表表示法存储二叉树的例子。在三叉链表表示中，双亲结点有指向其孩子结点的指针，而孩子结点也包含指向其双亲结点的指针。因此，在用三叉链表表示的二叉树的每个结点中，除了具有二叉链表中的两个指向孩子结点的指针域leftchild和rightchild外，还有一个指向双亲结点的指针域

13、parent。根结点没有双亲，所以它的parent指针为空（用NULL或0表示）。,5.3 二叉树的抽象数据类型和表示方式,2.二叉树链式表示的实现 二叉链表表示是二叉树最常用的存储结构，这里以二叉链表为例、围绕二叉树的创建介绍二叉树链式表示的实现，其他常用操作的实现在5.4节给出。详细代码见讲义,5.3 二叉树的抽象数据类型和表示方式,3.二叉树链式表示代码复用示例 【例5-2】基于二叉树二叉链表表示的C+实现代码，创建图5-12所示的二叉树，其中每一个结点保存一个字符信息。,图5-12 例5-2创建的二叉树,5.4 二叉树的遍历及常用操作,5.4 二叉树的遍历及常用操作,5.4 二叉树的遍

14、历及常用操作,1.先序遍历 先序遍历，也称为先根遍历，其访问方式递归定义如下： 对于一棵二叉树，先访问其根结点，再访问根结点的左、右子树； 对于左、右子树中的结点仍然是按照先序遍历方式访问，即先访问根结点，再访问根结点的左、右子树。 提示：在先序遍历中，只规定了根结点和其子树的访问顺序，但没有规定左、右子树的访问顺序。本书中规定，在先序、中序和后序遍历时均是先访问左子树后访问右子树。 例如，对于图5-12所示的二叉树，其先序遍历的结果为：A、B、D、G、C、E、F、H、I。,5.4 二叉树的遍历及常用操作,表5-1 图5-12所示二叉树的非递归先序遍历过程,5.4 二叉树的遍历及常用操作,2.

15、中序遍历 中序遍历，也称为中根遍历，其访问方式递归定义如下： 对于一棵二叉树，先访问根结点左子树，再访问根结点，最后右子树； 对于左、右子树中的结点仍然是按照中序遍历方式访问。 例如，对于图5-12所示的二叉树，其中序遍历的结果为：D、G、B、A、E、C、H、F、I。,5.4 二叉树的遍历及常用操作,3.后序遍历 后序遍历，也称为后根遍历，其访问方式递归定义如下： 对于一棵二叉树，先访问根结点的左子树，后访问右子树，最后访问根结点； 对于左、右子树中的结点仍然是按照后序遍历方式访问。 例如，对于图5-12所示的二叉树，其后序遍历的结果为：G、D、B、E、H、I、F、C、A。,1.获取指定结点的

16、双亲结点 在二叉树的二叉链表表示中，结点中没有指向其双亲结点的指针，要获取双亲结点则需要从根结点开始遍历二叉树直至找到指定结点的双亲结点。因此，可以参照上一小节中给出的二叉树遍历算法，编写获取双亲结点的程序。 2.删除以指定结点为根的子树 删除以指定结点为根的子树，一方面要将子树从二叉树中删除，另一方面要将子树中的结点释放。将子树从二叉树中删除是通过将指定结点的双亲结点的指针值置空来实现（若删除的是整棵二叉树，则应将根结点指针值置空）。将子树中的结点释放，就是采用类似于遍历子树中所有结点的方式将各结点占据的内存释放。,5.4 二叉树的遍历及常用操作,3.根据关键字查找结点 根据关键字查找结点，实质上就是按照某种规则依次访问二叉树中的每一结点，直至找到与关键字匹配的结点。因此，同遍历算法一样，根据关键字查找结点也可以采用递归方式和非递归方式。,5.4 二叉树的遍历及常用操作,5.5 哈夫曼树和哈夫曼码,5.5 哈夫曼树和哈夫曼码,5.5 哈夫曼树和哈夫曼码,5.