第7章 树和二叉树

第7章树和二叉树 本章要点 树的定义及相关术语 二叉树的定义 存储结构和基本运算的实现 二叉树的遍历 二叉树与树和森林的相互转换 哈夫曼树及应用 本章难点 二叉树的定义 存储结构和基本运算的实现 哈夫曼树及应用 1 领会树和二叉树的类型定义 理解树和二叉树的结构差别 2 熟记二叉树的主要特性 并了解它们的证明方法 3 熟练掌握二叉树的各种遍历算法 并能灵活运用遍历算法实现二叉树的其它操作 4 理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法 5 熟练掌握二叉树和树的各种存储结构及其建立的算法 6 学会编写实现树的各种操作的算法 7 了解最优树的特性 掌握建立最优树和赫夫曼编码的方法 学习目标 7 1树的定义和基本操作 7 1 1树的定义前面章节讨论的数据结构主要是线性结构 树型结构是一类重要的非线性结构 非线性结构结构中存在一个数据元素有两个或两个以上的直接前驱 或直接后继 元素 树型结构广泛用于描述家族谱系以及其它社会组织结构 在计算机领域中 如操作系统的文件目录结构 编译程序中的语法结构和数据库中的信息组织也都需要借用树来描述 本章将讨论树和二叉树两种树型结构 树的定义树是n n 0 个具有相同特性的数据元素的结点的有限集合 当n 0时 称为空树 用 表示 有且仅有一个称为根 root 结点的数据元素 根结点没有前驱结点 当n 1时 其余结点可分为m m 0 个互不相交的 非空 有限集T1 T2 Tm 其中每一个子集本身又是一棵符合本定义的树 称为根root的子树 树的定义是一个递归定义 它反映了树的固有特性 一棵数是由根和它的子树构成 而子树又由子树的根和更小的子树构成 7 1 1树的定义 7 1 1树的定义 a 空树 b 只有根结点的树 d 非树结构 c 一般的树 a 空树 b 只有根结点的树 c 有11个结点的树 是根结点 其余结点分成三个不相交的子集 T1 B T2 C E F G H I J K T21 E I J T22 F T23 G K T24 H T3 D d 非树结构 7 1 1树的定义 c 一般的树 树的特性 树的根结点没有前驱结点 除根结点之外的所有结点有且只有一个前驱结点 树中所有结点可以有零个或多个后继结点 7 1 1树的定义 7 1 1树的常用术语 结点的度结点拥有的子树的个数 叶子结点 终端结点 度为0的结点 分支结点 非终端结点 度不为0的结点 树的度树内各结点的度的最大值 双亲结点结点的直接前驱结点 c 一般的树 孩子结点一个结点的直接后继结点 兄弟结点同一双亲结点的孩子结点之间互称兄弟结点 祖先结点从根结点到该结点所经分支上的所有结点 子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙结点 结点的层次根为第一层 根的直接后继为第二层 依次类推 7 1 1树的常用术语 c 一般的树 树的深度 高度 结点的层次从根结点开始 根为第一层 根的孩子为第二层 树中结点的最大层次称为树的深度或高度 有序树 无序树如果一棵树中的结点的各子树从左到右是有次序的 即若交换了某结点各子树的相对位置 则构成不同的树 称这棵树为有序树 反之 则称为无序树 森林m棵互不相交的树的集合 一棵树可以看成是由根结点和根结点下的森林构成的 7 1 1树的常用术语 c 一般的树 直观表示法 嵌套集合表示法 7 1 3树的表示方法 直观表示法 嵌套集合表示法 括号形式表示法 A B C E I J F G K H D 凹入表示法 A B C E I J F G K H D 7 1 3树的表示方法 就结构中数据元素之间存在的关系可将树和线性结构作如下对照 将树和线性结构数据元素之间存在的关系作如下对照 可见 由于线性结构是一个 序列 元素之间存在的是 一对一 的关系 而树是一个层次结构 元素之间存在的是 一对多 的关系 7 1 3树的表示方法 二叉树是另一种基本的树型结构 用二叉树来研究树的问题是表示和处理树型结构的基本方法 7 2 1二叉树的定义二叉树是有限个元素的集合 该集合或者为空 或者由一个称为根的元素及两个互不相交的 被分别称为左子树和右子树的二叉树组成 当集合为空时 称该二叉树为空二叉树 约定 二叉树的每个结点至多只有二棵子树 即二叉树中不存在度大于2的结点 二叉树是有序的 如果将左右子树颠倒 就成为另一棵二叉树 7 2二叉树 7 2 1二叉树的定义 二叉树具有以下5种基本形态 空二叉树 仅有根的二叉树 仅有左子树的二叉树 仅有右子树的二叉树 左 右子树均非空的二叉树 二叉树并非是树的特殊情形 在二叉树中 即使是一个孩子 也有左右之分 具有2个结点的二叉树有2种形态 具有3个结点的二叉树有5种形态 2种特殊的二叉树 满二叉树如果二叉树中所有的分支结点的度数都为2 且叶子结点都在同一层次上 则称这类二叉树为满二叉树 对满二叉树从上到下从左到右进行从1开始的编号 如图所示 则深度为k的满二叉树有且必有2k 1个结点 这种二叉树的特点是每一层上的结点数都是最大的结点数 7 2 1二叉树的定义 满二叉树 非满二叉树 7 2 1二叉树的定义 7 2 1二叉树的定义 完全二叉树如果一棵包含n个结点的二叉树中每个结点都可以和满二叉树中编号为1至n的结点一一对应 则称这类二叉树为完全二叉树 完全二叉树 非完全二叉树 7 2 2二叉树的性质 性质1 一棵非空二叉树的第i层上至多有2i 1个结点 i 1 性质2 深度为k的二叉树中至多含有2k 1个结点 k 1 性质3 对任何一棵二叉树T 如果叶子结点数为n0 度为2的结点数为n2 则n0 n2 1性质4 具有n个结点的完全二叉树的深度为log2n 1 性质5 如果具有n个结点的完全二叉树 其深度为log2n 1 的结点按自上而下和从左到右的顺序对每个结点从1起开始顺序编号 则对任一编号为j的结点 1 j n 有 若j 1 则结点j是二叉树的根 无双亲 否则其双亲结点parent j 是j 2 若2j n 则结点j的左孩子结点是2j 否则无左孩子 即编号为j且满足2j n的结点为叶子结点 若2j 1 n 则结点为j的右孩子结点是2j 1 否则无右孩子 若结点j序号为奇数且不等于1 则它的左兄弟为j 1 若结点j序号为偶数且不等于n 它的右兄弟为j 1 7 2 2二叉树的性质 7 2 2二叉树的性质 例已知一棵完全二叉树共有892个结点 求 树的高度 叶子结点数 单支结点数 最后一个非终端结点的序号答 已知深度为k的二叉树最多有2k 1个结点 K 1 29 1 892 210 1 故树的高度为10 对于完全二叉树来说 度为1的结点只能是0或1因为n n0 n1 n2和n0 n2 1得 设n1 0 892 n0 0 n2 2n2 1得n2不为整数出错设n1 1 892 n0 1 n2 2n2 2得n2 445 n0 n2 1 446叶子结点数为446 7 2 2二叉树的性质 答 由 得单支结点数为1 对于n个结点的完全二叉树 最后一个树叶结点 即序号为n的叶结点其双亲结点即为最后一个非终端结点 序号为892 2 446 7 2 3二叉树的存储结构 顺序存储结构用一组地址连续的存储单元存储二叉树中的数据元素 二叉树的顺序存储结构的定义如下 defineMAX50 暂定二叉树中结点数的最大值为100 typedefstruct Elemtypea MAX intcount 二叉树中结点数 BTree 二叉树的顺序存储结构 typedefBTreebt 按照数据结构的 顺序存储映象 的定义 在顺序存储结构中没有附加信息 因此对二叉树的顺序存储结构 也只是以一组地址连续的存储空间存放二叉树中的数据元素 只是不能以 存储位置相邻 来表示 后继 关系 在二叉树的这种表示方式下 各结点之间的逻辑关系是隐含表示的 完全二叉树中 除最下面一层外 各层都充满结点 除最底层外 每一层的结点个数恰好是上一层结点数的2倍 故从一个结点的编号可推出其双亲 左右孩子和兄弟等结点的编号 完全二叉树中结点的层次关系可反映结点之间的逻辑关系 7 2 3二叉树的存储结构 为了能在存储结构中反映出结点之间的逻辑关系 必须将二叉树中结点依照一定规律安排在这组存储单元中 对于完全二叉树 只要从根起按层序存储即可 根据上一节所述完全二叉树的特性 将完全二叉树上编号为i的结点元素存储在一维数组中下标为i 1的分量中 如前例含12个结点的完全二叉树的顺序存储结构如下所示 7 2 3二叉树的存储结构 根据上节所述二叉树的性质5 可推出顺序存储结构中 双亲 和 孩子 的关系 假设bt a i 是完全二叉树上的一个结点 若2i 1 bt count 则bt a 2i 1 是它的左孩子 否则它的左子树为空树 若2i 2 bt count 则bt a 2i 2 是它的右孩子 否则它的右子树为空树 在二叉树表示方法下 各结点间的逻辑关系是隐含的 完全二叉树中 除最底层外 各层都充满结点 除最底层外 每一层结点数恰好是上一层结点数的2倍 故从一个结点的编号就可推得其双亲 左右孩子和兄弟结点的编号 数组下标 7 2 3二叉树的存储结构 7 2 3二叉树的存储结构 对于结点i 仅当i 1时 结点i为根结点 当i 1时 结点i的双亲结点为 结点i的左孩子结点2i 结点i的右孩子结点2i 1 当i为奇数且不为1时 结点i的左兄弟为i 1 当i为偶数且小于n时 结点i的右兄弟为i 1 完全二叉树中结点的层次关系反映了结点间的逻辑关系 对于完全二叉树 顺序存储既方便又节省存储空间 7 2 3二叉树的存储结构 对于一般的二叉树 采用顺序存储时 为了用结点在数组中的位置表示结点之间的逻辑关系 也必须按完全二叉树的形式来存储树中的结点 在最坏情况 一个只有k个结点的右单支树却需要2k 1个结点的存储空间 右单支二叉树 对应的完全二叉树 10 13 7 2 3二叉树的存储结构 例前例中的完全二叉树 已知某一结点编号x 求该结点的左孩子 typedefcharElemtypeElemtypeLChild BTreeBT intx if x 1 用 表示孩子为空 7 2 3二叉树的存储结构 例前例中的完全二叉树 已知某一结点编号x 求该结点的双亲结点 typedefcharElemtypeElemtypeparent BTreeBT intx if xBT count printf nodenotexist return 用 表示孩子为空 elsereturn BT a x 2 7 2 3二叉树的存储结构 顺序存储对于完全二叉树来说非常方便 对于一般的二叉树 可对照完全二叉树的编号进行相应的存储 但在没有结点的分量中需填充空白字符 显然 这种存储表示方法只适合于完全二叉树 对于一般的二叉树将造成存储空间的很大浪费 因此二叉树的常用存储结构是链表 7 2 3二叉树的存储结构 1 2 3 4 5 6 1 7 8 9 10 11 12 数组下标 对应的完全二叉树 一般二叉树 序号 1 12 链式存储结构二叉树的链式存储结构指的是用链表来存储二叉树 即用结点结构中的指针域来表达数据元素之间的关系 二叉树的二叉链表存储结点结构typedefstructnode Elemtypedata structnode LChild RChild 左 右孩子指针 BinNode BinTree 二叉树的结点由一个数据元素和指向左 右孩子的指针域 7 2 3二叉树的存储结构 在二叉链表中虽然没有指向双亲结点的指针 但可以通过指向孩子结点的指针找到 双亲 因此二叉链表中的信息是完备的 这和只有指向后继指针的单链表中隐含着 前驱 的信息是类似的 整个二叉树可以一个指向根结点的指针表示 如下列左图所示二叉树的二叉链表如下列右图所示 头指针bt 7 2 3二叉树的存储结构 基于二叉链表存储结构 建立二叉树算法分析用一个一维数组来模拟队列 存放输入的结点 输入时 按完全二叉树形式 若是非完全二叉树 必须给定一些假想结点 使之符合完全二叉树形式 存在的结点输入对应字符 不存在的结点输入逗号 以 为输入结束符 建成的二叉链表由根指针root惟一确定 7 2 3二叉树的存储结构 includetypedefcharElemtypetypedefstructnode Elemtypedata structnode LChild RChild 左 右孩子指针 BinNode BinTree BinTreeCreate BinTreeq 100 s root NULL intfront 1 rear 0 charch ch getchar while ch s NULL if ch s BinTree malloc sizeof BinNode s data ch s LChild NULL s RChild NULL 7 2 3二叉树的存储结构 rear q rear s if rear 1 root s else if s NULL 7 2 3二叉树的存储结构 增加虚结点假想为完全二叉树 非完全二叉树 从键盘输入数据为 AB C D 7 2 3二叉树的存储结构 头指针root 建立的二叉链表 7 2 3二叉树的存储结构 在以前各章的类型定义中都有 遍历 的基本操作 但从来没有专门提出来讨论过 而从另一方面看 很多操作是在遍历过程中进行的 如 在线性表中查询某个特定的数据元素 求链表的长度等等 这是因为线性结构是一个 序列 每个数据元素只有一个后继 因此它的遍历只有一条搜索路径 即从第一个数据元素起 顺着 后继 直到最后一个数据元素止 而非线性结构中每个数据元素可以有多个后继 为保证 遍历 成功就需要确定合适的搜索路径 7 2 4二叉树的遍历 从数据类型的定义得知 遍历 的含义是对结构中的每个数据元素都访问一次且仅仅访问一次 因此进行遍历应该确定一条搜索路径 使得结构中的每个数据元素都出现在这条搜索路径上 才能确保每个数据元素都被访问到 由于二叉树中每个结点都有两个后继 则可以有三条搜索路径 先左 子树 后右 子树 先右 子树 后左 子树 按层次从上到下 按层次从上到下的遍历比较简单 先访问第一层的结点 即根结点 再访问第二层 第三层 直到最后一层 对每一层的结点则从左到右 即 先被访问的父结点的孩子结点 先于 后被访问的父结点的孩子结点 进行访问 7 2 4二叉树的遍历 从二叉树的结构定义得知 二叉树是由 根结点 左子树 和 右子树 三部分构成 则遍历二叉树的操作可分解为 访问根结点 遍历左子树 和 遍历右子树 三个子操作 并且由二叉树的递归定义可知 遍历左子树和遍历右子树可如同遍历二叉树一样 递归 进行 因此整个遍历的操作只要在一条搜索路径上一次完成这三个子操作即可 第一次走到根结点即 访问 为 先序遍历 从左子树回来再 访问 为 中序遍历 从右子树回来再 访问 为 后序遍历 7 2 4二叉树的遍历 如图所示为对二叉树进行遍历的先左后右的搜索路径 从图可得知两个结论 由于左右子树互不相交 因此对左子树的遍历一定不会访问到右子树上的结点 反之对右子树的遍历也一定不会访问到左子树 因此沿这条搜索路径必可实现对二叉树中每个结点都访问到且只访问一次 也正由于左右子树不相交 因此在遍历了左子树之后必须回到根结点才能继续遍历右子树 由此可见 在这条搜索路径上从进入二叉树到离开二叉树 一共三次遇到根结点 因此访问根结点的操作可在任意一次也只能在其中一次进行 由此得到以下三个遍历二叉树的算法 7 2 4二叉树的遍历 按照遍历过程中先后访问的次序将二叉树中的结点排列起来分别得到二叉树的先序遍历 中序遍历和后序遍历 7 2 4二叉树的遍历 先序遍历 DLR voidPreOrder BinTreer 先序遍历以r为根指针的二叉树if r NULL Visit r data 访问根结点 PreOrder r LChild 先序遍历r的左子树 PreOrder r RChild 先序遍历r的右子树 按先序遍历得到结点序列 ABDCEF 7 2 4二叉树的遍历 中序遍历 LDR voidInOrder BinTreer 中序遍历以r为根指针的二叉树if r NULL InOrder r LChild 先序遍历r的左子树 Visit r data 访问根结点 InOrder r RChild 先序遍历r的右子树 按中序遍历得到结点序列 BDAEFC 7 2 4二叉树的遍历 后序遍历 LRD voidPostOrder BinTreer 后序遍历以r为根指针的二叉树if r NULL PostOrder r LCchild 先序遍历r的左子树 PostOrder r RChild 先序遍历r的右子树 Visit r data 访问根结点 按后序遍历得到结点序列 DBFECA 7 2 4二叉树的遍历 层次遍历指从二叉树的第一层 根结点 开始 从上到下逐层遍历 而在同一层中 则按从左到右的顺序对结点逐个访问 按层次遍历得到结点序列 ABCDEF算法设计设置一个队列结构 遍历从根结点开始 首先将根结点指针入队列 然后从队头取出一个元素 每取一个元素 执行下面操作 访问该元素所指结点 若该结点左 右孩子非空 则将左 右孩子指针顺序入队 当队列为空时 二叉树的层次遍历结束 7 2 4二叉树的遍历 voidlevelorder BinTreebt BinTreequeue MAXSIZE intfront rear if bt NULL front 1 rear 0 queue rear bt while front rear front Visit queue front data if queue front LChild NULL rear queue rear queue front LChild if queue front RChild NULL rear queue rear queue front RChild 7 2 4二叉树的遍历 表达式二叉树 可以把任意算术表达式由一棵二叉树表示 例 a b c d e f g表示如右图 称为表达式二叉树每个非叶子结点都是运算符 每个叶子结点都是操作数 前序 a bc de fg中序 a b c d e f g后序 abc de fg 7 2 5二叉树遍历的应用 7 2 5二叉树遍历的应用 中缀表达式是经常使用的表达式 前缀表达式和后缀表达式又分别称为波兰式和逆波兰式 其中后缀表达式就是在栈一章中提到的后缀运算式 后缀表达式在表达式计算中有非常重要的作用 对任意一棵二叉树 其三种遍历序列是惟一确定的 但已知二叉树的遍历序列 能否确定二叉树 若已知三种遍历序列的其中一种 具有这种遍历序列的二叉树是多种多样的 不能唯一确定一棵二叉树 若已知先序和中序遍历序列 二叉树可以惟一确定 若已知后序和中序遍历序列 二叉树可以惟一确定 如果只知道二叉树的先序和后序遍历序列 由于只能确定根结点 不能用根结点将其中的一个序列划分为左右子树 所以不能惟一地确定一棵二叉树 总之 由二叉树的遍历序列恢复二叉树时 必须至少已知两种编历序列 而且必须有中序序列 7 2 5二叉树遍历的应用 7 2 5二叉树遍历的应用 例写出如图所示的二叉树的先序 中序和后序遍历序列 先序 fdbacegihj 中序 abcdefghij 后序 acbedhjigf 二叉树 7 2 5二叉树遍历的应用 例若一棵树 左右子树均有三个结点 其左子树的先序序列与中序序列相同 右子树的中序序列与后序序列相同 试构造该树 解依题意 左子树的先序与中序序列相同 即有先序 根左右中序 左根右即以左子树为根的树无左孩子 右子树的中序与后序序列相同 即有中序 左根右后序 左右根也即 以右子树为根的树无右孩子 由此构造该树如图所示 二叉树 7 2 5二叉树遍历的应用 例已知一棵二叉树的先蓄序列和中序序列分别为 先序ABCDEFGHI中序CBAEDGHFI试恢复该二叉树 解 由先序序列 A是二叉树的根结点 A将中序序列分为左子树 B C 和右子树 E D G H F I 如图所示 在左子树中 由先序可知 结点B是根结点 由中序可知 C是左子树根结点 左子树完成 在右子树中 由先序可知 D是右子树的根结点 在右子树中序序列中 D将右子树分为左子树 E 和右子树 G H F I 如图所示 继续此方法划分右子树 G H F I 最终得到二叉树如图所示 7 2 5二叉树遍历的应用 一棵二叉树的恢复过程 算法思想先根据先序序列的第一个元素建立根结点 然后在盅许序列中找到该元素 确定根结点的左 右子树结点序列 再从这些结点序列中根据先序序列找到子树的根结点 将子树再划分为左 右子树 直到叶子结点为止 7 3线索二叉树 7 3 1线索二叉树的定义及结构 线索二叉树的定义对二叉树进行遍历的过程即为沿着某一条搜索路径对二叉树中的结点进行一次且仅仅一次访问 换句话说 就是按一定规则将一个处于层次结构中的结点排列成一个线性序列之后进行依次访问 这个线性序列或是先序序列 或是中序序列或是后序序列 在这些线性序列中每个结点 除第一个和最后一个外 有且仅有一个直接前驱和直接后继 前序 ABDEGCFH中序 DBEGAFHC后序 DGEBHFCA 7 3 1线索二叉树的定义及结构 这种信息是在遍历的动态过程中产生的 如果将这些信息在第一次遍历时就保存起来 则在以后再次需要对二叉树进行 遍历 时就可以将二叉树视作线性结构进行访问操作了 如何保存在遍历过程中得到的前驱和后继信息 最简单的办法是在结点中增加两个指针域分别指向该结点的前驱和后继 但这样做将使存储结构的存储密度大大降低 另一方面 一个含n个结点的二叉链表中 共有2n个指针域 其中只有n 1个用来存储孩子结点的地址 有n 1个链域的值为 NULL 可以利用这些空的指针域存放指向前驱和后继的信息 这些指向直接前驱结点和指向后继结点的指针称为线索 加了线索的二叉树称为线索二叉树 7 3 1线索二叉树的定义及结构 一个含n个结点的二叉链表中 共有2n个指针域 其中只有n 1个用来存储孩子结点的地址 另外n 1个指针域 若指针有左孩子 存放左孩子地址 否则可以存放该结点在某种遍历序列中的直接前驱结点的存储地址 同样 若若指针有右孩子 存放右孩子地址 否则可以存放该结点在某种遍历序列中的直接后继结点的存储地址 区别某结点的指针域内存放的是孩子地址还是前驱或后继地址 可以在结点中增加两个标志域 结点结构如下 二叉线索链表结点结构 7 3 1线索二叉树的定义及结构 Ltag和Rtag称为线索标志域 Ltag 0LChild域指向结点的左孩子1LChild域指向结点的前驱结点Rtag 0RChild域指向结点的右孩子1RChild域指向结点的后继结点由于序列可由不同的遍历方法得到 故线索树有先序线索二叉树 中序线索二叉树和后序线索二叉树三种 把二叉树改造成线索二叉树的过程称为先序线索化 前例二叉树对应的中序线索二叉树如下图所示 7 3 1线索二叉树的定义及结构 中序线索二叉树 A 0 线索二叉树的存储结构在线索二叉树中 结点结构定义如下 typedefcharElemtype typedefstructthread Elemtypedata structthread LChild RChild 左右指针 shortintLtag Rtag 左右指针类型标志 ThreadNode ThreadTree 如果某结点的左指针域为空 则使该指针域 LChild 存储该结点在某种遍历序列中的直接前驱结点的地址 如果某结点的右指针域为空 则使该指针域 RChild 存储该结点在某种遍历序列中的直接后继结点的地址 7 3 1线索二叉树的定义及结构 bt head 1 0 0 A 0 0 B 0 1 D 1 0 E 1 1 G 1 1 C 0 0 F 1 1 H 1 7 3 2线索二叉树的基本运算 建立一棵中序线索二叉树建立一棵中序线索二叉树 即对二叉树线索化 实质上就是遍历一棵二叉树 在遍历中访问结点的操作是检查当前结点的左 右指针是否为空 若为空 则将它们改为指向前驱结点或后继结点的线索 申请一个头结点 建立头结点与二叉树根结点的指向关系 对二叉树线索化后 还建立最后一个结点与头结点之间的线索 中序 DBEGAFHC voidInThread ThreadTreeroot 中序遍历 进行中序线索化 if root NULL InThread root LChild 左子树线索化 if root LChild NULL 前驱线索 root Ltag 1 root LChild pre if pre NULL 7 3 2线索二叉树的基本运算 ThreadTreepre 全局变量 intInorderthr ThreadTree head ThreadTreet 中序遍历二叉树t 并将其中序线索化 head指向头结点 head ThreadTree malloc sizeof ThreadNode if head return 0 head Ltag 0 head Rtag 1 head RChild head 建立头结点 if t NULL head LChild head 二叉树为空 左指针回指 else head LChild t pre head InThread t pre RChild head pre Rtag 1 head RChild pre return 1 7 3 2线索二叉树的基本运算 在中序线索二叉树上查找任意结点的中序前驱结点对于中序线索二叉树上任一结点 查找中序的前驱结点 有以下两种情况 如果该结点的Ltag 1 其左指针域所指向的结点便是它的前驱结点 如果该结点的Ltag 0 表明该结点有左孩子 根据中序遍历的定义 它的前驱结点是以该结点的左孩子为根结点的子树的最右结点 即沿着其左子树的右指针链向下查找 当某结点的右标志为1时 它就是所要找的前驱结点 7 3 2线索二叉树的基本运算 在中序线索二叉树上查找结点p的中序前驱结点算法ThreadNode Inprenode ThreadNode p ThreadTree pre q pre p LChild if p Ltag 1 pre pre LChild else for q p LChild q Rtag 0 q q RChild 在p的左子树中查找最右下端结点 pre q return pre 7 3 2线索二叉树的基本运算 在中序线索二叉树上查找任意结点的中序后继结点对于中序线索二叉树上任一结点 查找中序的后继结点 有以下两种情况 如果该结点的rtag 1 其右指针域所指向的结点便是它的后继结点 如果该结点的rtag 0 表明该结点有右孩子 根据中序遍历的定义 它的后继结点是以该结点的右孩子为根结点的子树的最左结点 即沿着其右子树的左指针链向下查找 当某结点的左标志为1时 它就是所要找的后继结点 7 3 2线索二叉树的基本运算 在中序线索二叉树上查找结点p的中序后继结点算法ThreadNode InPostNode ThreadNode p ThreadNode succ q succ p RChild if p Rtag 1 succ p RChild else for q p RChild q Ltag 0 q q LChild 在p的右子树中查找最左下端结点 succ q return succ 7 3 2线索二叉树的基本运算 在中序线索二叉树上查找值为x的结点利用在中序线索二叉树上查找后继结点和前驱结点的算法 就可以遍历到二叉树的所有结点 例如先找到按某种遍历序列的第一个结点 然后再依次查询其后继 或先找到按某种遍历序列的最后一个结点 然后再依次查询其前驱 这样 既不用栈也不用递归就可以访问到二叉树的所有结点 在中序线索二叉树上查找值为x的结点 实质上就是在线索二叉树上进行遍历 将访问结点的操作具体写为结点的值与x比较 7 3 2线索二叉树的基本运算 在中序线索二叉树上查找值为x的结点算法ThreadNode Search ThreadTreep Elemtypex p head LChild while p Ltag 0 7 3 2线索二叉树的基本运算 7 3 2线索二叉树的基本运算 在中序线索二叉树上的更新线索二叉树的更新是指 在线索二叉树中插入或删除一个结点 一般地 这些操作可能破坏原来已有的线索 因此 在修改指针时 还需要对线索做相应的修改 一般地 这个过程的代价基本和重新进行线索化相同 现以中序线索二叉树为例 说明线索二叉树的插入和删除 7 3 2线索二叉树的基本运算 插入结点在中序线索二叉树中插入结点p 使其成为结点s的右孩子 算法分析 若s的右子树为空 s的后继将成为p的中序后继 s成为p的中序前驱 而p成为s的右孩子 二叉树中其他部分的指针和线索不发生变化 若s的右子树非空 插入结点p之后 s原来的右子树变成p的右子树 由于p没有左子树 故s成为p的中序前驱 p成为s的右孩子 又由于s原来的后继成为p的后继 因此还要将s原来的本来指向s的后继的左线索 改为指向p 7 3 2线索二叉树的基本运算 p s S的右子树为空 插入结点p s 7 3 2线索二叉树的基本运算 S的右子树非空 插入结点p s s p 7 3 2线索二叉树的基本运算 2 删除结点与插入操作一样 在中序线索二叉树中删除一个结点 也会破坏原来的线索 故需要在删除的过程中体现二叉树的线索化 在中序线索二叉树中删除结点p s p s 删除结点p后 删除结点p前 7 4树 森林和二叉树的关系 7 4 1树的存储结构孩子兄弟表示法 又称为二叉链表表示法 其方法是 在树的每个结点中 除了存储结点信息外 再增加两个指针 左指针FirstChild指向该结点的 第一个 子树根结点 右指针RightSibling指向它的 下一个 兄弟结点 这里的 第一个 和 下一个 都没有逻辑上的含义 只是在构造存储结构时自然形成的次序 可描述为typedefstructnode Elemtypedata structnode FirstChild RightSibling node pnode pnoderoot 7 4树 森林和二叉树的关系 root FirstChild RightSibling 树的孩子兄弟表示法 7 4 1树的存储结构 从结点结构看出 当树用二叉链表表示时 树的结构已经转换成一棵二叉树 即给定一棵树 可以找到惟一的一棵二叉树与之对应 结论当一棵树用二叉链表表示时 可以用惟一对应的一棵二叉树表示 研究树的问题转化成了研究二叉树的问题 同时也为二叉树与树和森林的相互转换提供了依据 7 4 2树 森林与二叉树的转换 二叉树与树 森林能够相互转换 是因为它们都可以用孩子兄弟表示法或称二叉链表表示法作为存储结构 从物理结构看 其二叉链表是相同的 只是解释不同而已 树转换为二叉树对于一棵无序树 树中结点的各孩子的次序无关 但二叉树中的结点的左 右孩子结点是有序的 故约定树中每个结点的孩子结点从左到右有序 将一棵树转换为二叉树的方法 树中所有相邻兄弟加一条连线 对树中的每个结点 只保留与第一个孩子结点间的连线 删去与其他孩子结点间的连线 以树的根结点为轴心 将整棵树顺时针旋转 使之结构层次分明 7 4 2树 森林与二叉树的转换 树转换为二叉树过程示意 7 4 2树 森林与二叉树的转换 森林转换为二叉树森林是若干棵树的集合 只要将森林中各棵树的根看作兄弟 森林就可以用孩子兄弟链表表示 即森林可以用二叉树表示 森林转换为二叉树方法 将森林中的每棵树转换成相应的二叉树 第一棵树不动 从第二棵二叉树开始 依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子 当所有二叉树连接起来后 此时所得到的二叉树就是由森林转换得到的二叉树 7 4 2树 森林与二叉树的转换 7 4 2树 森林与二叉树的转换 二叉树转换为森林树和森林都可以转换为二叉树 不同的是 树转换成二叉树 其根结点无右子树 而森林转换后 其根结点有右分支 这一转换过程是可逆的 即如果根结点无右子树 则只能转换为树 否则必转换为森林 7 4 2树 森林与二叉树的转换 7 4 3树和森林的遍历 和二叉树的遍历类似 树的遍历问题亦为 从根结点出发 对树中各个结点进行一次且仅进行一次访问 对树进行遍历可有两条搜索路径 一条是从左到右 这里的左右指的是在存储结构中自然形成的子树之间的次序 另一条是按层次从上到下 树的按层次遍历类似于二叉树的按层次遍历 例如对右图存储结构的树进行按层次遍历所得结点先后被访问的次序的为 ABCDE 对树进行从左到右遍历的搜索路径类似于二叉树 在这条搜索路径上途经根结点两次 由对根的访问时机不同可得下列两个算法 先根遍历若树不空 则先访问根结点 然后依次从左到右先根遍历根的各棵子树 先根遍历序列 ABEHIJCDFJK 后根遍历若树不空 则先依次从左到右后根遍历根的各棵子树 然后访问根结点 后根遍历序列 HIJEBCFKJDA 7 4 3树和森林的遍历 森林是树的集合 由此可以对森林中的每一棵树依次从左到右 如下图所示 进行先根遍历或者后根遍历 又森林中的 第一棵树的根 第一棵树的子树森林 及 其余树构成的森林 分别对应为 二叉树的根 二叉树的左子树 和 二叉树的右子树 由此可如下定义森林的这两种遍历 7 4 3树和森林的遍历 先序遍历森林若森林不空 则可依下列次序进行遍历 1 访问森林中第一棵树的根结点 2 先序遍历第一棵树中的子树森林 3 先序遍历除去第一棵树之后剩余的树构成的森林 森林的先序序列 ABCDEFGHIJ 7 4 3树和森林的遍历 中序遍历森林若森林不空 则可依下列次序进行遍历 1 中序遍历第一棵树中的子树森林 2 访问森林中第一棵树的根结点 3 中序遍历除去第一棵树之后剩余的树构成的森林 森林的中序序列 BCDAFEHJIG 7 4 3树和森林的遍历 7 4 4树的应用 树的应用十分广泛 在排序和查找两项常用技术中 就有以树结构组织数据进行操作的 判定树树可用于判定问题的描述和解决 著名的八枚硬币问题 设有八枚硬币 分别表示为a b c d e f g h 其中有且仅有一枚硬币是假币 可能轻 也可能重 问题的解决过程如图所示 解决过程的一系列判断构成了树结构 称这样的树为判定树 a H a H e L c H f L b H d L g H h L h H g L b L d H f H a L e H c L 判定树 7 4 4树的应用 7 5哈夫曼树及其应用 哈夫曼树 又称为最优二叉树 是一类带权路径长度最短的树 在编码领域有广泛应用 7 5 1哈夫曼树的定义 基本概念最优树 又称哈夫曼树 HuffmanTree 是一类带权路径长度最短的树 本节仅限于讨论最优二叉树 首先介绍路径和路径长度的概念 路径长度从树的根结点到其余结点的分支构成一条路径 路径上的分支数目称路径长度 树的路径长度一般情况下 树的路径长度指从根到树中其余每个结点的路径长度之和 前面讲述的完全二叉树就是这种路径长度最短的二叉树 权值给二叉树上的每个叶子结点赋予某一个特定的值 这个特定的值称为该叶子结点的权 结点的带权路径长度从树根到该结点之间的路径长度与该结点上所带权值的乘积 树的带权路径长度假设树上有n个叶子结点 且每个叶子结点上带有权值为Wi i 1 2 n 则树的带权路径长度定义为树中所有叶子结点的带权路径长度之和 通常记作WPL 7 5 1哈夫曼树的定义 7 5 1哈夫曼树的定义 哈夫曼树 最优二叉树 假设有n个权值 w1 w2 wn 现构造具有n个叶子结点的二叉树 每个叶子结点的权值为wi 则这样的二叉树会有多种形式 其中带权路径长度WPL最小的二叉树称为最优二叉树 哈夫曼树 a b c a WPL 7 2 5 2 2 2 4 2 36 b WPL 7 3 5 3 4 2 2 1 46 c WPL 7 1 5 2 2 3 4 3 35其中以图 c 二叉树的带权路径长度为最小 可以验证 它恰为最优二叉树 即在所有叶子结点带权为7 5 2 4的二叉树中 带权路径长度的最小值为35 注意最优树并不特指二叉树 但 带权路径长度最短 是在 度相同 的树中比较而得的结果 因此有最优二叉树 最优三叉树之称等等 7 5 1哈夫曼树的定义 在解决某些判定问题时 利用哈夫曼树可以得到最佳的判定算法 例 将百分制转换成五分制的程序 if a 60 b bad elseif a 70 b pass elseif a 80 b good elseb excellent 学生成绩是 正态分布 7 5 1哈夫曼树的定义 不及格 及格 中等 Y Y N N 判定树 a 7 5 1哈夫曼树的定义 及格 中等 良好 优秀 不及格 Y Y Y N Y N N N 判定树 b 7 5 1哈夫曼树的定义 假定以5 15 40 30 10为权构造一棵有5个叶结点的哈夫曼树 则可以得到判定树 b 如图所示 现假设有10000个输入数据 按 a 判定过程进行操作 需进行31500次比较 按 b 判定过程进行操作 需进行22000次比较 结论对于同一问题 采用不同的判定树来解决 效率是不一样的 7 5 1哈夫曼树的定义 哈夫曼树的构造方法一棵二叉树要使得其WPL值最小 必须使权值越大的叶子结点越靠近根结点 而权值越小的叶子结点越远离根结点 哈夫曼根据这一特点 最早给出构造最优树的带有一般规律的算法 俗称哈夫曼算法 现以最优二叉树为例叙述如下 1 由给定的n个权值 w1 w2 wn 构成n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树Ti中只有一个带权为wi的根结点 其左右子树均空 2 在F中选取两棵根结点的权值最小的树作为左右子树 构造一棵新的二叉树 且置新的二叉树的根结点的权值为其左 右子树上根结点的权值之和 3 在F中删除这两棵树 同时将新得到的二叉树加入F中 重复 2 和 3 直到F只含一棵树为止 这棵树便是所求的哈夫曼树 7 5 2哈夫曼树的构造 例对5个权值 5 6 2 9 7 构造最优二叉树的过程如下图所示 注意 对于同一组给定的叶子结点所构造的哈夫曼树 树的形状可能不同 但它们的带权路径长度WPL的值是相同的 且一定是最小的 7 5 2哈夫曼树的构造 哈夫曼树的建立过程 哈夫曼树的建立过程 第五步 7 5 3哈夫曼编码 哈夫曼二叉树在通讯编码中的一个应用是利用它构造一组最优前缀编码 在某些通讯场合 需将传送的文字转换成由二进制字符组成的字符串 通常有两类二进制编码 一类为等长编码 这类编码的二进制串的长度取决于电文中不同的字符个数 假设需传送的电文中只有四种字符 只需两位字符的串便可分辨 但如果电文中可能出现26种不同字符 则等长编码串的长度为5 另一类是不等长编码 即各个字符的编码长度不等 例如 假设需传送的电文为 ABACCDA 它只有A B C和D四种字符 可设它们的编码分别为00 01 10和11 则上述七个字符的电文便为 00010