树结构的定义和基本操作.ppt

第6章树 6 1树结构的定义和基本操作6 2二叉树6 3遍历二叉树6 4树和森林6 5树的应用习题 前面谈的基本上是线性表结构 线性表 栈 队列 串 一维数组 即使二维数组 矩阵结构 十字类别 也不过只是线性表的组合 即 除首元素和尾元素以外 每一个元素有唯一的前驱和后续元素 树形结构是一种重要的非线性结构 讨论的是层次和分支关系 即 除了有一个根元素没有前驱以外 每一个元素都有唯一的前驱元素 另外 每一个元素有零个或多个后继元素 例如 人类社会的族谱和各种社会组织机构都可以用树来形象表示 树在计算机领域中也得到广泛应用 6 1树结构的定义和基本操作 6 1 1树的定义递归定义 树 tree 是n n 0 个结点的有限集 在任意一棵树中 1 有且只有一个特定的称为根 root 的结点 2 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一棵树 称为子树 subtree 图6 1所示 在图中的树有13个结点 A是树根 其余结点构成三个互不相交的子集 T1 B E F K L T2 C G T3 D H I J M T1 T2和T3都是根A的子树 且它们本身也是一棵树 如在T1中 B是该子树根 其余结点又构成两个互不相交子集 T11 E K L 和T12 F T11和T12都是根B的子树 且它们本身也是一棵树 图6 1树的示例 上面是树的一个递归定义 树除了该递归定义外 还有其它定义 如图6 2所示为图6 1中树的各种表示 从图6 1的示例可以看出 树有两个特点 1 树的根结点没有前驱结点 其余结点有且只有一个前驱结点 2 树结点可以有零个或多个后继结点 树结构描述的是层次和分支关系 图6 2树的其它三种表示方法 图6 2 a 是以嵌套集合的形式表示 任何两个集合 或不相交 或一个包含另一个 图6 2 b 是以广义表的形式表示 根作为子树森林组成的表的名字写在表的左边 图6 2 c 用的是凹入表示法 6 1 2树的常用术语结点 是包含一个数据元素和若干指向其子树的分支 即关系 结点的度 结点拥有的子树数 叶子 度为0的结点 分支结点 度不为0的结点 树的度 树内各结点的度的最大值 图6 1所示树是一个3叉树 孩子结点 child 结点的后继 结点子树的根结点 双亲结点 parent 孩子结点的前驱 s是f的孩子 则f是s的双亲 兄弟结点 sibling 同一个双亲的孩子之间互称为兄弟 祖先结点 从根到该结点的所经过分支上的所有结点 图6 1树中L结点的祖先结点是A B F 子孙结点 以某结点为根的子树中任一结点都称为该结点的子孙 图6 1树中D的子孙结点为H I J M 结点的层次 根是第1层 依次为第2层 树的深度 树中结点的最大层次 图6 1所示的树深度为4 有序树 树中结点的各子树看成从左至右是有次序的 例如 人类社会的族谱就是一个有序树 无序树 树中结点的各子树没有次序的 孩子结点的顺序可以调整 森林 m m 0 棵互不相交的树的集合 森林和树之间的联系是 一棵树取掉根 其子树构成一个森林 同样 一个森林增加一个根结点成为树 6 1 3树的基本操作 1 initiate T T树的初始化 包括建树 2 root T 求T树的根 3 parent T x 求T树中x结点的双亲结点 4 child T x i 求T树中x结点的第i个孩子结点 5 right sibling T x 求T树中x结点的右兄弟 6 Insert child y i x 将根为x的子树置为y结点的第i个孩子 7 del child x i 删除x结点的第i个孩子 整个子树 8 traverse T 遍历T树 按某个次序依次访问树中每一个结点 并使每个结点都被访问且只被访问一次 9 clear T 置空T树 以上操作的具体实现 依赖于采用的存储结构 6 2二叉树 6 2 1定义及其操作二叉树是另一种树形结构 它的特点是每一个结点至多只有两棵子树 并且 子树有左 右之分 其次序不能颠倒 递归定义 二叉树是n n 0 个结点有限集 当n 1时 有而且仅有一个结点为根结点 其余结点构成为2个互不相交的子集T1 T2 其中每一个子集又是一棵二叉树 分别称作为根结点的左子树和右子树 注意 二叉树不是度为2的树 在度为2的树中 当一个结点的度为1时 其子树是不考虑序的 而在二叉树中 当一个结点的度为1时 其子树要考虑序 即 是作为双亲的左子树还是作为双亲右子树 另外 树不允许为空树 但二叉树允许为空 由二叉树的递归定义可知 二叉树有五种基本形态 如图6 3所示 a 空树 b 仅有根 c 右子树空 c 左 右子树均在d 左子树空 图6 3二叉树的五种形态 由二叉树的递归定义可知 二叉树有五种基本形态 如图6 3所示 与树的基本操作类似 二叉树有下面一些基本操作 l lch T x 求T树中x结点的左孩子 2 rch T x 求T树中x结点的右孩子 3 lsibling T x 求T树中x结点的左兄弟 4 rsibling T x 求T树中x结点的右兄弟 其他操作与树相同 6 2 2二叉树的性质二叉树具有下列重要性质 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 当i 1时 只有一个根结点 2i 1 20 1 由于二叉树的每一个结点的度最多为2 因此 当i 2时 第i层上的结点数 最多为上一层的2倍 所以 第2层最多有2 1 21个结点 第3层最多有2 21 22个 依次类推 第i层最多有2 2i 2 2i 1个 性质2 深度为k的二叉树至多有2k 1个结点 k 1 由性质1可见 深度为k的二叉树的最大结点数为 第i层上的最大结点数 2i 1 2k 1 性质3 对任何一棵二叉树T 如果其叶子结点数为n0 度为2的结点数为n2 则n0 n2 1 在二叉树中 度为1的结点为n1 这样树的结点数n n0 n1 n2另外 除根结点外每个结点都有唯一的双亲结点指向该结点 所以度为1的结点指向一个后续 而度为2的结点指向两个后续 因此 二叉树结点数n n1 2 n2 1 因为n n0 n1 n2 n1 2 n2 1可得n0 n2 1 下面介绍两种特殊的二叉树 满二叉树 一棵深度为k的二叉树 若其有2k 1个结点 则称为满二叉树 在满二叉树中只有度为0和度为2的结点 并且在每一层上的结点数都是该层所能取结点的最大值 如图6 4 a 所示为一个深度为4的满二叉树 a 满二叉树 完全二叉树 一个深度为k的二叉树 其结点数n 2k 1 并且这n个结点所构成的二叉树 与一个深度为k的满二叉树前n个结点位置相同 则该树是一个深度为k的完全二叉树 如图6 4 b 所示为一个深度为4 结点数为12的完全二叉树 深度为k的完全二叉树 其前k 1层是满二叉树 最后第k层的结点依次排在左边的位置上 b 完全二叉树 完全二叉树有如下两个重要性质 性质4 具有n个结点的完全二叉树的深度为trunc log2n 1 注 trunc x 为取整函数 该函数无条件舍掉x的小数部分 性质5 如果对一棵有n个结点的完全二叉树 其深度trunc log2n 1 的结点按顺序标号 标号的顺序从根开始 按层次自上而下 在每一层上从左至右 如图6 4 b 所示的完全二叉树 就是按此规则标号 对于树中任意标号为i的结点有以下特性 1 i 1时 i的双亲结点是trunc i 2 2 若2i n 则i的左孩子是标号为2i的结点 若2i n 则该结点不存在左孩子 3 若2i 1 n 则i的右孩子是标号为2i 1的结点 若2i 1 n 则该结点不存在右孩子 6 2 3二叉树的存储结构 1 顺序存储结构满二叉树或完全二叉树顺序存储方式 即用一个数组按结点的标号顺序依次存放二叉树中的数据元素 图6 4 b 是一棵完全二叉树 可以用一维数组bt 12 作为它的存储结构 将二叉树中标号为i的结点的数据元素存放在分量bt i 1 中 如图6 5 a 所示 存储位置暗藏了树中的关系 树的关系是通过完全二叉树的性质实现 例如bt 5 的双亲结点标号是k trunc i 1 2 3 双亲结点所对应的数组分量bt k 1 bt 2 a 完全二叉树 非完全二叉树 也必须按完全二叉树的形式存储 如图6 5 b 所示 图中 0 表示该结点不存在 对于畸形二叉树 树中大量存在度为1和度为0的结点 采用顺序存储方式 空间浪费较大 b 非完全二叉树 2 链式结构由于二叉树是一种非线性结构 一般情况下采用链式存储结构 不同的结点结构 可以构成不同的链式结构 常用的有以下两种 a 标准存储 也称为 二叉链表 每一个结点有三个域 即 数据域 左指针 右指针 用C语言描述如下 structbitnode intdata structnode lch rch typedefstructbitnodeBiTNode b 带逆存储 也称为 三叉链表 在二叉链表中 便于找到一个结点的左右孩子 但要找一个结点的双亲不方便 必须从树根开始遍历整个二叉树 所以 在结点中增加一个指向双亲结点的指针域 结点的结构如下 structtritnode intdata structnode lch rch parent typedefstructtritnodeTriTnode 图6 6是一个二叉树的两种链式存储结构图示 从图中可知 二叉树的链式存储结构和逻辑结构是一致的 a 二叉树逻辑结构 b 二叉链表 c 二叉链表 图6 6二叉树的链式存储结构 6 3遍历二叉树 一个遍历二叉树的问题 即 按一定规律访问二叉树上的每个结点 且每个结点只能访问一次 这里 访问 的含义很广 可以是对结点作各种处理 在线性结构中 因为除尾结点外 每一个结点都有唯一后续 所以只要从首结点开始 每次取后继结点就可以遍历线性结构中每一个结点 而二叉树是一种非线性结构 每一个结点可能有两个后续 因此需要寻找一种规律 将层次形的二叉树序列转化为一个线性序列 由递归定义可知 二叉树是由三个基本单元组成 即 根结点 左子树和右子树 因此 若能依次遍历这三部分 便是遍历了整个二叉树 若以 T R分别表示遍历左子树 访问根和遍历右子树 则可有六种遍历方案 TLR LTR LRT TRL RTL RLT 通常限定先遍历左子树 后遍历右子树 所以 二叉树的遍历主要指前三种 6 3 1二叉树遍历的递归算法 1 前序遍历 TLR 递归算法前序遍历 也可以称为前序遍历 二叉树的操作定义为 若二叉树为空 则空操作 不作任何操作 否则 1 访问根结点 2 前序访问左子树 3 前序访问右子树 算法6 1前序遍历二叉树的递归算法 voidprev BiTNode root if root NULL printf d root data 访问根结点 prev root lch prev root rch 2 中序遍历 LTR 递归算法中序遍历二叉树的操作定义为 若二叉树为空 则空操作 不作任何操作 否则 1 中序访问左子树 2 访问根结点 3 中序访问右子树 由中序遍历的定义 可得到中序遍历二叉树的递归算法如下 算法6 2中序遍历二叉树的递归算法 voidmid BiTNode root if root NULL mid root lch printf d root data 访问根结点 mid root rch 3 后序遍历 LRT 递归算法后序遍历二叉树的操作定义为 若二叉树为空 则空操作 不作任何操作 否则 1 后序访问左子树 2 后序访问右子树 3 访问根结点 由后序遍历的定义 可得到后序遍历二叉树的递归算法如下 算法6 3后序遍历二叉树的递归算法 voidpos BiTNode root if root NULL pos root lch pos root rch printf d root data 访问根结点 图6 7表达式 a b c d e 的二叉树 前序遍历二叉树 得到二叉树的前序序列为 a bc de中序遍历二叉树 得到此树的中序序列为 a b c d e后序遍历二叉树 得到此树的后序序列为 abc de 递归算法逻辑清晰 易懂 但在实现时 由于函数调用栈层层叠加 所以效率不高 每次函数调用 都要保存函数返回地址 实现参数传递 创建局部变量 下面讨论二叉树遍历的非递归算法 6 3 2二叉树遍历的非递归算法 1 前序非递归的算法前序遍历的特点是 首先访问根 访问完根后访问左子树 所以对每一个结点 在访问完该结点后 沿其左链访问下来 直到左链为空 这时 所有已被访问过的结点进栈 然后结点出栈 对于每一个出栈结点 即表示该结点和其左子树已被访问结束 按照前序遍历的定义 应该访问该结点的右子树 1 当前指针指向根结点 2 打印当前结点 当前指针指向其左孩子并进栈 重复 2 直至左孩子为NULL 3 依次退栈 将当前指针指向右孩子 4 若栈非空或当前指针非NULL 执行2 否则结束 算法6 4前序遍历二叉树的非递归算法 voidBiT PreOrder BiTNode root BiTNode p node MAX inttop 0 p root do while p NULL printf d p data node top p top p p lch if top 0 top p node top p p rch 凡是退栈的指针 其所指的结点及其左子树 都已遍历 while top 0 p NULL 2 中序非递归的算法中序的特点是 首先访问左子树 所以对每一个结点 沿其左链走下来 直到左链为空 所有经过的结点进栈 然后结点出栈 对于每一个出栈结点 即表示该结点的左子树已访问结束 按照中序遍历的定义 应该访问该结点 根 访问完该结点后 访问该结点的右子树 1 当前指针指向根结点 2 当前结点进栈 当前指针指向其左孩子 重复 2 直至左孩子为NULL 3 依次退栈 退栈指针成为当前指针 打印当前结点 4 将当前指针指向右孩子 5 若栈非空或当前指针非NULL 执行2 否则结束 算法6 5中序遍历二叉树的非递归算法 voidBiT MidOrder BiTNode root BiTNode p node MAX inttop 0 p root do while p NULL node top p top p p lch if top 0 top p node top printf d p data p p rch 凡是退栈的指针 其所指的结点的左子树 都已遍历 while top 0 p NULL 3 后序非递归的算法后序的特点是 在左 右子树都被访问结束后 才能访问根 所以 每一个出栈的结点都要判断是访问完左子树返回根 还是访问完右子树返回根 一个结点只有在其右子树访问结束后 才能访问该结点 因此 需要对进栈的指针进行补充说明 在这里引入了一个标志栈intflag MAX 1 当前指针指向根结点 2 当前结点进栈 所对应的标志栈为0 当前指针指向其左孩子 重复 2 直至左孩子为NULL 3 判断栈顶元素的标志 若为1 则依次退栈 并打印退栈指针所指结点 直到标志为0 4 将栈顶元素的标志变为1 将当前指针为指向栈顶元素的右孩子 5 若栈非空或当前指针非NULL 执行2 否则结束 算法6 6后序遍历二叉树的非递归算法 defineLEFT0 defineRIGHT1 voidBiT PostOrder BiTNode root BiTNode p node MAX inttop flag MAX p root top 0 top指向下一个进栈的位置 do while p NULL 结点非空 进栈 遍历左子树 直至最左下结点 node top p flag top LEFT top p p lch while top 0 6 3 3二叉树的层次遍历算法按照层次遍历二叉树 是通过队列实现的 首先 将根的结点入列 然后 每次判断队列是否为空 若队列不为空 则取出队首元素所对应的结点 并将该不为空 NULL 的孩子结点的指针入列 如若队列为空 则遍历结束 算法6 7二叉树的层次遍历算法 voidTravelByLevel BiTNode root BiTNode p QueueQ Q为指针队列 Queue Init 6 3 4遍历算法的应用 1 一种建树算法已知树的结构 可以写出唯一的前序序列 但反之 则不能建立唯一的树结构 这里推荐一种改进的前序遍历方法 其遍历序列可以和树结构一一对应 该遍历方法对空指针用字符 表示 于是6 8图的前序序列为 ABD E C 由于这样的序列和树结构一一对应 所以可以用此类序列作为建树的参数 图6 8 图6 8 算法6 8一种建立二叉树的算法 s 中为带空指针记号的前序序列 pi为下标在 函数调用中被改变 BiTNode BiT Create chars int pi BiTNode root charch ch s pi pi if ch return NULL 创建根结点 root BiTNode malloc sizeof BiTNode root data ch 创建左子树 并将左子树的根指针赋给root lchild root lchild BiT Create s pi pi在调用中已被修改 创建右子树 并将右子树的根指针赋给root lchild root rchild BiT Create s pi return root main chars 20 ABD E C inti 0 BiTNode root root BiT Create s i 2 释放二叉树结构树结构是一种动态数据结构 它由一个个结点逐渐创建链接而成 当树结构处理完成后 有必要释放其所有结点 遍历算法的本质是访问每个结点且每个结点只访问一次 这和释放每个结点的要求非常相似 以下是利用后序遍历算法的结构 释放二叉树中所有结点的存储结构的算法 算法6 9释放二叉树中所有结点的存储结构的算法 voidBiT Free BiTNode root if root NULL BiT Free root lchild BiT Free root rchild free root 将访问语句改为释放语句 需要注意的是 必须采用后序遍历算法的结构 而不能是前序或中序的遍历结构 因为只有在释放完左右子树之 才允许释放根结点 否则 程序的运行是不安全的 3 统计结点的个数统计结点个数是树结构的一个简单应用算法 同样可以借鉴遍历算法的结构 只是将访问结点的语句改为加法运算而已 算法6 10统计二叉树结点个数算法 intBiT Count BiTNode root intleft right if root NULL return 0 left BiT Count root lchild 计算左子树的结点数 right BiT Count root rchild 计算右子树的结点数 return left right 1 计算结点总数 算法6 11统计二叉树树叶结点的个数算法 统计结点个数算法的一个变形是 统计树叶结点的个数 这只需要在做加法运算前 先判断结点的度是否为0 intBiT LeafCount BiTNode root intleft right if root NULL return 0 if root lchild NULL 4 求二叉树的深度空二叉树的深度为0 否则它的深度等于其根的左右子树的深度的最大值加1 显然这是一个递归定义 最简捷的实现方式是采用递归算法 同样 在此借鉴后序遍历算法的结构 在遍历根的左右子树时 分别计算其深度 于是二叉树的深度自然就求出了 算法6 12计算二叉树的深度算法 intBiT Depth BiTNODE root intleft right if root NULL return 0 left BiT Depth root lchild 计算左子树深度 right BiT Depth root rchild 计算右子树深度 return max left right 1 5 交换树中每个结点的左右子树若仅仅交换某个结点的左右子树 那就太简单了 要求对每个结点的左右子树都进行交换 这是加强对遍历算法理解 应用的一个常用练习 以下采用后序遍历的算法结 交换每个结点的左右子树 算法6 13交换二叉树每个结点的左右子树算法 voidBiT Exchange BiTNode root BiTNode p if root NULL return BiT Exchange root lchild 对左子树中的每个结点交换 BiT Exchange root rchild 对右子树中的每个结点交换 交换结点的左右孩子 p root lchild root lchild root rchild root rchild p 6 根据前序序列和中序序列构造二叉树结构我们已经知道二叉树结构和它的某个遍历序列不存在一一对应的关系 但若已知一个二叉树的前序序列和中序序列 却一定可以唯一确定一个二叉树的结构 算法思路如下 a 因为前序序列的首元素为根元素 所以可以立即确定根结点 b 在中序序列中定位根结点的位置 必然将中序序列分为根元素和左 右子树三个部分 c 由于已知左 右子树的元素个数 也自然可以将前序序列分为根元素和左 右子树三个部分 d 建树问题被细分为建左右子树的同类小问题 在问题逐步分解细化过程中 若中序序列和前序序列都为空序列 则表明待建子树为空 示例 设pre 0 到pre 6 为前序序列 abdecgh mid 0 到mid 6 为中序序列 dbeagch 其建树的步骤如下 确定根结点的数据为pre 0 即字符a 2 在中序序列中定位字符a的位置 即下标为3 可以确定mid 0 到mid 2 为左子树的中序序列 mid 4 到mid 6 为右子树的中序序列 3 根据中序序列与前序序列的对应关系 可知pre 1 到pre 3 为左子树的前序序列 pre 4 到pre 6 为右子树的前序序列 4 根据前序序列pre 1 到pre 3 中序序列mid 0 到mid 2 构造左子树 根据前序序列pre 4 到pre 6 中序序列mid 4 到mid 6 构造右子树 在程序中值得注意的是 在这种递归算法策略中 大小问题的描述 即函数的参数形式 必须具有完全相同的形式 算法6 14由前序序列和中序序列构造二叉树结构算法 pre 中存储前序序列 mid 中存储中序序列 n为序列中元素的个数 pre i为前序序列在pre 中的起始位置 mid i为前序序列在mid 中的起始位置 BiTNode premid charpre charmid intpre i intmid i intn inti 0 BiTNode root if n 0 return NULL 最终解决方案 空序列建空树 在中序序列中定位根元素的位置 while idata pre pre i 建左子树 root lchild premid pre mid pre i 1 mid i i 建右子树 root rchild premid pre mid pre i i 1 mid i i 1 n i 1 return root main charpre abdecgh mid dbeagch BiTNode root root premid pre mid 0 0 7 6 4树和森林 6 4 1树的存储结构在大量的应用中 可以使用多种形式的存储结构来表示树 在这里介绍三种表示树的方法 在具体应用中可以采用这三种表示方法 也可以定义其它存储结构 以满足应用的需求 采用某种结构的理由来自实践的需要 即使数据完全一样 因具体应用不同 所以结构就可能不同 1 双亲表示法采用一组连续空间存储树的结点 同时在每个结点中附设一个指示器指示其双亲结点在该连续空间中位置 若该连续空间用数组表示 则每一个结点的指示器值是其双亲结点在数组中下标 用C语言定义的树的双亲表示存储结构如下 structnode intdata intparent 双亲结点的下标 tree MAX 例如 图6 10所示为一棵树及其双亲表示的存储结构 其中 tree 0 parent存放树中结点数 图6 10树的双亲表示法 在这种存储结构中 利用每一个结点的双亲指示域 很容易找到每一个结点的双亲 同样找结点的祖先结点也非常便利 但要找某个结点的孩子或子孙结点 需遍历整个数组 2 孩子表示法将树中每个结点的孩子结点用一个单链表 孩链表 表示 那么 一棵树有n个结点就有n个孩链表 度为0的结点 所对应的孩链表为空表 这n个孩链表的头指针又构成一个线性表 用一个指针数组存储该线性表 这就构成了树的孩子表示法的存储结构 如图6 11 a 所示为图6 10中树的孩子表示法的存储结构 在这种存储结构中 找一个结点的孩子十分方便 例如 要找结点B的孩子 只要遍历结点B的孩链表 就可以找到该结点的所有孩子 但要找一个结点的双亲就不方便 需要遍历整个结构 例如 要找结点D的双亲结点 就要找到某个结点的孩链表中有结点D 该结点就是D的双亲 在这里结点B的孩链表中包含了D结点的位置 所以 B是D的双亲结点 图6 11图6 10中树的孩子表示法 为了便于查找结点的双亲 将树的双亲表示法和孩子表示法结合起来 就有了树的双亲孩子表示法 如图6 11 b 所示就是树的双亲孩子表示法存储结构示意图 这种结构用C语言描述如下 structnode intpos 结点在数组中下标 structnode link structt node chardata intparent structnode first link 孩子链表的头指针 tree MAX 其中 tree 0 parent用来存放树中结点数 3 孩子兄弟表示法又称为二叉树表示法 也称为二叉链表表示法 即 以二叉链表作为树的存储结构 链表中结点的两个指针域分别指向该结点的第一个孩子结点和右边下一个兄弟结点 分别命名为son域和brother域 structnode intdata structnode son 第1个孩子 structnode brother 下一个兄弟 图6 12图6 10中树的二叉链表表示法 图6 12所示为图6 10中树的孩子兄弟链表的存储结构 在这种存储结构中 找一个结点的孩子十分方便 6 4 2树与二叉树的转换由于二叉树和树都可以用二叉链表存储 因此 可从树的孩子兄弟链表中 导出树与二叉树之间的一个对应关系 也就是说 可以找到唯一的二叉树与之对应 从物理 存储 结构来看 它们的二叉链表是相同的 只是解释不同而已 例如 图6 12所示为图6 10中树的孩子兄弟链表的存储结构 表中结点的两个指针域son域和brother域解释为 指向该结点的第一个孩子结点和下一个兄弟结点 但也可以看成是将图6 10中树转换成的二叉树的存储结构 这时 表中结点的两个指针域son域和brother域就应解释为 指向该结点左孩子和右孩子 所以 树与二叉树之间转换和树的二叉链表表示法所用的方法相同 6 4 3森林与二叉树的转换 1 森林转换为二叉树从树的二叉链表表示的定义可知 一棵与树对应的二叉树 其右子树必为空 所以 只要将森林中所有树的根结点视为兄弟 即将各个树转换为二叉树 再按森林中树的次序 依次将后一个树作为前一棵树的右子树 并将第一棵树的根作为目标二叉树树根 就可以将一个森林转换成二叉树 转换规则定义 若F T1 T2 Tn 是森林 可按以下规则转成一棵二叉树B F root LB RB 1 若F为空 即n 0 则B F 为空树 2 若F非空 即n 0 则B F 的根是T1的根 其左子树为LB是从T1根结点的子树森林F1 T11 T12 T1m 转换而成的二叉树 其右子树RB是从除T1外的森林F T2 Tn 转换而成的二叉树 图6 13森林与二叉树的对应关系示例 2 二叉树还原为森林转换规则定义 若B root LB RB 是一棵二叉树 可按以下规则转换为森林F T1 T2 Tn 1 若B为空 则B F 为空树 2 若B非空 则F中第一棵树T1的根是二叉树的根 T1中根结点的子森林F1是由B的左子树LB转换而成的森林 F中除T1之外其余树组成的森林F T2 T3 Tm 是由B F 的右子树RB转换而成 森林与目标二叉树之间有一一对应的关系 所以 对森林的操作也可以在二叉树的结构上进行 回顾 树和森林一 树的存储结构 1 双亲表示法2 孩子表示法3 孩子兄弟表示法 二 树和二叉树的转换三 森林和二叉树的转换四 二叉树转换为树或森林 6 5树的应用 6 5 1二叉排序树6 5 2哈夫曼树 6 5 1二叉排序树1 二叉排序树的定义二叉排序树 是一种很有用的 特殊的二叉树 它的每一个结点数据中都有一个关键值 并有如下性质 对于每个结点 如果其左子树非空 则左子树的所有结点的关键值都小于该结点的关键值 如果其右子树非空 则右子树的所有结点的关键值都大于该结点的关键值 如图6 14所示的二叉树 就是一棵二叉排序树 二叉排序树有查找效率高 增添 删除方便的特点 而且对二叉排序树进行中序遍历 将得到一个按结点关键值递增有序的中序线性序列 所以 它被广泛地用来作为动态查找的数据结构 二叉排序树的存储结构也采用二叉链表 存储结构如下 举例 用二叉排序树作为目录树 把一个记录的关键码和记录的地址作为二叉排序树的结点 按关键码值建成二叉排序树 这样 既能像有序表那样进行高效查找 又能像链表那样灵活删除 而不需要移动其他结点 如要得到按关键码值的排序结果 还可以对其进行中序遍历 structbstnode intdata structbstnode lch rch typedefstructbstnodeBSTNode 2 二叉排序树的查找在二叉排序树中进行查找 将要查找的值从树根开始比较 若与根的关键值相等 则成功 若比根的关键值小 则到左子树找 若比根的关键值大 则到右子树找 直到查找成功或查找子树为空 失败 若成功 则返回查找到结点的地址 若失败 则返回空指针 查找的递归算法如下 算法6 15二叉排序树的查找递归算法 BSTNode search BSTNode root intx if root NULL return NULL while root if x root elem key return root if xelem key root root lch elseroot root rch return NULL 3 二叉排序树的插入和生成插入是一个动态的查找过程 首先在树中查找x 若不存在则插入 从空树开始 插入一系列结点 就是二叉排序树的生成过程 例如 给定一组关键值序列为 45 24 53 45 12 24 90 则生成二叉排序树的过程如图所示 45 24 53 45 12 24 90 图6 15二叉排序树的生成过程 x 再插入50 将要插入的关键值存放在数组a MAX 中 MAX为要插入的关键值个数 a 二叉排序树的插入算法算法6 16二叉排序树中插入结点的递归算法BSTNode BSTNode Insert BSTNode root BSTNode newp 在根指针为root的二叉排序树中插入结点 newp if root NULL return newp if newp datadata root lch BSTNode Insert root lch newp elseroot rch BSTNode Insert root rch newp return root 算法6 17二叉排序树中插入结点的非递归算法 BSTNode BSTNode Insert BSTNode root BSTNode newp 在根指针为root的二叉排序树中插入关键值为a i 的结点 BSTNode p root if root NULL return newp while 1 if newp datadata if p lch p p lch else p lch newp return root elseif p rch p p rch else p rch newp return root return root b 建立二叉排序树算法6 18利用插入算法 建立二叉排序树 BSTNode BSTNode Create BSTNode root inta intn 依据a 中元素序列 建立二叉排序树 BSTNode p head NULL inti for i 0 idata a i p lch p rch NULL head BSTNode Insert head p 调用插入函数 return head 3 二叉排序树的删除在二叉排序树中删除结点 首先要进行查找 若查找成功则删除该结点 但删除之后 不能破坏原二叉排序树中结点的关系 即删除后二叉树的中序序列仍然是按关键值递增有序 删除算法可分下面三种情况讨论 1 被删除结点是叶子结点 2 被删除结点是单分支结点 3 被删除结点是双分支结点 假定 p指向要删除结点 f指向p的双亲结点 且不失一般性 设p是f的右孩子 1 被删除结点是叶子结点若 p结点为叶子结点 只需直接删除 即 将双亲结点指向它的指针 设置为空指针 f rch NULL 2 被删除结点是单分支结点若 p结点为单分支结点 只需用它唯一子树的根去继承它的位置 即 将双亲结点原指向它的指针 设置为指向它的左孩子或右孩子 若只有左子树 则f rch p lch 若只有右子树 则f rch p rch 3 被删除结点是双分支结点若 p结点为双分支结点 为保证删除该结点后 该树的中序序列任然是按关键值递增有序 所以有如下两种方法 方法1 用左子树中序遍历的最后一个结点 左子树的最右结点 替换 p 查找到 p的左子树的右链为空的结点 s 然后 用 s的数据替换 p的数据 最后 删除 s结点 s是其双亲结点的右孩子 并且s rch为NULL 若s lch也为空 则置 s双亲的右指针为NULL 删除 s 若s lch不为空 则置 s双亲的右指针为s lch 删除 s 左子树最右结点 s双亲的右指针改为s lch s lch 方法2 用右子树中序遍历的第一个结点 右子树的最左结点 替换 p 首先 沿 p的右子树的左链 查找到左指针域为空的结点 s 然后 用 s的数据替换 p的数据 最后 删除 s结点 算法6 19二叉排序树中删除结点的算法 x删除结点的关键值 BSTNode BSTNode del BSTNode root intx BSTNode p f s f s p要删除结点 f为p的双亲 s为p的左子树的最右边结点 s f为s双亲 if root NULL return 二叉排序树为空树 f NULL p root while p NULL 查找结束 进行节点删除 下一页 查找失败 无找到要删除的结点 if p NULL return root 删除 p的第一种情形 p为叶子 if p lch NULL 删除 p的第二种情形 p为单分支结点 if p lch NULL 没有左子树 if f NULL root p rch free p return root if f lch p f lch p rch p是双亲的左孩子 elsef rch p rch p是双亲的右孩子 free p return root if p rch NULL 没有右子树 if f NULL root p lch free p return root if f lch p f lch p lch elsef rch p lch free p return root 删除 p的第三种情形 p为双分支结点 s f p s p lch 找 p左子树的最右结点 s s f是 s的父结点 while s rch NULL 循环 直到s右指针为空 s f s s s rch s以替代p 然后删除s结点 p data s data if s lch NULL s是叶子 s f rch NULL 置 s双亲结点的右指针为空 else s有左子树 s f rch s lch 置 s双亲的右指针为 s的左孩子 free s return root 6 5 2哈夫曼树以及应用哈夫曼树 又称为最优树 是一类带权路径长度最短的树 有着广泛的应用 a 基本术语路径 从一个结点到另一个结点之间的若干分支 路径长度 路径的分支数 结点的路径长度 从根到该结点的路径长度 树的路径长度 树中所有结点的路径长度之和 一般记作PL 图6 17所示为计算树的路径长度的示例 在结点数相同的条件下 路径最短的二叉树为完全二叉树 若将上述概念推广到一般情况 考虑带有权值的结点 结点的带权路径 从根到带权结点之间的路径长度与结点上的权值乘积 树的带权路径 树中所有带权结点的带权路径长度之和 无权值结点的路径不考虑 一般记作WPL 即 其中 wk是编号为k结点的权值 lk是根到编号为k结点的路径 n为树中带权结点数 最优二叉树 哈夫曼树 假设有n个权值 w1 w2 wn 是构造一棵有n个叶子结点的严格二叉树 只有度为0和度为2的结点 每个叶子结点带权为wi 则其中带权路径长度WPL最小的严格二叉树称为哈夫曼树 因为 哈夫曼树为严格二叉树 所以 由二叉树性质3可知 哈夫曼树有n个叶子结点 度为0 和n 1非终端结点 度为2 的结点组成 图6 18具有不同带权路径长度的严格二叉树 例如 图6 18中的四棵严格二叉树 都有4个叶子结点A B C D 分别带权7 5 2 4 其中以图6 18 c 和 d 的WPL最小 可以验证它们两个都是哈夫曼树 所以 哈夫曼树不是唯一的 它们各自的WPL的值如下 图6 18 a WPL 7 2 5 2 2 2 4 2 36图6 18 b WPL 7 3 5 3 2 1 4 2 46图6 18 c WPL 7 1 5 2 2 3 4 3 35图6 18 d WPL 7 1 5 2 2 3 4 3 35从图中可以看出 要使二叉树WPL小 就必须在构造树时 使权值大的结点靠近树根 而使权值小的结点远离树根 b 哈夫曼树的构造哈夫曼 Huffman 最早给出了一个带有一般规律的构造最优二叉树的算法 所以俗称为哈夫曼算法 叙述如下 1 根据给定的n个权值 w1 w2 wn 构成n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树Ti中只有一个权为Wi的根结点 其左右子树为空 2 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树 新树根结点的权为左右子树根结点的权之和 3 在F中删除这两棵树 同时将新得到的二叉树加入F中 4 重复 2 和 3 直至F只有含一棵树为止 这棵树便是哈夫曼树 例如 图6 19展示了图6 18 d 的哈夫曼树的构造过程 其中 根结点上标注的数字是结点的权值 图6 19哈夫曼树的构造过程 在图6 19中 每次选取根结点的权值最小的树构造新树 采用先选取的树为左子树 而后选取的树为右子树的规则 这样 对给定的权值序列 其所构造出的哈夫曼树是唯一的 3 哈夫曼编码在通信中 在发送端将要传送电文中的字符序列转换成0 1序列后发送 而接收端将接收到的0 1序列再转换成相应的字符序列 字符序列与0 1序列之间转换是通过信息编码实现的 字符集的编码按长度分类 可以分为两种形式 1 等长编码 采用长度相等的二进制序列表示一个字符 ASC 就是采用7位二进制序列表示一个字符 等长编码对于字符集中使用的频率不同的字符 都采用长度一样的编码 这样得到的电文编码的总长度较长 降低了传输效率 2 不等长编码 每一个字符所对应二进制序列的长度是不等的 在一个字符集中 出现频率高的字符所对应编码长度短 而出现频率低的字符所对应编码长度长 在不等长编码中 为了在接收端将0 1序列还原成字符 必须保证任何字符的编码都不是另一字符编码的前缀 也称为前缀编码 例6 1有一段电文为 ABACCDA 它只有4种字符 1 采用等长编码需要长度为2的0 1编码便可分辨 设 A 00B 01C 10D 11则 ABACCDA 对应的编码串 00010010101100 总长度为14位 接收端可按每两位对应一个字符进行译码 2 采用不等长编码时 将出现次数多的字符采用短的编码 设 A 0B 00C 1D 11则 ABACCDA 对应的编码串为 000011110 总长度为9位 但接收端对这样的电文编码串无法译码 如开始的子串 0000 就可有多种译法 或是 AAAA 或是 ABA 或是 BB 等 因为 上述编码不是前缀编码 若设 A 0B 110C 10D 111则该编码是前缀编码 ABACCDA 对应的编码串为 0110010101110 总长度为13位 接收端可对这样的电文编码进行译码 并且所得到的译码是唯一的 可以利用严格二叉树来设计二进制前缀编码 例6 1中的前缀编码所对应的严格二叉树如图6 20所示 在树中 每一个叶子结点对应一个字符 并约定左分支表示编码0 右分支表示编码1 从根到叶子的路径为该叶子结点上字符的编码 图6 20前缀编码示例 设字符集中的字符在电文中出现的次数为wi 为叶子结点的权值 其编码长度为li 从根到叶子路径长度 电文中有n种字符 则电文的总长度为 wili 由此可见 设计电文总长度最短的二进制前缀编码即为以n种字符出现的频率作权 设计一棵哈夫曼树的问题 由此得到二进制前缀编码称为哈夫曼编码 如图6 18所示的二叉树是一个哈夫曼树 所以 例6 1的前缀编码是一个哈夫曼编码