第六章 树

Transcription

1 第六章树和二叉树 本章教学知识点与学习要求 :( 课内教学时数 8 学时, 实践教学时数 2 学时 ) (1) 理解树型结构的基本概念和术语 ; (2) 熟练掌握二叉树的定义 性质及相应的证明方法 ; (3) 熟悉二叉树的各种存储结构的特点及适用范围 ; (4) 熟练掌握二叉树的三种遍历算法, 且能灵活运用遍历算法实现二叉树的其他操作 ; (5) 熟练掌握线索化二叉树的过程, 以及在中序线索化树上找给定结点的前驱和后继 的方法 ; (6) 熟悉树的各种存储结构及其特点 ; (7) 掌握树和森林与二叉树之间相互转换的方法 ; (8) 学会编写实现树的各种操作的算法 ; (9) 了解最优树的特性, 掌握建立哈夫曼树和哈夫曼编码的方法及算法 本章学习重点 : (1) 二叉树的定义 性质 逻辑特点及五种基本形态 基本运算 ; (2) 二叉树的链式存储结构 顺序存储结构及其类型说明 ; (3) 二叉树链式存储结构的组织方式 ; (4) 二叉树的三种遍历方法及其算法, 以遍历为基础在二叉树上实现的几种运算 ; (5) 哈夫曼树和哈夫曼算法 ; 森林与二叉树的转换 本章教学难点 : (1) 二叉树的递归定义 ; (2) 二叉树链式存储结构的组织方式 ; (3) 三种遍历的主要区别 ; 二叉树上的复杂运算 ; (4) 哈夫曼算法及其应用 ; 森林与二叉树的转换 6.1 树 现实生活和软件设计中的许多关系表现为树的形式, 如图 6-1 所示的家族成员关系表 为简洁起见, 将其中的每个成员用一个符号来表示 这一结构具有明显的层次性, 并且其中 的每个元素最多只有一个前趋 ( 或父辈 ), 但可能有多个后继 ( 或后代 ) 1

2 A11 A21 A22 A23 A31 A32 A33 A3 4 A41 A42 图 6-1 家族成员关系表示例与此类似的还有很多, 例如一个单位的组成结构 这类结构在软件设计中经常要涉及到, 为此, 将满足这类特点 ( 即具有明显的层次性, 并且其中的每个元素最多只有一个前趋, 但可能有多个后继 ) 的结构抽象表示为本章的树形结构 定义 : 树是由一个叫作根的结点和若干个结点集合所组成的结构, 其中每个集合也构成树, 称为根的子树子树 和许多教材类似的是, 本教材中有关树的定义是采用递归方式描述的, 这是由树结构的特点所决定的 每个子树和树具有相同的组织形式 需要说明一点, 本书有关树的定义没有给出空树的概念, 即树中结点数目至少为 1, 这与大多数教材一致 但在部分教材中有此概念, 需要注意 树有几种常见的表示形式 : 1) 图形表示法 : 如图 6-2 所示 2) 嵌套集合表示法 ( 类似于地图的表示 ) 3) 凹入表表示法 ( 类似于书本中的目录形式 ) 4) 广义表表示法 如图 6-2 所示的树的广义表形式为 (A,(B,(C),(D),(E)),(F,(G),(H))) A B F C D E G H 图 6-2: 树结构的图形表示示例显然, 图形表示形式最为直观 清晰, 因此, 在各种教材中都将此作为主要的表示形式 下面给出与树有关的概念 一个结点的度是指该结点的孩子数目 ; 若一个结点的度为 0, 则称该结点为叶子结点叶子结点或终结点, 否则称为分支结点分支结点或非终结点 ; 称非根的分支结点为内部结点, 根也被称为开始结 2

3 点 一棵树的度树的度是树中最大的结点度 例如,A 的度为 2,B 的度为 3,C D 和 E 的度为 0, 树的度为 3 树结构清晰地反映出结点之间的多种关系, 有关这些关系的术语借助于现实生活中较为熟悉而形象的关系术语来描述, 因此非常直观 形象 某个结点的子树的根称为其孩子结点, 而该结点为孩子结点的双亲结点双亲结点或父结点父结点 例如, 在图 6-2 中,A B 是一对父子,B 和 C,B 和 D,B 和 E 等也是一对父子结点 指同一个结点的孩子称为兄弟结点兄弟结点 图 6-2 中,B 和 F 是兄弟,C 和 D E 也是兄弟 延伸父子关系可得祖先结点祖先结点和后代结点后代结点关系 下面给出与层次数相关的一组术语 : 根的层次为 1, 其余结点的层次为父结点的层次数加 1, 而最大的层次数称为树的高度高度或深度深度 如果树中各兄弟结点之间的排列是次序无关的, 则称之为有序树, 否则为无序树无序树 称多棵树为森林森林 树结构的特点 : 与线性表及其他结构相比, 树结构有明显的差异 : 每个结点至多有一个直接前趋 ( 即父结点 ), 但却可以有多个后继结点 ( 即孩子结点 ) 树的运算 : 对树 ( 包括森林 ) 可执行如下的基本运算 : (1) 初始化树 :initial(t); 建立树或森林 T 的初始结构 : (2) 插入子树 :insert(t, S); 将以结点 S 为根的树作为 T 的第一个子树插入到树中 (3) 插入兄弟结点 :insert_sibling(t, S); 将以结点 S 为根的树作为 T 的兄弟子树插入到树中 (4) 查询根结点 :rootof(t); 查询结点 T 所在树的根结点 (5) 查询父结点 :fatherof(t); 查询结点 T 的父结点 (6) 查询孩子结点 :childof(t); 查询结点 T 的所有或某个孩子结点 (7) 查询兄弟结点 :siblingof(t); 查询结点 T 的所有或某个兄弟结点 这些运算是一些基本运算, 还可能有一些运算, 在此不再细述 由于树和森林的存储结构涉及到后面将要介绍的二叉树结构, 因此, 有关其存储结构及运算将在二叉树之后再作介绍 6.2 二叉树 二叉树是树形结构的一个重要形式, 其运算较为直观 树结构可转换为二叉树形式, 因 此可借助二叉树的运算来实现树结构的运算 由此可知, 二叉树是本章及整个课程的重点, 理解其概念 性质及存储结构, 并熟练写出有关算法是最基本的要求 二叉树的有关概念 定义 : 二叉树 T 是 n 个结点的有限集合, 其中 n 0, 当 n=0 时, 为空树, 否则, 其中有一个结点为根结点, 其余结点划分为两个两个互不相交的子集 TL TR, 并且 TL TR 分别构成叫作左 右子树左 右子树的二叉树 二叉树大多用图的形式表示, 如图 6-3 所示 3

4 A B I C F J L D E G H K M 图 6-3 二叉树示例 在此要注意的是 : 虽然二叉树的图形表示形式和树结构的图形表示形式有相似之处, 但两者从本质上说就是不同的, 因为二叉树每个结点的孩子都有左右之分, 每个结点都有左右两个子树, 这与树结构明显不同 例如, 由 3 个结点所构成的树和二叉树的所有形态就明显不同, 如题 6-4 所示 : A A A A A A A B C B B C B B B B C C C C C 三个结点的树 ( 两棵 ) 三个结点的二叉树 ( 五棵 ) 图 6-4 三个结点所组成的二叉树和树的所有形态 由定义可知, 依据结点数的多少可知二叉树有图 6-4 所示的五种不同的形态 : (1) 空树 结点数为 0 (2) 单结点二叉树 仅有一个结点 (3) 左子树为空右子树不空 (4) 右子树为空左子树不空 (5) 左右子树均不空 图 6-4 二叉树的五种形态问题 : 在第 4 种情况下, 能否说该二叉树没有没有右子树? 解答 : 不能这么说, 因为按二叉树的定义, 任意结点均有两个子树, 只不过可能为空 问题 : 若二叉树中某结点的度为 1, 是否可以说该结点仅有一棵子树? 是否可以说叶子结点没有子树 4

5 解答 : 这种说法同样是错误的, 原因同上 二叉树性质 二叉树的性质是理解二叉树的重要内容, 理解二叉树的性质有助于二叉树后续内容的学习, 是解答许多有关问题的基础 通过对有关性质的学习, 可加深对这一内容的理解 下面分别介绍二叉树的五个性质, 并通过实例来说明其应用 对于较简单直观的性质, 没有给出其证明 性质 1: 在二叉树的第 i 层上至多有 2 i-1 个结点 (I>0) 性质 2: 深度为 k 的二叉树至多有 2 k -1 个结点 (k>0) 性质 3: 对任一棵非空二叉树 T, 如果其叶子数为 n 0, 度为 2 的结点数为 n 2, 则有下面的关系式成立 :n 0 =n 2 +1 证明 : 设 T 的总结点数为 n, 度为 1 的结点数为 n 1, 则 T 的结点数满足下面关系式 : n=n 0 +n 1 +n 2 (a) 下面再从 T 的分支数来讨论 : 一方面, 在这 n 个结点中, 除根以外, 每个结点有一个分支进入, 因此其总分支数为 n-1 另一方面, 这些分支仅从度为 1 和 2 的结点发出, 因而有下面关系式成立 : n-1=n 1 +2n 2 (b) 综合 (a) 和 (b) 两式得 :n 0 =n 2 +1 得证 性质 1 说明了每层结点数目的上限 ; 性质 2 则指出了给定层数的二叉树中的结点数目的上限 ; 性质 3 描述二叉树中叶子结点数目与度为 2 的结点数目的关系 其中性质 1 和性质 2 较为直观, 容易理解 ; 而性质 3 则较抽象, 这不仅是性质本身如此, 且其证明也如此, 这两者都较重要 例 : 如果已知一棵二叉树有 20 个叶子结点, 有 10 个结点仅有左孩子,15 个结点仅有右孩子, 问该二叉树有几个结点? 分析 : 有些初学者在解答此题时, 不会运用所学的性质, 因此只能用硬凑的方法, 先画出一个符合这一条件的二叉树, 然后再数出其结点数, 因而只能算是最笨拙的方法 另外, 即使画出了二叉树, 也很容易将结果数错 如果运用性质 3, 则本题就容易求解 设总结点数为 n, 则由性质 3 的证明过程可知 n=n0+n1+n2, 其中 n0 n1 n2 分别是度为 的结点数 因此, 若知道这 3 个值即得出本题的解 由给定条件可知, n0=20, n1 是只有一个孩子的结点, 因此本题中 n1=10+15=25, 唯一不知的是 n2, 而这可由性质 3 求得, 即 n2=n0-1=19, 由此可知 n= =64 问题 : 一棵二叉树中度为 1 的结点数是否一定比叶子结点数少 解答 : 这两者之间没有必然的联系 下面要讨论的性质 4 涉及到完全二叉树和满二叉树这两种特殊形式的二叉树, 这是两种非常重要的二叉树, 是考核中的常见部分 所谓满二叉树满二叉树是指每层都达到最大数目结点的二叉树, 即高度为 k 的满二叉树中有 2 k -1 个结点, 例如高度为 4 的满二叉树有 2 4-1=15 个结点, 如图 6-5 所示 而完全二叉树完全二叉树则是指在满二叉树的最下层从右到左连续地删除从右到左连续地删除若干个结点所得到的二叉树, 如图 6-6 所示 5

6 n 性质 4: 有 n 个结点的完全二叉树 (n>0), 其深度为 log 2 +1 性质 4 给出了给定结点数的完全二叉树的高度的求解公式, 即有 n 个结点的完全二叉树 n 的高度为 log 2 +1 A B C D E F G H I J K L M N O 图 6-5 高度为 4 的满二叉树示例 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K 11 L 12 M 13 图 6-6 完全二叉树示例 问题 : 已知完全二叉树有 100 个结点, 则该二叉树有多少个叶子结点? 解答 : 许多初学者求解本题时, 容易想当然地给出 37 这一错误答案, 这显然是没有经过仔细思考 下面讨论其求解方法 事实上, 本题有多种求解方法, 此处先给出一种求解方法 本题所给出的完全二叉树有 100 个结点, 因此由性质 4 可知有 7 层, 其中上面 6 层有 63 个结点, 第 7 层有 37 个结点 可以说, 求解出 37 这一错误答案的原因可归结为对完全二叉树叶子结点分布的错误理解 : 认为叶子结点只分布在最下一层 这种错误的求解漏掉了倒数第 2 层 ( 即本题中的第 6 层, 见图 6-7) 的叶子结点 那么, 这一层到底有多少个叶子结点呢? 第 1 层 32 第 6 层 37 第 7 层 6

7 图 个结点的完全二叉树示意图由图 6-7 可知, 第 6 层上的叶子结点是右边那些没有孩子的结点, 其左边则是分支结点 (37 个结点的双亲结点 ) 其中第 6 层的结点数由性质 1 及完全二叉树的定义可知为 32 个 ( 为什么?) 另外, 第 7 层的 37 个叶子结点的双亲结点为 19 个 由分析可知答案为 37+(32-19)=50 问题 : 已知完全二叉树的第 6 层有 5 个叶子, 则该二叉树最多有多少个叶子结点? 解答 : 许多初学者在解答本题时, 很容易出现这样的错误 : 认为二叉树共有 6 层, 因而 用上例的求解方法求得总结点数是 =36, 因而其叶子数是 18 然而, 由于完全二叉树的叶子可能分布在两层上, 因此满足这一条件的完全二叉树可能 有 6 层, 也可能有 7 层 考虑到本题要求的是满足这一条件的最多的叶子结点, 故应选择 7 层的情况 : 上面 6 层是满的, 其中最右边 5 个结点是叶子结点, 因此第 7 层中的叶子结点数 是 =54, 由此可知其叶子结点数是 59 问题 : 判断编号为 i j 的两个结点是否在同一层的方法是 解 : 求解本题时, 先要清楚给定编号的结点所在层次数的规律 是否有此规律呢? 事实 i 上, 性质 4 就提供了所需的规律, 即编号为 I 的结点的层次数为 log 2 +1( 能给出其关系吗?) 因此, 本题答案是 log i 2 +1= j i log 2 +1 或 log 2 = j 2 log 若写成 log2 i =log2 j 行吗? 如果对满二叉树或完全二叉树按照 从上到下, 每层中从左到右, 根结点编号为 1 的 方式编号, 则可发现结点编号之间的的规律, 在许多教材中将此作为性质 5 给出 性质 5: 在编号的完全二叉树中, 各结点的编号之间的关系为 : 编号为 I 的结点如果存在左孩子, 则其编号为 2i, 如果存在右孩子, 则其编号为 2i+1, 如果存在父结点, 则其编号为 i/2 这一关系用图形形式表示如图 6-8 所示 : i/2 i 2i 2i+1 图 6-8 完全二叉树中各结点的编号之间关系在后面讨论顺序存储结构以及在排序算法中要用到这一性质 理解这一性质有助于许多问题的求解 用此性质可以更方便地求解上面的有关叶子结点数的问题, 下面给出其求解过程 解 : 若认为每个结点均已编号, 则最大的编号为 100, 其父结点编号为 50( 见图 6-9), 从 51 到 100 均为叶子, 因此叶子数为 =

8 图 6-7 求解图形示例 100 问题 : 设计算法求编号为 i 和 j 的两个结点的最近的公共祖先结点的编号 解 : 本题有一些难度, 许多读者在求解本题时可能容易这样构思 : 若开始时两个结点不在同一层 ( 如何判断?), 则反复求出低一层结点的父结点的编号 ( 如何求解?), 直到两结点处于同一层为止, 然后再同时求解各自的父结点, 直到遇到同一个结点, 这一结点即是最终解 这种方法较为直观, 但算法设计较繁, 经过分析 归纳可发现, 即使两个结点在同一层, 在没有相遇时也需要继续 上行 因此可这样实现: 若两个结点的编号不相等, 则不管是否在同一层, 大的先上行, 直到两个相等时为止 由此得算法如下 : int common(int i, int j) { while (i!=j) { if (i>j) i/=2; else j/=2; return(i); 二叉树的存储结构 与线性结构类似, 二叉树的存储结构也可采用顺序存储方式和链式存储方式即二叉链表存储方式两类存储形式 1. 顺序存储结构在顺序存储结构中, 不仅要能将结点的值存储起来, 同时还要能体现出结点间的关系 ( 父子关系及兄弟关系 ), 否则便没有任何意义 例如, 如果简单地将所有结点的值 挤 在数组的前 n 个元素中便不能体现出相互间的关系 可采用的存储方式是按完全二叉树的编号次序进行, 即编号为 i 的结点存储在数组中下标为 i 的元素中 这样, 由性质 5 可知, 其左孩子结点在数组中的元素的下标为 2i, 右孩子下标为 2i+1, 其父结点的下标为 (i/2)( 若存在的话 ) 然而这种方法也存在问题 : 若二叉树不是完全二叉树形式, 则为了体现出这种关系, 就不得不要空出许多元素来, 这就造成了空间的浪费, 极端情况下, 仅有 n 个结点的二叉树, 却需要 2 n -1 个元素空间 ( 请描述这样的二叉树的形式 ), 这显然是不能接受的 为此, 要求存储结构还要能合理地利用空间 ( 即依据实际结点数分配存储空间 ), 这就涉及到了动态链表结构 2. 二叉链表结构 在二叉链表存储结构中, 每个结点应包括存储结点的数据部分及两个孩子的指针, 不妨 分别设为 data,lchild,rchild 因此, 这是一个构造型结构, 其结构形式如图 6-10 所示 8

9 T 存储结点值的数据域 A lchild 指向左孩子结点 rchild 指向右孩子结点 图 6-10 二叉链表结点结构 二叉链表结构描述如下 : typedef char datatype; // 不妨设数据类型为字符型 typedef struct bnode { datatype data; struct bnode *lchild, *rchild; Bnode; 用这样的结点所构造的链表中的每个结点有两个分叉的指针分别指向其左右孩子或者说是其左右子树的根指针 ( 尽管可能其值为空 ), 因此这一链表被称为二叉链表 对于一个二叉链表, 如果给出其根指针, 即可由此出发搜索到其余各结点, 因此常用根指针作为二叉链表的名称 如图 6-11 所示的二叉树 ( 链表 ) 的根指针为 T, 因此可称之为二叉树 T 或二叉链表 T T A A B E B E ^ C D F ^ C ^ ^ D ^ ^ F G 图 6-11 二叉树及其对应的二叉链表示例 ^ G ^ 问题 : 在一个有 n 个结点的二叉链表中, 值为空指针域数是多少? 解答 : 在 n 个结点的二叉链表中, 总共有 2n 个指针域, 其中有 ( 除根外的 )n-1 个结点有父结点, 即是其他结点的孩子结点 因此, 在二叉链表中对应地有 n-1 个非空的指针, 也就是说, 空指针数为 2n-(n-1)=n+1 个 6.3 二叉树的遍历 所谓遍历二叉树遍历二叉树是指按某种次序访问二叉树中每个结点一次且仅一次 9

10 二叉树遍历运算是二叉树各种运算的基础 真正理解真正理解这一运算的实现及其含义有助于许多二叉树运算的实现及算法设计 然而, 根据笔者多年的教学经验, 许多初学者对这一部分的学习效果并不理想 这一方面是由于其内在规律的困难所至, 另一方面也是许多初学者难以从教材中的有限篇幅真正理解其深刻的含义, 因此, 对稍稍有些变化的问题就难以求解 为了能深刻地理解有关内容, 下面将先讨论其基本方法和算法实现, 在此基础上讨论其应用, 并给出几个实例 遍历算法的实现 1. 基本遍历方法讨论遍历二叉树的运算由于二叉树的非线性结构形式而变得困难 : 每个结点可能有两个后继 这就使得寻找其所有后继结点变得困难 : 如何保证既不遗漏, 也不地重复访问所有结点 为此, 若采用和线性表同样的方法来进行, 显然要麻烦得多 这就要求我们要换一种构思方式 讨论如下 : (1) 若二叉树 T 为空, 则遍历结束, 否则执行 (2) (2) 不失一般性, 设 T 的形式如图 6-10 所示 T T L R 图 6-10 二叉树一般形式示意图 a) 在这种情况下, 首先, 假设左右子树 L 和 R 能分别遍历出来 ( 即能各自单独地做到 不重复 不遗漏地访问其中的每个结点 ), 并用 L R 分别表示其遍历过程, 则在此基础上 可得到整个二叉树的如下几种次式的遍历 : 先序 : TLR TRL 中序 : LTR RT L 后序 : LRT RLT 先左后右 先右后左 其中第一行中的两个次序的遍历为先访问根结点, 然后再分别遍历其左右子树, 因此称为先根序遍历, 简称为先序遍历 ; 中间一行中的两个次序的遍历中, 访问根结点在遍历其左右子树之间, 因此称为中根序遍历, 简称为中序遍历 ; 最后一行中的两个次序的遍历为后根后根序遍历, 简称为后序遍历, 其中的访问根结点在分别遍历其左右子树之后 此外要注意 : 左边竖排的三个次序都是左子树在右子树之前遍历, 而右边三个则相反 考虑到通常的习惯是先左后右, 因此仅讨论左边一组三种次序的遍历, 即先序次序为 TLR, 中序次序为 LTR, 而后序次序则为 LRT 10

11 现在, 需要讨论的另一个问题是 : 如何实现左右子树的遍历? b) 至于左右子树的遍历, 可采用与整个二叉树相同的方式来遍历, 即在先序遍历中, 其左右子树 L R 也分别采用先序方式来进行 这同样运用于其更低层次子树的遍历 对中序和后序遍历的讨论也相同 在本章后面的讨论中, 你将看到 : 以上的讨论过程将适用于二叉树各种运算的实现的讨论 基于以上讨论可知, 对二叉树 T 的先序遍历可描述为 : 若二叉树 T 不空, 则 : 1 访问 T 的根结点 2 先序遍历 T 的左子树 3 先序遍历 T 的右子树 有关算法在后面给出 2. 有关遍历方法的例题在阅读过以上有关遍历的分析和讨论之后, 是否能真正理解其求解过程呢? 其实不然 许多初学者对此仍有一些模糊的认识, 例如 : (1) 容易将遍历方法中所提及的 对左 右子树的遍历 演变成对 左 右孩子的访问, 因而只能考虑到三个结点的访问 (2) 一种较为普遍的担心是 : 这种方法能否访问到所有结点, 因为其中仅涉及到对根结点的访问和对子树的遍历 为此, 请各位初学读者严格按照下面的要求来练习 例 : 假设访问二叉树 T 的结点的操作是打印结点的值, 请分别写出图 6-13 所示的二叉树的先序 中序和后序序列 T A B F C D G I E H J 图 6-13 二叉树 解答 : 为了写出各遍历序列, 我们采用 分步填空 的方式, 即对整个二叉树来说, 先 写出其遍历序列的三部分, 即根结点 左右子树遍历序列 由于其中的左右子树的遍历序列 暂时还不知道, 因此先用空格来占位置, 待下一步继续分解 例如 : 在求先序时, 先写出如 下的序列 : (1)A AL(A 的左子树 )AR(A 的右子树 ) 然后对 A 的左右子树 AL 和 AR 分别用同样的方法, 即也是按三部分划分 填空的方式 进行 因此, 对每个结点来说, 都是先写出以此为根的子树的遍历序列的三部分, 而将其中 未知部分先用空格来占位, 然后对其进行分解, 直到全部填完空为止 该问题的求解序列如 下 : (2)A B F 11

12 B BL BR F FL FR AL AR (3)A B C DE FG H IJ BL BR FL FR AL AR (4) 由此可知先序遍历序列为 ABCDEFGHIJ 以同样的方式可得其它遍历序列分别如下, 在此不再细述, 请读者自己练习 中序 :CBEDAGHFJI 后序 :CEDBHGJIFA 下面讨论另一类有关遍历方法的问题 : 由二叉树遍历序列求解出二叉树 在熟练掌握了二叉树遍历方法之后, 我们可以运用其遍历思想求解与本题相反的问题, 即由二叉树的序列构造出 ( 或还原出 ) 二叉树 这类问题的求解可进一步加强对遍历方法的理解 现在的问题是 : 由二叉树的什么序列可以唯一确定一棵二叉树? 可以证明, 由二叉树的先序和后序序列不能唯一确定一棵二叉树, 但由二叉树的先序和中序或后序和中序序列能唯一确定一棵二叉树 下面通过实例来讨论这一求解过程 例 : 已知二叉树的先序和中序序列如下, 试构造出相应的二叉树 先序 :ABCDEFGHIJ 中序 :CDBFEAIHGJ 解答 : 由二叉树的结构可知, 如果能由这两个序列确定出根结点, 并分别构造出左右子树即完成了问题的求解 因此, 下面分别讨论这两个问题的求解 : 1 根结点的确定 : 由先序遍历的描述可知, 先序序列中的第一个结点为根结点 因此, 本题中的根为 A 2 左右子树的确定 : 在中序序列中, 根结点处于左右子树的中序序列之间, 因此本题中的根结点 A 将左右子树的中序序列划分为 (CDBFE) 和 (IHGJ) 现在, 如果能知道左右子树的先序序列, 即可由此而采用相同的方式分别构造出左右子树, 从而完成本题的求解 由先序遍历方法的描述可知, 左 右子树的先序序列在先序序列中也是连在一起的, 分别为 BCDEF 和 GHIJ 因此, 左子树的构造需要由其先序序列 BCDEF 和中序序列 CDBFE 来求解, 右子树的构造需要由其先序序列 GHIJ 和中序序列 IHGJ 来求解, 而这又和原题形式相同, 因此可采用同样的方式, 即由先序序列确定根, 中序序列分左右, 求解过程如图 6-15 所示 A A 先序 中序 BCDEF CDBFE GHIJ IHGJ B G CD CD EF FE HI IH J J A B G 12

13 C E H J D F I 图 6-15 求解过程示意图 3. 遍历算法 从以上对遍历方法的讨论可知, 对二叉树的遍历是在对各子树分别遍历的基础之上进行 的 由于各子树的遍历和整个二叉树的遍历方式相同, 因此, 可借助于对整个二叉树的遍历 算法来实现对左右子树的遍历 也就是说, 要采用递归调用方式来实现对左右子树的遍历 具体地说, 就是 : 在先序遍历以 T 为根 ( 指针 ) 的二叉树 ( 即二叉树 T) 时, 在访问过根结 点之后, 要分别对以根结点 *T 的左右孩子为根的子树 ( 根指针分别为 T->lchild 和 T->rchild) 进行先序遍历 如果用 preorder 表示先序遍历算法的名称, 则可得到先序遍历算法如下 : void preorder (Bnode *T) // 先序遍历以 T 为根指针的二叉树的算法 { if (T!=NULL) { visite(t); // 访问 T 的根结点 preorder(t->lchild); // 先序遍历 T 的左子树 preorder(t->rchild); // 先序遍历 T 的右子树 ; 其中访问结点的操作 visite(t) 在不同的场合下可以有不同的要求, 其中最常用的操作是 打印结点的值, 因而此处没有给出其具体的操作 类似地, 我们可以得到中序遍历 ( 一般用 inorder 表示算法的名称 ) 和后序遍历 ( 一般 用 postorder 表示算法的名称 ) 算法如下 : void inorder(bnode *T) // 中序遍历以 T 为根指针的二叉树 T 的算法 { if (T!=NULL) { inorder(t->lchild); // 中序遍历 T 的左子树 visite(t); // 访问 T 的根结点 inorder(t->rchild); // 中序遍历 T 的右子树 void postorder(bnode *T) // 后序遍历以 T 为根指针的二叉树 T 的算法 { if (T!=NULL) { postorder(t->lchild); // 后序遍历 T 的左子树 postorder(t->rchild); // 后序遍历 T 的右子树 visite(t); // 访问 T 的根结点 4. 遍历算法执行过程实例 关于递归程序 ( 函数 ) 的执行过程, 在有关递归的部分给出, 尽管如此, 仍有许多初学 者可能会不甚理解 为此, 下面通过模拟算法对一棵二叉树的遍历的过程来体会遍历算法 例 : 模拟算法对图 6-16 二叉树中序遍历的执行过程 T 13

14 A B G C D H E F I 图 6-16 二叉树示例解答 : 按前面所讨论的方法及中序遍历算法可知, 执行 inorder(t) 等价于依次执行下面三个操作, 即 inorder(t->lchild),visite(t),inorder(t->rchild) 为简化描述及区分所指示的结点, 下面用方框框住输出结点的值来代替 visite 操作 Inorder 中的指针参数也用该结点的值来代替 若指针为空, 则用 ^ 表示 例如, 整个二叉树的调用为 inorder(a), 其三个等价替换为 :inorder(b);a;inorder(g); 其中值的形式也只是一种符号形式 由此可得算法执行的过程如图 6-17 所示 inorder(a) inorder(b) A inorder(g) inorder(c) B inorder(d) inorder(h) G inorder(^) inorder(^) C inorder(^) inorder(^) H inorder(i) inorder(e) D inorder(f) inorder(^) E inorder(^) inorder(^) F inorder(^) 图 6-17 遍历过程示意图由图可知其输出序列是 :CBEDFAHIG 5. 遍历算法的简单应用如前所述, 遍历算法中对每个结点进行一次访问操作, 而访问结点的操作可以是多种形式及多个操作, 例如输出结点的值 利用这一特点, 适当修改访问操作的内容, 便可得到许多问题的求解算法 下面给出几个典型问题的求解 例 : 设计算法按中序次序打印二叉树 T 中度为 2 的结点 解 : 本算法的要求与中序遍历算法既有相同之处, 又有不同之处 相同之处是输出次序 均为中序, 不同之处是此处不是输出每个结点, 而是仅输出其中的度为 2 的结点 即为有条件输出 为此, 将中序遍历算法中的访问操作改为条件输出即可 考虑到结点值的类型可能是多个类型, 为此, 采用 C++ 中的输出语句来输出表达式的值 算法如下 : 14

15 void { inrder(bnode *T) // 按中序次序输出二叉树 T 中的度为 2 的结点 if (T!= NULL) { inorder(t->lchild); // 按中序次序输出左子树中满足条件的结点 if (T->lchild!=NULL && T->rchild!=NULL) cout<< T->data; // 判断结点满足条件时输出结点的值 inorder(t->rchild); // 按中序次序输出右子树中满足条件的结点 例 : 设计算法求二叉树 T 的结点数 解 : 本算法不是要打印每个结点的值, 所要求的仅是求出其中的结点数 我们可适当修改遍历算法以完成要求 : 将某一遍历算法中的访问结点的操作改为计数操作, 即将该结点的数目 1 累加到一个全局变量 n 中 ( 显然,n 的初值应为 0), 每个结点都这样做一次即完成了结点数的求解 算法如下 : void Inorder(Bnode *T) // 将二叉树 T 中的结点数累加到全局变量 n 中, 其中 n 的初值为 0 { if (T!= NULL) { Inorder(T->lchild); // 将左子树中的结点数累加到 n 中 n++; // 计数 Inorder(T->rchild); // 将右子树中的结点数累加到 n 中 例 : 设计算法按中序次序输出二叉树 T 的第 K 个结点的值 (K>0) 解 : 由于该问题要求按中序次序进行, 因此需在中序遍历算法的基础上进行变化 所不同的是此处仅要求输出一个结点, 而不是全部 某结点是否输出取决于其在序列中的序号是否为 K, 因而需要在访问每个结点的同时计数, 以便于判断 而这正是前面所讨论的计数类问题 由此得算法如下 : void Inorder(Bnode *T) // 按中序次序输出二叉树 T 的第 K 个结点的值, 其中全局变量 n 的初值为 0 { if (T!= NULL) { Inorder(T->lchild); n=n+1; if (n==k) cout<<t->data; // 结点满足条件时输出 Inorder(T->rchild); 15

16 6.4 线索二叉树 线索二叉树结构 在二叉树中经常可能会要求求解某结点在某种次序下的前趋或后继结点, 并且各结点在每种次序下的前趋 后继的差异较大 例如, 图 6-19 中的二叉树的结点 D 在先序次序下的前趋 后继分别是 C E; 在中序次序中的前趋 后继分别是 E F; 在后序次序的前趋后继分别是 F B 这种差异使得求解较为麻烦 A B G C D H E F I J 图 6-19 二叉树如何实现这一问题的快速求解? 对此有几种考虑 : (1) 遍历 通过指定次序的遍历发现结点的前趋或后继 例如, 为求图 6-19 中结点 D 的先序前趋, 则对整个二叉树先序遍历, 看看哪个结点之后是结点 D, 则该结点就是 D 的先序前趋 以同样的方式可求出各结点在各种次序下的前趋和后继 尽管如此, 但由于这类方法太费时间 ( 因为对每个结点的求解都要从头开始遍历二叉树 ), 因此不宜采用 (2) 增设前趋和后继指针 在每个结点中增设两个指针, 分别指示该结点在指定次序下的前趋或后继 这样, 就可使前趋和后继的求解较为方便, 但这是以空间开销为代价的 是否存在既能少花费时间, 又不用花费多余的空间的方法呢? 下面要介绍的第三种方法就是一种尝试 (3) 利用二叉链表中的空指针域, 将二叉链表中的空的指针域改为指向其前趋和后继 具体地说, 就是将二叉树各结点中的空的左孩子指针域改为指向其前趋, 空的右孩子指针域改为指向其后继 称这种新的指针为 ( 前趋或后继 ) 线索, 所得到的二叉树被称为线索二叉树, 将二叉树转变成线索二叉树的过程被称为线索化线索化 线索二叉树根据所选择的次序可分为先序 中序和后序线索二叉树 例如, 前图中二叉树的先序线索二叉树的二叉链表结构如下图 (a) 所示, 其中线索用虚线表示 : A 16

17 B G C D H E F I J 空指针 (a) 未加区分标志的先序线索二叉树的二叉链表示例 0 A 0 0 B 0 0 G 1 1 C 1 0 D 0 1 H 0 1 E 1 1 F 1 0 I 1 1 J 1 空指针 (b) 先序线索二叉树示例图 6-20 线索二叉树的二叉链表形式示例然而, 仅仅按照这种方式简单地修改指针的值还不行, 因为这将导致难以区分二叉链表中各结点的孩子指针和线索 ( 虽然由图中可以 直观地 区分出来, 但在算法中却不行 ) 例如, 图 6-20 中结点 C 的 lchild 指针域所指向的结点是其左孩子还是其前趋? 为此, 在每个结点中需再引入两个区分标志 ltag 和 rtag, 并且约定如下 : ltag=0: lchild 指示该结点的左孩子 ltag=1: lchild 指针该结点的前趋 rtag=0: rchild 指示该结点的右孩子 rtag=1: rchild 指针该结点的后继 这样一来, 上图 6-20(a) 中的二叉链表就变成了图 6-20(b) 所示的样子 这就是线索二叉树的内部存储结构形式 为简便起见, 通常将线索二叉树画成如图 6-21 所示的形式 A C D H B G E F I 17

18 B J (a) 先序线索二叉树 A G A C D H E F I J (b) 中序线索二叉树 B G C D H E F I J (c) 后序线索二叉树 图 6-21 线索二叉树示例 问题 : (1) 线索二叉树的二叉链表中是否还存在空的指针域? 为什么? 是否各种线索二叉树中的空指针域个数都相同? (2) 如何判断线索二叉树中的结点为叶子结点? 设计算法求解其叶子结点数 (3) 分析在各种线索二叉树中求解相应结点的前趋 后继结点的情况, 并设计出求解算法 线索二叉树中前趋后继的讨论 下面讨论在线索二叉树中求解前趋和后继的方法, 共有六个问题的求解 ( 一 ) 先序后继的求解在先序线索二叉树中求解指针 P 所指结点 ( 即 *P) 的后继结点的指针 分析 : 此处所谓 *P 的先序后继即是在先序序列中紧跟在 *P 后面的结点 按先序遍历的定义, 以 P 为根指针的子树的遍历次序是 P PL RR 其中 P 代表 P 所指结点,PL 代表先序遍历 P 所指结点的左子树,PR 代表先序遍历 P 所指的右子树 由这一顺序可知 : (1)*P 有左孩子 ( 即左子树不空 ), 则其左子树 PL 中的第一个元素就是 *P 的后继, 而 PL 中的先序序列的第一个结点即是其根结点, 即 P 的左孩子 ( 指针为 P->lchild) (2) 否则, 若 *P 有右孩子, 则其右孩子就是其后继, 其指针为 P->rchild (3) 否则,P->rchild 即是后继线索, 由此可得求解先序后继的算法 Bnode *presuc(bnode *P) {if (P->ltag==0) 18

19 return(p->lchild); else return(p->rchild); 2 先序前趋的求解在先序线索二叉树中求出 P 所指结点的前趋结点 分析 : 按先序遍历的定义,*P 的前趋一定不在其子树中, 因而按下面几种情况来讨论 : (1) 若 *P 是二叉树的根, 则不存在前趋 (2) 否则, 若 *P 是其父结点 ( 不妨用 D 代表 ) 的左孩子, 则以 D 为根的二叉树的先序遍历序列为 :D,DL (P,PL,PR),DR, 其中 D 代表指向 D,(P,PL,PR) 构成 D 的左子树 DL 的先序遍历,DR 表示先序遍历 D 的右子树 由序列可知,P 的先序前趋是其父结点 D 由于在二叉链表中没有指针指向父结点, 因而其求解是较困难的 ( 除非 P 的左孩子指针为前趋线索 ) (3) 若 *P 是其父结点 D 的右孩子, 则以 D 为根的子树的遍历序列为 :D,DL,DR(P, PL,PR) 此时可能有两种情况: (a)*p 没有左兄弟, 即 DL 为空, 则其父结点 D 是其先序前趋 (b) 否则,*P 的左兄弟子树中的最后一个结点就是其前趋, 而这一结点是其左兄弟子树中的最右下的叶子结点 ( 为什么?) 无论是 (a) 还是 (b), 在线索二叉树中都是难以求解的 综合上述几种情况可知, 在先序线索二叉树中求解结点的先序前趋是难以实现的 3 中序后继的求解在中序线索二叉树中求出 P 所指结点的中序后继 分析 : 设 *P 的左右子树分别为 PL 和 PR, 由于中序遍历的次序为 PL,P,PR, 因此, 其求解讨论如下 : (1) 设 P 的右子树 PR 不空, 则 PR 中的第一个结点为 *P 的后继 现在问题是 :PR 中的第一个结点有什么规律? 如何求解? 下面先分析这一问题的求解方法 不妨设二叉树形式如图 6-22 所示 : P PR t1 t2 t3 t4 图 6-22 二叉树 若 t1 的左子树为空, 则 t1 为 PR 的第一个结点, 否则,PR 中的第一个中序结点应在子 树 t2 中 类似地, 若 t2 的左子树为空, 则 t2 为 PR 的第一个结点, 否则,PR 的第一个中序 19

20 结点应在子树 t3 中 以此类推可知, 其求解过程就是沿着箭头方向向左下下滑到第一个没有左孩子的结点 也就是说,PR 中的第一个结点就是在以 PR 为根的子树中的最左下的第一个没有左孩子的结点 (2) 若 PR 为空 ( 即 *P 无右孩子 ), 则 *P 的右孩子指针为后继线索, 即 P->rchild 为其中序后继的指针 综合上述分析可得中序后继算法 : Bnode *insuc(bnode *p) {node *q=p->rchild; if (p->rtag==1) return(q); else { while (q->ltag==0) q=q->lchild; // 沿左下方向搜索 return(q); 4 中序前趋的求解在中序线索二叉树中求出 P 所指结点的中序前趋 分析 : 中序前趋的求解与中序后继的讨论方法类似, 所不同的是两个算法中要左右对换 因此算法从略 5 后序前趋的求解在后序线索二叉树中求出 P 所指结点的后序前趋 分析 :*P 的后序前趋即是在后序序列中在 *P 前面的结点 按后序遍历的定义, 以 P 为根指针的子树的遍历次序是 PL,PR,P( 有关符号的描述同前 ) 由这一顺序可知: (1)*P 有右孩子 ( 即右子树不空 ), 则其右子树 PR 中的最后一个元素就是 *P 的前趋, 而 PR 中的后序序列的最后一个结点即是其根结点, 即 P 的右孩子 ( 指针为 P->rchild) (2) 否则, 若 *P 有左孩子, 则其左孩子就是其前趋, 其指针为 P->lchild (3) 否则,P->lchild 即是其前趋线索, 由此可得求解后序前趋的算法 Bnode *postpre (Bnode *P) {if (P->rtag==0) return(p->rchild); else return(p->lchild); 6 后序后继的求解在后序线索二叉树中求出 P 所指结点的后序后继 分析 : 按后序遍历的定义,*P 的后继一定不在其子树中, 因而按下面几种情况来讨论 : (1) 若 *P 是二叉树的根, 则不存在后序后继 (2) 否则, 若 *P 是其父结点 ( 不妨用 D 代表 ) 的右孩子, 则以 D 为根的二叉树的后序遍历序列为 : DL,DR(PL,PR,P),D 由序列可知,P 的后序后继是其父结点 D 由于在二叉链表中没有指针指向父结点, 因而其求解是较困难的 ( 除非 P 的右孩子指针为线索 ) 20

21 (3) 若 *P 是其父结点 D 的左孩子, 则以 D 为根的子树的遍历序列为 :DL(PL,PR,P), DR,D 此时可能有两种情况: (a)*p 没有右兄弟, 即 DR 为空, 则其父结点 D 是其后序后继 (b) 否则,*P 的右兄弟子树中的第一个结点就是其后序后继, 而这一结点是其右兄弟子树中的最左下的叶子结点 ( 为什么?) 无论是 (a) 还是 (b), 在线索二叉树中都是难以求解的 综合上述几种情况可知, 在后序线索二叉树中求解结点的后序后继是难以实现的 6.5 树和森林 在系统地学习了二叉树之后, 就可以较好地学习树和森林的有关内容了, 这部分包括树和森林的存储形式, 树 ( 森林 ) 与二叉树之间的相互转换, 树 ( 森林 ) 的遍历等 为描述方便起见, 在不作特别说明的情况下, 树包括森林 树的存储结构 树有多种存储结构, 其中最常见的是双亲表示法 孩子链表表示法和二叉链表表示法 熟悉这些存储形式, 并能写出以这些存储结构形式存储的树的算法是基本要求 然而, 其中 有些算法比二叉树可能要复杂些, 因此要注意 一 双亲表示法 : 双亲表示法通过给出树中每个结点的双亲来表示树 由于每个结点最多有一个双亲结 点, 因此结点的的存储信息包括两部分 : 本身值 data 和双亲地址 例如图 6-26(a) 中的树 的双亲表示如图 6-26(b) 所示 其中根结点 A 的双亲地址不存在, 不妨值设为 -1 A B C D E F G H I J K (a) 原树 图 6-26 树的双亲表示法示例 有关其存储结构的说明包括两部分 : 结点的说明和存储数组的说明 struct { tnode datatype data; data parent 0 A -1 1 B 0 2 C 0 3 D 0 4 E 1 5 F 1 6 G 1 7 H 2 8 I 2 9 J 3 10 K 4 (b) 双亲表示法 21

22 int parent; ; struct tnode treelist[maxnum]; 其中 parent 指示父结点的下标,data 存放结点的值 分析 : 这种方法便于搜索相应结点的父结点及祖先结点, 但若要搜索结点的孩子结点及其后代结点, 则需搜索整个表, 因此较费时间 若要求方便地搜索其后代结点, 则需要重新选择存储结构 问题 : (1) 如果是一棵森林, 应如何用双亲表示法表示? 二 孩子链表表示法 : 孩子链表表示法就是分别将每个结点的孩子结点连成一个链表, 然后将各表头指针放在 一个列表中构成一个整体结构, 如图 6-26(a) 所示的树用孩子链表表示法表示如图 6-27 data children 0 A ^ 1 B ^ 2 C 3 D 7 8 ^ 4 E 9 ^ 5 F 6 G 10 ^ 7 H 8 I 9 J 10 K 图 6-27 孩子链表表示法其类型描述如下 : typedef struct listnode { int data; listnode *next; listnode; typedef struct arrelemnt { datatype info; listnode *firstchild; arrelemnt; arrelemnt tree[maxnum]; 分析 : 与双亲表示法相反, 这种结构便于搜索任意结点的孩子结点及后代结点, 但不便 22

23 于搜索各结点的双亲结点和祖先结点 在某些情况下, 为了同时便于双亲和孩子结点的搜索, 可以将这两种表示方法结合起来, 构成双亲 - 孩子结构表示法 三 孩子 - 兄弟链表表示法 : 所谓孩子 - 兄弟链表表示法是指以这样的链表来存储树和森林, 对树中每个结点用一个 链表结点存储 每个链表结点中除了存放结点的数据外, 还有两个指针, 一个用于指示该结 点的第一个孩子, 另一个用于指示该结点的下一个兄弟结点, 故有此名 各结点结构如图 6-28 所示 图 6-26(a) 中的树的孩子兄弟链表结构如图 6-29 所示 例如 : 森林所对应的孩子 - 兄弟链表表示法 firstson T data 图 6-28 孩子 兄弟链表结点结构 nextbrother A B C D ^ ^ H ^ I ^ J ^ E ^ F ^ G ^ ^ K ^ 图 6-29 孩子 - 兄弟链表表示法示例若将该链表按顺时针方向旋转 45 0, 如下图所示, 可以看出该链表事实上就是前面所介绍的二叉树的存储结构之一, 即二叉链表结构, 而每个二叉链表对应唯一一棵二叉树, 由此可知, 每棵树对应唯一一棵二叉树 也正因为如此, 将二叉链表表示法称为二叉链表表示法或二叉树表示法 T A ^ B E C 23

24 ^ K ^ ^ F ^ H D ^ ^ G ^ ^ I ^ J ^ 图 6-30 对应的二叉链表示例如果要存储森林的话, 可以这样实现 : 将每棵树的根结点看作是兄弟结点, 在这种约定下即可方便地实现森林的存储 二叉链表存储结构的描述与二叉树存储结构的描述相同, 主要说明结点的结构 每个结点 ( 不妨用 tnode 表示其类型 ) 中由三部分组成 : 即结点的值 ( 不妨用 data 表示 ), 指向第一个孩子结点的指针 ( 不妨记为 firstson) 和指向下一个兄弟结点的指针 ( 不妨记为 nextbrother) 描述如下: typedef struct tnode { datatype data; struct tnode *firstson, *nextbrother; Tnode; 由于树和森林可以转换为二叉链表存储形式, 因此可借助于二叉树问题的求解方法实现对树和森林的运算 由此可进一步体会到二叉树运算的基础性 树 ( 森林 ) 与二叉树的转换 : 借助于孩子 - 兄弟链表表示法, 可以将森林转化成唯一的一个二叉链表结构或二叉链表 ; 反之由二叉链表也可唯一地对应到一个森林 因此, 可将森林转换为二叉树的形式, 并借助于二叉树的有关算法实现对森林的运算 这样就需要实现树 ( 森林 ) 与二叉树的相互转换 一 森林到二叉树的转换 : 由前面的存储结构可知, 若要将森林转换为二叉树, 则需将森林中的每个结点进行这样 的转换 : 让其左边指针指向其第一个孩子 ( 或为左孩子形式 ), 让其右边指针指向其下一个 兄弟 森林中各树的根当作兄弟来转换, 如果森林用有序表 E(T1,T2, Tm) 来表示, 则将 森林 T=(T1,T2, Tm), 转换为二叉树 BT 形式化的 ( 递归地 ) 描述如下 : 如果 m=0,bt 为空 ; 否则 将 T1 的根作为 BT 的根 ; 将 T1 的子树森林转换为 BT 的左子树 ; 将 (T2 T3 Tm) 转换为 BT 的右子树 这一描述用的是递归形式的描述, 由描述可知, 转换过程可分三部分 : 即根 子树 及兄弟森林三部分, 而第二 第三部分的求解与原题求解类似 例如, 对图 6-32(a) 中的森林的转换的层次如图 6-32 所示, 其中各层次中的一个整体用一个框框住, 并用编号标注 限于篇幅, 并没有将所有层次都标注出来 24

25 A L O B C D M N P E F G H I J K (a) 待转换的森林示例 1 二叉树的根 A L O B 2.3 C D M N P E F G H I J 对应右子树 K 对应左子树 (b) A 转换过程及对应关系描述 B L E C M O K F H D N P G I J (c) 转换结果 图 6-32 将森林转化为二叉树的过程二 二叉树到森林的转换 : 求解这一问题显然是前面所讨论问题的逆问题, 在实现将二叉树转换为对应的树 ( 森林 ) 时, 要记住这样的规律 : 将二叉树中每个结点的左孩子看为所对应树中的第一个孩子, 而其 右孩子则是树中的下一个兄弟, 因此, 应与其一样连到相同的父结点上 ( 除非没有父结点 ) 由此可得到将二叉树 BT 转换为森林 T=(T1,T2 Tm) 的形式化描述 : 若 BT 不空, 则 : BT 的根对应为 T1 的根 ; 25

26 BT 的左子树对应为 T1 的子树森林 ; BT 的右子树对应为 (T2, Tm) 有关例子不再列举 问题 : (1) 图 6-34 中的二叉树转换为对应的森林 A B C D E F G H I J K L M N O 图 6-34 二叉树 (2) 已知二叉树的先序序列为 ABCDE, 且所对应的树高度为 5, 画出该二叉树所对应的树 (3) 设计算法将二叉树转换为对应的森林 树 ( 森林 ) 的遍历 和二叉树等结构类似的是, 遍历算法也是树 ( 森林 ) 的基本算法 根据访问根结点和访 问子树中的结点之间的次序关系, 树的遍历可分为先序和后序遍历 所谓先序遍历, 就是每 个结点在其所有子树之前访问 ; 所谓后序遍历, 就是每个结点在其所有子树之后访问 一 先序遍历森林先序遍历森林 T=(T1,T2 Tm) 的描述如下 : 若 T 不空, 则 : 访问 T1 的根 ; 先序遍历 T1 的子树森林 ; 先序遍历森林 (T2,T3 Tm); 由此描述可知, 森林的先序遍历过程也可采用前面所介绍的二叉树遍历的填空方法来 描述, 请有兴趣的读者自己练习 图 6-35 中的所示森林的先序遍历所产生的先序序列为 : ABEKFGCHIDJLMNOP A L O B C D M N P E F G H I J 26

27 K 图 6-35 森林 若将此结果和对应的二叉树的先序序列相比, 发现两者完全相同 这显然不是巧合 通过体会和分析森林与二叉树之间的相互转换过程的描述可知, 两者之间的相同是由其内在 的对应关系所决定的, 由归纳法也可证明这一点 如果采用前面的类型描述, 则先序遍历森林的算法如下 : void preorder(tnode *t) { if(t!=null) // 先序遍历森林 { visite(t); // 访问结点 preorder(t->firstson); preorder(t->nextbrother); 二 后序遍历森林后序遍历森林 T=(T1,T2 Tm) 的方法描述如下 : 如果 T 不空, 则 : 后序遍历 T1 的子树森林 ; 访问 T1 的根 ; 后序遍历森林 (T2,T3 Tm) // 先序遍历 t 的子树森林 // 先序遍历 t 的兄弟森林 也请读者对图 6-35 中的森林模拟其后序遍历过程, 所得的后序遍历序列为 KEFGBHICJDAMNLPO 将这一序列与所对应的二叉树的中序序列相比, 发现两者也相同! 事实上, 可以证明, 对任意一个森林, 其后序遍历序列与所对应的二叉树的中序序列相同 由后序遍历的描述及 转换过程也可发现这一关系 也正因为如此, 有些教科书中将这一方法称为中序方法, 但笔 者认为不太合适, 因为这是针对树和森林而不是针对二叉树进行的遍历 假设用二叉链表表示, 则后序遍历算法如下 : void postorder(tnode *t) {if (t!=null) {postorder(t->firstson); visite(t); postorder(t->nextbrother); // 后序遍历第树 t 的子树森林 // 访问第树 t 的根结点 // 后序遍历 t 的后续兄弟森林 27

28 6.6 哈夫曼树 引言 在软件设计以及许多数据处理中, 经常需要对数据进行压缩, 以节省存储空间 压缩的基本原理是什么? 本节要介绍的哈夫曼树便为压缩提供了一种基本的方法 在介绍有关内容之前, 下面先看一个例子 : 例 : 设计一个将百分成绩转换转换为等级制的算法, 具体要求如下 : A:90~100 B:80~89 C:70~79 D:60~69 E:0~50 分析 : 对学过程序设计课程的读者来说, 这一问题较为简单, 有多种求解方法 例如图 6-37 中的几个流程图都能正确地求解 N S>=90 Y Y S<60 N N S>=80 Y A E Y S<70 N N S>=70 Y B D Y S<80 N N S>=60 Y C C Y S<90 N E D B A (a) (b) Y S>=70 N Y S>=80 N Y S>=60 N Y S>=90 N C D E A B (c) 图 6-37 流程图然而, 不同的方法在时间性能上有很大的差异 可能有的读者对此感到不解, 看不出这些算法转换一个成绩表的时间性能上的差异 事实上, 此处所谓的时间性能指的是统计意义 28

29 上的, 即对大批量数据处理时的时间性能 假设算法要转换 个成绩, 各区间的分布如下 : 90~100 5% 80~89 20% 70~79 30% 60~69 25% 0~59 20% 由这一分布可知, 在图 6-37(a) 中, 每个 A 格的成绩只需判断一次即可 ;B 格的则需 2 次判断 ;C 格的需 3 次 ;D E 格的需 4 次 因此, 对 个成绩来说, 共需的判断次数是 : =31500 次用图 6-37(b) 来判断, 需要 : =26000 次用图 6-37(c) 来判断, 需要 : =22500 次由此可知, 不同的判断方法的判断次数是有差异的 现在问题是, 如何判断才能保证时间最少? 更进一步来说, 对任一类似的问题, 如何判断才能最省时间? 下面来讨论说明 问题描述及求解方法 如果注意观察一下, 就可发现, 流程图有点像一棵二叉树, 其中分支 ( 判断 ) 结点对应于二叉树的分支结点 ; 而每个结论 ( 推出什么 ) 则对应于二叉树的叶子结点 ; 得到一个结论所作的比较次数则是从根结点到该叶子结点的分支数 ( 比层次数少 1); 每个结论成立的次数作为叶子结点的权值 因此, 上述问题可借助于二叉树这一模型来描述 : 给定一组数值 {w1,w2, wn 作为叶子结点的权值, 构造一棵二叉树 如果 wili 最小, 则称此二叉树为最优二叉树, 也称哈夫曼树哈夫曼树 并称 wili 为带权路径长度 如何构造哈夫曼树呢? 哈夫曼 (Huffman) 给出了一个带有一般规律的算法, 俗称哈夫曼算法 描述如下 : (1) 根据给定的 n 个权值 {w 1,w 2,,w n, 构成 n 棵二叉树的集合 T={T 1,T 2,,T n, 其中每个 T i 只有一个带权为 w i 的根结点, 其左右子树均空 (2) 从 T 中选两棵根结点的权值最小的二叉树, 不妨设为 T 1 T 2 作为左右子树构成一棵新的二叉树 T 1, 并且置新二叉树的根值为其左右子树的根结点的权值之和 (3) 将新二叉树 T 1 并入到 T 中, 同时从 T 中删除 T 1 T 2 (4) 重复 (2) (3), 直到 T 中只有一棵树为止 这棵树便是哈夫曼树 例 : 以集合 {3,4,5,6,8,10,12,18 为叶子结点的权值构造哈夫曼树, 并计算其带权路径长度 求解 : 按构造算法, 首先将这些数变成单结点的二叉树集合 T={ 3, 4, 5, 6, 8, 10, 12, 18 29

30 然后从 T 中选出两个根值最小的二叉树 { 3, 4 作为左右子树造出一棵新的二叉树, 根为 T, 同时从 T 中去掉这两棵子树 然后再重复这一操作过程, 即选择最小的两个子树构造一棵新的二叉树, 直到 T 中仅有一棵二叉树为止 操作过程如下 : 选定根值最小的两棵树 ( 分别为 3 和 4) 构成一棵树, 结果如下 : T={ 7, 5, 6, 8, 10, 12, 从 T 中选择根值为 5 和 6 的两棵树构成一棵树, 结果如下 : T={ 7, 11, 8, 10, 12, 从 T 中选择根值为 7 和 8 的两棵树构成一棵树, 结果如下 : T={ 11, 15, 10, 12, 从 T 中选择根值为 10 和 11 的两棵树构成一棵树, 结果如下 : T={ 21, 15, 12, 从 T 中选择根值为 12 和 15 的两棵树构成一棵树, 结果如下 : T={ 18, 21, 从 T 中选择根值为 18 和 21 的两棵树构成一棵树, 结果如下 : T={ 39, 27 30

31 合并这两棵树构成一棵树, 结果如下 : T={ 带权路径长度 WPL=( ) 4+(8+10) 3+(12+18) 2=186 现在, 我们对这一哈夫曼树作一个计算 : 将所有分支结点的值加起来, 即 =186 这一值正好等于带权路径长度 可以证明 ( 请读者自己证明 ), 任一棵哈夫曼树的带权路径长度均具这一性质 根据这一性质求解 WPL 要快捷得多 问题 : 若给定作为叶子结点权值的数值的个数为 n, 则所构造的哈夫曼树中的结点数是多少? 求解 : 由构造算法可知, 每次合并操作要增加一个结点, 同时树的数目减 1, 因此要合并 n-1 次, 也即增加了 (n-1) 个分支结点 由此可知, 整个二叉树的结点数是 2n-1 也可从另一角度来求解 : 由构造过程可知, 树中不存在度为 1 的结点 由二叉树的性质 3 可知,n2=n-1, 因此总结点数是 n+(n-1)=2n-1 问题 : 设计算法求解给定哈夫曼树的带权路径长度 求解 : 本题的求解既可按定义来求解, 也可按前面所介绍的方法求解 下面按定义来设计算法 分析, 要按定义求解 WPL, 需要解决如下几个问题 : (1) 算法中对每个叶子结点求解时要能知道该叶子结点到根的路径长度 (2) 所求解的每个叶子结点的带权路径长度要能累加起来以得到整个哈夫曼树的 WPL 对 (1) 可象前面二叉树遍历算法那样, 设置一个参数 ( 不妨设为 k) 以指示当前结点到根的路径长度 显然, 根结点对应的 k 值为 0, 每当对其子树递归调用时, 就将这一参数值设置为 k+1 对 (2), 为了将所有叶子结点的求解合在一起, 可采用两种方式, 一是将算法设计为无值函数, 并设置一个全程变量用于累加整个树中各叶子结点的带权路径长度, 因此在算法调用时要将其初值设置为 0; 另一种方法是将算法设置为函数形式, 用于返回当前子树中所有叶子结点的带权路径长度之和 两种算法分别如下 : void wpl (Bnode *t, int k) // 全局变量 w=0; k 的初值为 0 31

32 {if (t!=null) { if ((t->lchild==null)&&(t->rchild==null)) {w+=t->data*k; wpl(t->lchild,k+1); wpl(t->rchild,k+1); int wpl (Bnode *t, int k) {if (t!=null) { if ((t->lchild==null)&&(t->rchild==null)) return(t->data*k); else return (wpl(t->lchild,k+1)+wpl(t->rchild+1)); 应用实例 下面通过一个实例来说明哈夫曼树的应用 例 : 已知一个文件中仅有 8 个不同的字符, 各字符出现的个数分别是 试重新为各字符编码, 以节省存储空间 解 : 本题可借助于哈夫曼树来实现求解 首先, 将所给出的各字符的个数作为权值来构造一棵哈夫曼树, 然后对此编码可以得到哈夫曼编码, 这些编码就可以作为各字符的新编码 (1) 构造哈夫曼树 : 以所给出的数据集 {3,4,8,10,16,18,20,21 所构造的哈夫曼树如图 6-38 所示 (2) 编码 : 设根结点的编码为空, 然后从根结点开始依次对各结点按如下方法编码 : 每个结点的左孩子的编码通过在其父结点的编码后添加二进制 0 而得到, 而每个结点的右孩子的编码通过在其父结点的编码后添加二进制 1 而得到 例如, 值为 10 的结点的编码为

33 图 6-38 哈夫曼树 (3) 各字符的编码及其长度 : 将各叶子结点所对应的编码作为对应字符的新编码即可节省存储空间 即出现个数为 3 的字符的编码为 00000, 出现个数为 4 的字符的编码为 等 依照这一方法来编码, 可得到重新编码的文件的长度为各字符的个数乘以其长度之积的和, 也即为哈夫曼树的带权路径长度的值 : (3+4) ( ) 3+(20+21) 2=281 也就是说, 在对文件中的字符按新的编码存储时,100 个字符所占用的位数共有 281 位 如果采用等长方式, 则每个字符需要 3 位, 因此共需要 300 位 由此可知, 这一不等长编码能节省存储空间 33