数据结构-06树.ppt

数据结构 DataStructure 主讲 严冬梅 第6章树和二叉树 Tree Binarytree 第6章树和二叉树 6 1二叉树6 1 1树的定义和基本术语6 2 2二叉树的定义和基本术语6 2 3二叉树的几个基本性质6 2 4二叉树的存储结构6 2二叉树遍历6 2 1问题的提出6 2 2遍历算法描述6 2 3二叉树遍历应用举例6 2 4线索二叉树 6 3树和森林6 3 1树和森林的定义6 3 2树和森林的存储结构6 3 3树 森林与二叉树的转换6 3 4树和森林的遍历6 4树的应用6 4 1堆排序的实现6 4 2二叉排序树6 4 3赫夫曼树及其应用 6 1二叉树 6 1 1树的定义和基本术语6 1 2二叉树的定义和基本术语6 1 3二叉树的几个基本性质6 1 4二叉树的存储结构 第6章树和二叉树 树型结构是一类重要的非线性数据结构 其中以树和二叉树最为常用 直观角度看 树是以分支关系定义的层次结构 树在计算机领域中得到广泛应用 如文件管理中的目录结构 数据库系统中的信息组织形式等 树结构在客观世界中也广泛存在 如人类社会的族谱和各种社会组织机构都可用树来形象表示 本章重点讨论二叉树的存储结构及各种操作 并研究树和森林与二叉树的转换关系 第6章树和二叉树 到目前为止 我们已经介绍了线性数据结构和表数据结构 这些数据结构一般不适合于描述具有层次结构的数据 在层次化的数据之间可能有祖先 后代 上级 下属 整体 部分以及其他类似的关系 例1 Joe的后代 上图给出了Joe的后代 并按层次方式组织 其中Joe在最顶层 Joe的孩子 Ann Mary和John 列在下一层 在父母和孩子间有一条边 在层次表示中 非常容易地找到Ann的兄弟姐妹 Joe的后代 Chris的祖先等 第6章树和二叉树 例2 软件工程 考察另一种层次数据 软件工程中的模块化技术 通过模块化 可以把大的复杂的任务分成一组小的不太复杂的任务 模块化的目标是把软件系统分成许多功能不相关的部分或模块以便于进行相对独立的开发 由于解决几个小问题比解决大问题更容易一些 因此模块化方法可以缩短整个软件的开发时间 另外 不同的程序员可以同时开发不同的模块 如果有必要 每个模块可以再细分 从而得到如图所示的用树形表示的模块层次结构 该树给出了某文字处理器的一种可行的模块分解图 第6章树和二叉树 例3 学校的组织结构 学院 何谓树状结构树是n n 0 个结点的有限集 在任意一棵非空树中 1 有且仅有一个特定的称为根的结点 2 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一棵树 并且称为根的子树 若一棵树中的结点可以有n个子结点 则称这样的树为n元树 例如二叉树中的结点 最多只能有两个结点 A为根结点 B C D M为A的子结点 6 1树的定义和基本术语 树的相关名称及意义根结点 rootnode 一棵树中没有父结点的结点 称为根结点叶 子 结点leafnode或终端结点terminalnode一棵树中没有子结点的结点 称为叶 子 结点或终端结点分支结点或非终端结点 nonterminalnode 除了叶 子 结点以外的其他结点 称为分支结点或非终端结点 6 1树的定义和基本术语 父结点 parent 和子结点 child 若结点x有一个以结点y为树根的子树 则x为y的父结点 父亲 而y为x的子结点 孩子 兄弟 sibling 同一个父结点之子结点 称为兄弟如图B C D的父结点均为A 故B C D互为兄弟结点的度 degree 结点的子树个数 称为结点的度 如图 A的度为3 B的度为3 C的度为1 最大的度值为3 故树为3元树 层次 level 层次为结点之特性值 将根结点之层次设为1 其子结点为2 依此类推 如图 层次为1的有结点A 为2的有结点B C D 为3的有结点E F G H I 6 1树的定义和基本术语 深度 depth 或高度 height 叶子结点的最大层次数称为树的深度 如图 叶子最大层次值为3 故树T的深度为3祖先 ancestor 由某结点X到根结点之路径上的所有结点 均称为X之祖先树林 forest n 0个树的集合称为树林若将一树的根结点移去 所剩这恰是一树林 6 1树的定义和基本术语 6 1树的定义和基本术语 例1 只有根结点的树A例2 一般的树1 此树Tree A共有13个结点 是由三棵子树组成 Tree B T1 B E F K L Tree C T2 C G Tree D T3 D H I J M B C D为三棵子树的根 且互不相交2 T1又分为两个互不相交的Tree E T11 E K L 和Tree F T12 F T2又分为一个树Tree G T21 G T3又分为三棵互不相交的Tree H T31 H M Tree I T32 I 和Tree J T33 J 3 T11又分为 Tree K T111 和Tree L T112 T31又分为 Tree M T311 每棵子树的结构均符合上述定义 6 1树的定义和基本术语 例3 不是一棵树因为 子树Tree H H M 子树Tree I I M 出现了交叉 违反树的定义 树的其它表示形式Tree A的结构 结点A包括 B C D 结点B包括 E F 结点C包括 G 结点D包括 H I J 结点E包括 K L 结点H包括 M 树的表示形式 A B C D B E F C G D H I J E K L H M 2凹入表示法 1集合表示法 6 1 2二叉树的定义和基本术语 二叉树 binarytree 是n n 0 个数据元素的有限集 它或为空集 n 0 或者含有唯一的称为根的元素 且其余元素分成两个互不相交的子集 每个子集自身也是一棵二叉树 分别称为根的左子树和右子树 集合为空的树简称为空树 树中的元素称为结点 6 1 2二叉树的定义和基本术语 根以外的任意两个结点不可能同时在同一棵子树中出现 二叉树的子树有左右之分 不能任意颠倒 如图所示A为根结点D G H J为叶子结点A是B的父亲 B是A的左孩子 C是A的右孩子 A是E的祖先 E是A的子孙 D和E是兄弟 D和F是堂兄弟A B 的度为2 C F I的度为1 D G H J的度为0二叉树的深度为5 二叉树的五种形态 练习 如果只有三个结点 形态如何 左 右子树具全的二叉树 左子树为空的二叉树 空的二叉树 仅有根结点的二叉树 右子树为空的二叉树 满二叉树 fullbinarytree 若二叉树中所有的分支结点的度数都为2 且叶子结点都在同一层次上 则称这类二叉树为满二叉树 若该树的高度为h 则此满二叉树的结点为2h 1 6 1 2二叉树的定义和基本术语 完全二叉树 completebinarytree 假如任意一棵包含n个结点的二叉树中每个结点都可以和同深度的满二叉树中编号为1至n的结点一一对应 则称这类二叉树为完全二叉树 一棵树扣除掉最大阶层那层后为一满二叉树 且阶层最大那层的结点均向左靠齐 则该二叉树称为完全二叉树 level最大层的结点均向左靠齐 完全二叉树 6 1 2二叉树的定义和基本术语 6 1 2二叉树的定义和基本术语 二叉树的应用 表示家族的血缘关系 6 1 2二叉树的定义和基本术语 二叉树的基本操作定义 1 initBiTree T 操作结果 构造一棵空的二叉树T DestroyBiTree T 初始条件 二叉树T存在 操作结果 销毁二叉树TCreateBiTree T definition 初始条件 definition给出二叉树T的定义 操作结果 按definition给出的定义构造二叉树T BiTreeEmpty T 初始条件 二叉树T存在 操作结果 若T为空二叉树 则返回TRUE 否则返回FALSE 6 1 2二叉树的定义和基本术语 二叉树的基本操作定义 2 BiTreeDepth T 初始条件 二叉树T存在 操作结果 返回T的深度 Parent T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 若e是T的非根结点 则返回它的双亲 否则返回 空 LeftChiild T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的左孩子 若e无左孩子 则返回 空 RightChild T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的右孩子 若e无右孩子 则返回 空 6 1 2二叉树的定义和基本术语 二叉树的基本操作定义 3 LeftSibling T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的左兄弟 若e是其双亲的左孩子或无左兄弟 则返回 空 RighrtSibling T e 初始条件 二叉树T存在 e是T中某个结点 操作结果 返回e的右兄弟 若e是其双亲的左孩子或无左兄弟 则返回 空 InsertChild T p LR C 初始条件 二叉树T存在 p指向T中某个结点 左或右的标志LR为0或1 非空二叉树c与T不相交且右子树为空 操作结果 根据LR为0或1 插入c为T中p所指结点的左子树或右子树 p所指结点原有的左子树或右子树均成为c的右子树 6 1 2二叉树的定义和基本术语 二叉树的基本操作定义 4 DeleteChild T p LR 初始条件 二叉树T存在 p指向T中某个结点 LR为0或1 操作结果 根据LR为0或1 删除T中p所指结点的左或右子树 Traverse T 初始条件 二叉树T存在操作结果 依某条搜索路径遍历T 对每个结点进行一次且仅一次访问 例如输出结点元素值 6 1 3二叉树的几个基本性质 性质1在二叉树的第i层上至多有2i 1个结点 i 1 利用数学归纳法证明 i 1时 只有一个根结点 显然2i 1 20 1是对的 现在假定对所有j 1 j i 命题成立 即第j层上至多有2j 1个结点 那么 可以证明j i时命题亦成立 由归纳假设 第i 1层上至多有2i 2个结点 由于二叉树的每个结点度数至多为2 故在第i层上的最大结点数为第i 1层上的最大结点数的两倍 即2 2i 2 2i 1 6 1 3二叉树的几个基本性质 性质2深度为k的二叉树至多有2k 1个结点 k 1 证明 由性质1可见深度为k的二叉树上最大的结点数为 6 1 3二叉树的几个基本性质 性质3对任何一棵二叉树T 如果其终端结点数为n0 度为2的结点数为n2 则 n0 n2 1证明 设度为1的结点数为n1 则结点总数为n n0 n1 n2考虑分支数 Branch n 1 n0 n1 n2 1 1 Branch 0 n0 1 n1 2 n2 n1 2 n2 2 由 1 2 可得 n0 n1 n2 1 n1 2 n2 n0 n2 1 6 1 3二叉树的几个基本性质 性质4具有n个结点的完全二叉树的深度为 证明 假设深度为k 则根据性质2和完全二叉树的定义有2k 1 1 n 2k 1 或2k 1 n 2k取对数便有k 1 log2n k 因为是整数 所以 6 1 3二叉树的几个基本性质 性质5如果对一棵有n个结点的完全二叉树 其深度为 的结点按层序 从第1层到第层 每层从左到右 从1开始编号 则对任意编号为i的结点 1 i n 有 1 如果i 1 则编号为i的结点是二叉树的根 无双亲 如果i 1 则其双亲结点parent i 的编号是 2 如果2i n 则编号为i的结点无左孩子 编号为i的结点为叶子结点 否则其左孩子结点lChild i 的编号是2i 3 如果2i 1 n 则编号为i的结点无右左孩子 否则其右孩子结点rChild i 的编号是2i 1 6 1 3二叉树的几个基本性质 对于E 2 5 1012 没有右孩子对于J 2 10 20 12 为叶子结点 1 顺序存储结构用一组地址连续的存储单元存储二叉树中的数据元素将完全二叉树编号为的结点存储在一维数组下标为的单元中一般二叉树可能浪费大量存储空间 6 1 4二叉树的存储结构 6 1 4二叉树的存储结构 1 顺序存储结构完全二叉树的顺序存储结构定义 constMAXSIZE 100 结点数最大值typedefstruct TElemType data 存储空间基址intnodenum 树中结点数 SqBiTree 完全二叉树的顺序存储结构 1 顺序存储结构 从下标为1的单元开始存储 假设父结点编号为n 可以得到 1 左子结点为父结点乘以2 2 n 2 右子结点为父结点乘以2加1 2 n 1 6 1 4二叉树的存储结构 6 1 4二叉树的存储结构 2 链式存储表示二叉树结点的逻辑结构如左图 二叉链表typedefstructBiTNode TElemTypedata structBiTNode lchild rchild 左 右孩子指针 BiTNode BiTree 完全二叉树的二叉链表结构 6 1 4二叉树的存储结构 二叉树的二叉链表 6 1 4二叉树的存储结构 2 链式存储表示三叉链表typedefstructBiTNode TElemTypedata 结点数据structBiTNode parent lchild rchild BiTNode BiTree 完全二叉树的三叉链表结构 6 1 4二叉树的存储结构 二叉树的三叉链表 6 1 4二叉树的存储结构 3 结构体数组存储可用结构体数组来存储二叉树 此结构体包含3个字段 其中一个字段是用来存放结点的数据内容 而另两个字段则是分别存放左子树和右子树在数组中的索引值 二叉树的结构体数组声明如下 typedefstruct intleft TElemTypedata intright treenode 完全二叉树的二叉链表结构treenodeb tree SIZE 在结构数组中b tree 会将根结点置于数组结构中索引值为0之处 将结点值存在data字段 而left及right字段则分别存储左右子树在数组结构中的索引值 若子树不存在则存值 1 6 1 4二叉树的存储结构 3 结构体数组存储例如 有一棵二叉树其树状结构与结构数组表示法如下 图中根结点为A 故A在结构数组索引值为之处 其左子结点B在索引值1 右子结点B在索引值2 故结点A的left字段和right字段分别为1和2 而结点C的right字段值为 1 表示其没有右子结点 而结点D和E都是叶结点 leafnode 没有子结点 故left和right字段均为 1 6 2二叉树遍历 6 2 1问题的提出6 2 2遍历算法描述6 2 3二叉树遍历应用举例6 2 4线索二叉树 6 2 1问题的提出 遍历二叉树 Traversingbinarytree 如何按某条搜索路径巡访树中每个结点 使得每个结点均被访问到且仅被访问一次 访问 存取操作 打印等加工处理 数组和链表可以从前端到尾端或从尾端到前端依序抽取各个数据值 而二叉树是一种特殊的数据结构 每个结点其下又各有左 右两个分支 二叉树的遍历 是以固定的顺序 有系统地抽取二叉树中的各结点 且每个结点均恰好被抽取一次 二叉树的遍历是以递归的方式进行 以递归的调用顺序不同 可分为三种遍历方式 先序遍历方式中序遍历方式后序遍历方式 6 2 1问题的提出 先序遍历 Preordertraversal 是先遍历根结点 再遍历左子树 最后遍历右子树 若一棵二叉树如右图 则先序遍历的顺序为 DLR 也就是说每当遍历一个结点就先处理该结点 之后先向左方前进 直到无法前进才往右方走 左图中从根结点A开始 先往左子树B再到D 由于D没有左子树 故转向右子树G 再回到B 因为B没有右子树 所以此时A的左子树均遍历完毕 则转向A的右子树 再往左边继续遍历 依此类推 其前序遍历为 ABDGCEHIF 6 2 1问题的提出 先序遍历二叉树的步骤如下 if二叉树为空then遍历结束else 1 访问当前结点 2 先序访问左子树 3 先序访问右子树 6 2 1问题的提出 中序遍历 Inordertraversal 是先遍历左子树 再根结点 最后才遍历右子树 若一棵二叉树如右图 则中序遍历的顺序为 LDR 也就是说一开始先往左方前进 直到无法前进才处理结点 之后再往右方前进 左图中从根结点A开始 一直往左走到D无法再前进 则处理D 再往D之右方到G 此时 已遍历完B之左子树 接着处理B 再往B的右方向前进 由于B没有右子树 故A之左子树遍历完毕 再往A之右子树前进 依此类推 其中序遍历为 DGBAHEICF 6 2 1问题的提出 中序遍历二叉树的步骤如下 if二叉树为空then遍历结束else 1 中序访问左子树 2 访问当前结点 3 中序访问右子树 6 2 1问题的提出 后序遍历 Postordertraversal 是先遍历左子树 再遍历右子树 最后才遍历根结点 若一棵二叉树如右图 则后序遍历的顺序为 LRD 也就是说一开始先往左方前进 直到无法前进才处再往右方前进 最后才处理结点 左图中从根结点A开始 一直往左走到D无法再前进 则往D之右方前进到G 由于G没有左 右子树 故处理结点G 之后由于D之右子树处理完毕 故进而处理D 而B之左子树也相应完成 且结点B没有右子树 故可接着处理B 此时A之左子树已遍历完毕 再往A之右子树C前进 依此类推 其后序遍历为 GDBHIEFCA 6 2 1问题的提出 后序遍历二叉树的步骤如下 if二叉树为空then遍历结束else 1 后序访问左子树 2 后序访问右子树 3 访问当前结点 6 2 1问题的提出 二叉树遍历过程示意图 先序 ABDEC中序 DBEAC后序 DEBCA 遍历练习 先序 ABDGEHCFIJ 中序 DGBEHACIFJ 后序 GDHEBIJFCA 遍历练习 已知某二叉树的先序序列为 abdgcefh 中序序列为 dgbaechf 求其后序序列 先序abdgcefh 中序dgbaechf abdgcefh abdgcefh dgbaechf dgbaechf 根 根 根 根 根 根 遍历练习 已知某二叉树的后序序列为 gdbehfca 中序序列为 dgbaechf 求其先序序列 后序gdbehfca 中序dgbaechf gdbehfca gdbehfca dgbaechf dgbaechf 根 根 根 根 根 根 6 2 2遍历算法描述 先序递归算法 先序遍历以T为根指针的二叉树voidPreorder BiTreeT void visit BiTree if T T NULL时 二叉树为空树 不做任何操作visit T 通过函数指针 visit访问根结点 以便灵活完成相应的操作Preorder T lchild visit 先序遍历左子树Preorder T rchild visit 先序遍历右子树 6 2 2遍历算法描述 中序递归算法 中序遍历以T为根指针的二叉树voidInorder BiTreeT void visit BiTree if T T NULL时 二叉树为空树 不做任何操作Inorder T lchild visit 中序遍历左子树visit T 通过函数指针 visit访问根结点 以便灵活完成相应的操作Inorder T rchild visit 中序遍历右子树 6 2 2遍历算法描述 后序递归算法 后序遍历以T为根指针的二叉树voidPostorder BiTreeT void visit BiTree if T T NULL时 二叉树为空树 不做任何操作Postorder T lchild visit 后序遍历左子树Postorder T rchild visit 后序遍历右子树visit T 通过函数指针 visit访问根结点 以便灵活完成相应的操作 6 2 2遍历算法描述 堆栈遍历算法 typedefenum Travel 1 Visit 0 TaskType 为Travel时工作状态是遍历 为Visit时是访问typedefstruct BiTreeptr 指向二叉树结点的指针TaskTypetask 任务的性质 SElemType 栈元素的类型定义 6 2 2遍历算法描述 先序堆栈算法 voidPreOrder iter BiTreeBT void visit BiTree 利用栈实现中序遍历二叉树 T为指向二叉树的根结点的头指针InitStack S e ptr BT e task Travel e为栈元素if BT Push S e 布置初始任务while StackEmpty S 每次处理一项任务Pop S e if e ptr 处理非空树的遍历任务while e ptr p e ptr visit e ptr coutdata e ptr p rchild Push S e 最不迫切任务 遍历右子树 进栈e ptr p lchild Push S e 也可直接处理迫切任务 遍历左子树 if while PreOrder iter 6 2 2遍历算法描述 中序堆栈算法 voidInOrder iter BiTreeBT void visit BiTree 利用栈实现中序遍历二叉树 T为指向二叉树的根结点的头指针InitStack S e ptr BT e task Travel e为栈元素if BT Push S e 布置初始任务while StackEmpty S 每次处理一项任务Pop S e if e task Visit visit e ptr 处理访问任务elseif e ptr 处理非空树的遍历任务p e ptr e ptr p rchild Push S e 最不迫切任务 遍历右子树 进栈e ptr p e task Visit Push S e 处理访问任务的工作状态进栈e ptr p lchild e task Travel Push S e 迫切任务 遍历左子树 进栈 if while InOrder iter 6 2 2遍历算法描述 后序堆栈算法 voidPostOrder iter BiTreeBT void visit BiTree 利用栈实现中序遍历二叉树 T为指向二叉树的根结点的头指针InitStack S e ptr BT e task Travel e为栈元素if BT Push S e 布置初始任务while StackEmpty S 每次处理一项任务Pop S e if e task Visit visit e ptr 处理访问任务elseif e ptr 处理非空树的遍历任务p e ptr e ptr p e task Visit Push S e 处理访问任务的工作状态进栈e ptr p rchild e task Travel Push S e 不迫切任务e ptr p lchild Push S e 迫切任务 遍历左子树 进栈 if while PostOrder iter 6 2 3二叉树遍历应用举例 二叉树的遍历是二叉树各种操作的基础 例如求结点双亲 结点的孩子 判定结点所在层次等 甚至建立二叉树都要利用遍历 6 2 3 1建立二叉链表按先序建立二叉链表 输入根结点若为 则为空树否则生成新结点 设置data递归建立其左子树递归建立其右子树 输入顺序 AB DE C 6 2 3二叉树遍历应用举例 建立二叉链表 算法6 3 voidCreatebiTree BiTree 递归建 遍历 右子树 else CreateBiTree 6 2 3二叉树遍历应用举例 6 2 3 2求森林的深度深度 森林 MAX 叶子结点所在层次的最大值 先序算法6 4voidBiTreeDepth BiTreeT inth int 6 2 3二叉树遍历应用举例 D 0h 1 D 1h 1 D 2h 2 D 3h 3 D 3h 2 D 4h 4 D 4h 4 D 4h 3 D 3h 3 D 4 D depth 6 2 3二叉树遍历应用举例 后序算法6 5深度 MAX 左子树的深度 右子树的深度 1intBiTreeDepth BiTreeT 后序遍历求T所指二叉树的深度if T return0 else hL BiTreeDepth T lchild hR BiTreeDepth T rchild if hL hR returnhL 1 elsereturnhR 1 if BiTreeDepth 6 2 3二叉树遍历应用举例 6 2 3 3复制二叉树 算法6 6 BiTNode GetTreeNode TElemTypeitem BiTNode lptr BiTNode rptr T newBiTNode T data item T lchild lptr T rchild rptr returnT GetTreeNodeBiTNode CopyTree BiTNode T 已知二叉树的根指针为T 本算法返回它的复制品的根指针if T returnNULL 复制一棵空树if T lchild newlptr CopyTree T lchild 递归复制 遍历 左子树elsenewlptr NULL if T rchild newrptr CopyTree T rchild 递归复制 遍历 右子树elsenewrptr NULL newnode GetTreeNode T data newlptr newrptr 生成根结点returnnewnode CopyTree 6 2 3二叉树遍历应用举例 6 2 3 4算术表达式计算表达式的递归定义若表达式为数或简单变量 则相应二叉树中只有一个根结点 其数据域存放该表达式的信息 若表达式 第一操作数 运算符 第二操作数 则相应的二叉树中以左子树表示第一操作数 以右子树表示第二操作数 根结点存放运算符 若为一元运算 则左子树为空 操作数本身也是表达式 6 2 3二叉树遍历应用举例 求表达式 exp a b c d e f constPLUS 1 constMINUS 2 constASTERISK 3 constSLANT 4 doublevalue BiTreeT floatopnd 对以T为根指针的二叉树表示的算术表达式求值 操作数的数值存放在一维数组opnd中if T return0 空树的值为0if T data 0 returnopnd T data Lv value T lchild opnd 遍历左子树求第一操作数Rv value T rchild opnd 遍历右子树求第二操作数switch T data casePLUS v Lv Rv caseMINUS v Lv Rv caseASTERISK v LV Rv caseSLANT v Lv Rv default ERROR 不合法的运算符 switchreturnv value 表达式计算算法 6 2 4线索二叉树 遍历二叉树时 每个结点只有一个直接前驱和直接后继 为了提高再次遍历二叉树的速度 可在结点中增加两个指针域 使之分别指向前驱和后继 这些指针称为 线索 加上线索的二叉树称为 线索二叉树 相应的存储结构称为 线索链表 按照遍历的顺序 可分为 先序全线索链表 中序全线索链表和后序全线索链表 全线索链表存储结构typedefstructBiTreeNode TElemTypedata structBiTreeNode lchild rchild structBiTreeNode pred succ BiThrNode BiThrTree 中序全线索树DBGEHACIJF 6 2 4线索二叉树 中序遍历中序全线索链表 算法6 8 voidInOrder BiThrTreeH void visit BiTree H为指向中序线索链表中头结点的指针 中序遍历以H lchild所指结点为根的二叉树p H succ while p H visit p p p succ while InOrder 建立中序全线索链表 算法6 9 6 10 voidInOrderThreading BiThrTree 右子树线索化 if InThreading 6 2 4线索二叉树 建立线索链表也可以在每个结点中增加两个类型的成员 lthread和rthread分别用来指示lchild和rchild是子树指针还是线索 若child字段为引线 则thread字段值为1 若child字段为指针 则thread字段值为0 typedefenum Link Thread PointerTag typedefstructBiTreeNode TElemTypedata structBiTreeNode lchild rchild PointerTaglthread rthread BiThrNode BiThrTree 6 2 4线索二叉树 左图的中序遍历顺序为 12345678 6 2 4线索二叉树 若二叉树为空时 开头结点的左指针会指向NULL 故建立左引线指向自己 如下图 建立中序全线索链表 P134 voidInOrderThreading BiThrTree 右子树线索化 if InThreading 6 2 4线索二叉树 插入一新结点t成为结点s的右子树 s的右子树为空 1 t的右引线指向s右引线指向的结点 2 t的左引线指向s 3 s的右指针指向t 6 2 4线索二叉树 s的右子树非空 1 t的右指针指向s之右子树 2 t的左引线指向s 3 s的右指针指向t 4 s的原右子树最左边结点的左引线指向t 6 3树和森林 6 3 1树和森林的定义6 3 2树和森林的存储结构6 3 3树 森林与二叉树的转换6 3 4树和森林的遍历 6 3 1树和森林的定义 树 tree 是n n 0 个数据元素 结点 的有限集D 若D为空集则为空树 否则 在D中存在惟一的称为根结点数据元素root 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每个子集本身又是一棵符合本定义的树 并称为根root的子树 6 3 1树和森林的定义 森林 forest 是m m 0 棵互不相交的树的集合 树 tree 是n n 0 个结点的有限集 若n 0 为空树 否则 树由一个根结点和m m 0 棵树组成的森林构成 森林中的每棵树都是根的子树 6 3 1树和森林的定义 树的基本操作定义 1 InitTree T 操作结果 构造一棵空树T DestroyTree T 初始条件 树T存在 操作结果 销毁树T结构 CreateTree T definition 初始条件 definition给出树T的定义 操作结果 按definition给出的定义构造树T TreeEmpty T 初始条件 树T存在 操作结果 若T为空树 则返回TRUE 否则FALSE 6 3 1树和森林的定义 树的基本操作定义 2 TreeDepth T 初始条件 树T存在 操作结果 返回T的深度 Parent T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 若cur e是T的非根结点 则返回它的双亲 否则函数值为 空 LeftChild T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 若cur e是T的非叶子结点 则返回它的最左孩子 否则返回 空 RightSibling T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 若cur e有右兄弟 则返回它的右兄弟 否则函数值为 空 6 3 1树和森林的定义 树的基本操作定义 3 InsertChild T p i 初始条件 树T存在 p指向T中某个结点 1 i p所指结点的度 1 非空树C与T不相交 操作结果 插入C为T中p所指结点的第I棵子树 DeleteChild T p i 初始条件 树T存在 p指向T中某个结点 1 i p所指结点的度 操作结果 删除T中p所指结点的第I棵子树 TraverseTree T 初始条件 树T存在操作结果 按某种次序对T的每个结点进行一次且至多一次访问 6 3 2树与森林的存储结构 6 3 2 1双亲表示法constintMAX TREE SIZE100 typedefstructPTNode elemtypedata intparent PTNode typedefstruct PTNodenodes MAX TREE SIZE intr n PTree 6 3 2树与森林的存储结构 6 3 2 2孩子链表表示法typedefstructCTNode intchild structCTNode next ChildPtr typedefstruct Elemdata ChildPtrfirstchild CTBox typedefstruct CTBoxnodes MAX TREE SIZE intn r CTree 6 3 2 3孩子兄弟表示法typedefstructCSNode Elemdata structCSNode firstchild nextSibling CSNode CSTree 6 3 3树 森林与二叉树的转换 6 3 3 1树与二叉树的转换将树转换为二叉树 关键是把n个分支变为两个分支 步骤如下 1 保留所有结点与其左子结点的链接 2 打断所有结点原本与右结点的链接 3 连结所有兄弟结点 拥有同一个父结点的子结点 4 将兄弟结点顺时针转45将二叉树转换为树 1 二叉树的根即为树的根 2 打断所有结点与其右结点的链接 3 二叉树的左子树为树的左子树 从根开始一直向右 遇到的右子树均依次作为树的子树 4 将兄弟结点逆时针转45 一般树转二叉树 1 保留所有结点与其左子结点的链接 2 打断所有结点原本与右结点的链接 3 连结所有兄弟结点 拥有同一个父结点的子结点 4 将兄弟结点顺时针转45 二叉树转一般树 1 二叉树的根即为树的根 2 打断所有结点与其右结点的链接 3 二叉树的左子树为树的左子树 从根开始一直向右 遇到的右子树均依次作为树的子树 4 将兄弟结点逆时针转45 6 3 3树 森林与二叉树的转换 6 3 3 2森林与二叉树的转换森林转化为二叉树假设森林F T1 T2 Tn 其中第一棵树T1由根结点ROOT T1 和子树森林 t11 t12 t1m 构成 则可按如下规则转换成一棵二叉树B LBT Node root RBT 若森林F为空集 则二叉树B为空树 否则 由森林中第一棵树的根结点ROOT T1 复制得到二叉树的根Node root 由森林中第一棵树的子树森林 t11 t12 t1m 转换得到二叉树中的左子树LBT 由森林中删去第一棵树之后的由其余树构成的森林 T2 T3 Tn 转换得到二叉树中的右子树RBT 步骤如下 1 先将森林中的每一棵子树转化为二叉树 2 从第二棵树开始依次将第i棵树作为第i 1棵树的右子树 森林转化为二叉树 6 3 3树 森林与二叉树的转换 6 3 3 2森林与二叉树的转换二叉树转化为森林对于任意一棵二叉树B LBT Node root RBT 可按如下规则转换得到由棵子树构成的森林F T1 T2 Tn 其中第一棵树T1由根结点ROOT T1 和子树森林 t11 t12 t1m 构成 若二叉树B为空树 则与其对应的森林F为空集 否则 由二叉树的根结点Node root 复制得到森林中第一棵树的根结点ROOT T1 由二叉树中的左子树LBT转换构造森林中第一棵树的子树森林 t11 t12 t1m 由二叉树中的右子树RBT转换构造森林中其余树构成的森林 T2 T3 Tn 步骤如下 1 二叉树的根即为森林中第一棵树的根 2 从二叉树的根开始向右 遇到右子树 剪断其连接 使根及其左子树 成为第一棵树 如此往复处理其右子树 3 将每棵二叉树转换为树 二叉树转化为森林 6 3 3树 森林与二叉树的转换 森林与二叉树的对应关系示例 6 3 3树 森林与二叉树的转换 总结树和森林进行的各种操作均可通过对 二叉树 进行相应的操作来完成 但要注意 此时的二叉树其左 右子树和根结点之间的关系不再是 左 右孩子 而是左子树是根的 孩子们 右子树是根的 兄弟们 6 3 4树与森林的遍历 6 3 4 1树的遍历先根 次序 遍历树 若树不空 则先访问树的根结点 然后依次先根遍历根的各棵子树 后根 次序 遍历树 若树不空 则先依次后根遍历根的各棵子树 然后访问树的根结点 按层 次序 遍历树 若树不空 则从树的根结点起 依结点所在层次从小到大 每一层从左到右依次访问各个结点 6 3 4树与森林的遍历 先根 ABCDE 后根 BCEDA 6 3 4树与森林的遍历 6 3 3 2森林的遍历先序遍历森林若森林非空 则 1 访问森林中第一棵树的根结点 2 先序遍历第一棵树中根结点的子树森林 3 先序遍历除去第一棵树之后剩余的树构成的森林 中序遍历森林若森林非空 则 1 中序遍历森林中第一棵树的根结点的子树森林 2 访问第一棵树的根结点 3 中序遍历除去第一棵树之后的森林 6 3 4树与森林的遍历 先序 ABCDEFGHI 中序 BCDAFEHJIG 6 3 4树与森林的遍历 小结树和森林进行的各种操作均可通过对 二叉树 进行相应的操作来完成 但要注意 此时的二叉树其左 右子树和根结点之间的关系不再是 左 右孩子 而是左子树是根的 孩子们 右子树是根的 兄弟们 当森林转化成二叉树时 其第一棵树的子树森林转化成左子树 剩余树的森林转换成右子树 则森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历 当二叉树以链表形式存储时 树的先根遍历和后根遍历可借用二叉树的先序和中序遍历的算法实现 6 3 4树与森林的遍历 例6 5求森林的深度深度 森林 MAX 左分支森林的深度 1 右分支森林的深度 intTreeDepth CSTreeT if T return0 else h1 TreeDepth T firstchild h2 TreeDepth T nextsibling return max h1 1 h2 TreeDepth 6 3 4树与森林的遍历 例6 6输出树中从根结点到所有各个叶子结点的路径假设以孩子 兄弟链表做树的存储结构 则树就相当于二叉树 可利用 先序遍历 RABRADCRADERGHRGFRGJK R A B D C E G H F J K 父子关系 兄弟关系 叶结点 非叶结点 6 3 4树与森林的遍历 算法6 12 a voidOutPath CSTreeT Stack 继续遍历右子树求其它叶结点路径 while OutPath 6 3 4树与森林的遍历 例6 6输出树中从根结点到所有各个叶子结点的路径对于具体问题还要视情况而变 cn com edu tsinghua www ftp pku www telnet bjpu www ftp gov net 6 3 4树与森林的遍历 算法6 12 b voidOutPath CSTreeT Stack 继续遍历右子树求其它路径 while OutPath 6 3 4树与森林的遍历 例6 6建立树的存储结构 孩子 兄弟链表 A A B A C A D C E D F D G E H voidCreateTree CSTree 链接其它孩子结点 else for CreateTree 6 3 4树与森林的遍历 6 4树的应用 6 4 1堆排序的实现6 4 2二叉排序树6 4 3赫夫曼树及其应用 6 4 1堆排序的实现 堆 heapsort 是对选择排序的一种改进方法堆的定义 堆是满足下列性质的数列 若上述数列是堆 则r1必是数列中的最小值或最大值 则分别称为小顶堆或大顶堆 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法 具体做法为 先按记录的关键字建一个 大顶堆 因此选得一个关键字为最大的记录 然后与序列中的最后一个元素交换 之后继续对前n 1个记录进行 筛选 重新将它调整为一个 大顶堆 再将堆顶记录和第n 1个记录交换 这样有序性逐渐从右部向左扩大 如此反复直至排序结束 6 4 1堆排序的实现 可以将堆描述为完全二叉树 根结点为最小值或最大值 假设 r1 r2 rn 是堆 称r1为堆顶元素 称rn为堆顶元素 堆排序的核心问题是如何将树调整为堆 父结点 Vi子结点 V2i 左 V2i 1 右 2 将此二叉树建成最大堆 1 将n个数存入数组 3 交换堆顶与堆底 将剩下的树调整成堆 4 重复 3 直到所有值均以输出 6 4 1堆排序的实现 n 8 n 2 4 6 4 1堆排序的实现 1 考虑n4 sc nj sc覆盖ns s 4 sc ns j s 2 6 4 1堆排序的实现 2 考虑n3 sc nj nj覆盖ns s j j 2 越界 sc覆盖ns s 3 sc ns j s 2 1 6 4 1堆排序的实现 3 考虑n2 sc nj sc覆盖ns s 2 sc ns j s 2 6 4 1堆排序的实现 4 考虑n1 sc nj nj覆盖ns sc nj nj覆盖ns sc nj sc覆盖ns s j j s 2 s j j s 2 s 1 sc ns j s 2 最大堆 6 4 1堆排序的实现 取出树根 与最后一个结点交换 n1n8 n1 n7成堆 6 4 1堆排序的实现 n1n7 n1 n6成堆 6 4 1堆排序的实现 n1n6 n1 n5成堆 6 4 1堆排序的实现 n1n5 n1 n4成堆 6 4 1堆排序的实现 n1n4 n1 n3成堆 6 4 1堆排序的实现 n1n3 n1 n2成堆 6 4 1堆排序的实现 n1n2 堆排序算法 算法6 14 6 15 typedefSqTableHeapType voidHeapAdjust HeapType 将堆顶记录和堆底交换 for HeapSort 6 4 1堆排序的实现 时间复杂度 O nlogn 空间复杂度 O 1 优点 最坏情况下时间复杂度也仅为O nlogn 缺点 运行时间主要耗费在建初始堆和调整堆上 排序数据较少时 不值得提倡 3 7二叉树排序法 二叉排序树 binarysorttree 或者是一棵空树 或者是具有以下特性的二叉树 若它的左子树不空 则左子树上所有结点的值均小于根结点的值 若它的右子树不空 则右子树上所有结点的值均不小于根结点的值 它的左右子树也都是二叉排序树 中序遍历即为有序 6 4 2二叉排序树 算法6 17voidBSTSort SqList 6 4 2二叉排序树 算法6 16typedefRcdTypeTElemType voidInsert BST BiTree 插入为f所指结点的右子树根 else Insert BST 6 4 2二叉排序树 算法6 17voidBSTSort SqList 6 4 2二叉排序树 时间复杂度 受高度影响 为O n h 当为平衡树时h log2n空间复杂度 O n 优点 以插入的方式进行排序 方法简单 缺点 在插入结点时 第一个元素必为树根 若该值在数列中偏大或偏小 则会使树的歪斜程度加大 从而影响排序速度 稳定性 由排序条件决定左结点 parent 右结点 稳定排序左结点 parent 右结点 不稳定排序 6 4 3赫夫曼树及其应用 赫夫曼树 H