数据结构第5章树与二叉树.ppt

1 第5章树和二叉树 Tree BinaryTree 特点 非线性结构 一个直接前驱 但可能有多个直接后继 一对多或1 n 5 1树的概述 5 2二叉树定义和性质 5 3遍历二叉树 5 4线索二叉树 5 5树和森林 5 6哈夫曼及其应用 2 5 1树的基本概念 1 树的定义2 若干术语3 逻辑结构4 存储结构5 树的运算 3 1 树的定义 注1 树的定义具有递归性 即 树中还有树 由一个或多个 n 0 结点组成的有限集合T 有且仅有一个结点称为根 root 当n 1时 其余的结点分为m m 0 个互不相交的有限集合T1 T2 Tm 每个集合本身又是棵树 被称作这个根的子树 4 树的表示法主要有5种 图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子 右兄弟表示法 5 图形表示法 华科大武昌分校 叶子 根 子树 6 嵌套集合表示法 7 广义表表示法 A B E K L F C G D H M I J 根作为由子树森林组成的表的名字写在表的左边 麻烦问题 应当开设多少个链域 8 凹入表示法 又称目录表示法 9 左孩子 右兄弟表示法 10 2 若干术语 即树的数据元素 结点挂接的子树数 结点结点的度结点的层次终端结点分支结点 树的度树的深度 或高度 从根到该结点的层数 根结点算第一层 即度为0的结点 即叶子 即度不为0的结点 也称为非终端结点 所有结点度中的最大值 Max 各结点的度 指所有结点中最大的层数 Max 各结点的层次 问 右上图中的结点数 树的度 树的深度 13 3 4 有几个直接后继就是几度 亦称 次数 11 3 树的逻辑结构 一对多 1 n 有多个直接后继 如家谱树 目录树等等 但只有一个根结点 且子树之间互不相交 4 树的存储结构 讨论1 树是非线性结构 该怎样存储 特点 仍然有顺序存储 链式存储等方式 12 5 2二叉树 为何要重点研究每结点最多只有两个 叉 的树 二叉树的结构最简单 规律性最强 可以证明 所有树都能转为唯一对应的二叉树 不失一般性 1 二叉树的定义2 二叉树的性质3 二叉树的存储结构 二叉树的运算见5 3节 13 1 二叉树的定义 定义 是n n 0 个结点的有限集合 由一个根结点以及两棵互不相交的 分别称为左子树和右子树的二叉树组成 逻辑结构 一对二 1 2 基本特征 每个结点最多只有两棵子树 不存在度大于2的结点 左子树和右子树次序不能颠倒 问 具有3个结点的二叉树可能有几种不同形态 有5种 基本形态 一般的树有几种 14 2 二叉树的性质 3 2 讨论1 第i层的结点数最多是多少 利用二进制性质可轻松求出 性质1 在二叉树的第i层上至多有2i 1个结点 i 0 性质2 深度为k的二叉树至多有2k 1个结点 k 0 再提问 第i层上至少有个结点 1 讨论2 深度为k的二叉树 最多有多少个结点 利用二进制性质可轻松求出 2i 1个 2k 1个 15 讨论3 二叉树的叶子数和度为2的结点数之间有关系吗 性质3 对于任何一棵二叉树 若2度的结点数有n2个 则叶子数 n0 必定为n2 1 即n0 n2 1 证明 二叉树中全部结点数n n0 n1 n2 叶子数 1度结点数 2度结点数 又 二叉树中全部结点数n B 1 总分支数 根结点 除根结点外 每个结点必有一个直接前趋 即一个分支 而总分支数B n1 2n2 1度结点必有1个直接后继 2度结点必有2个 三式联立可得 n0 n1 n2 n1 2n2 1 即n0 n2 1 物理意义 叶子数 2度结点数 1 16 2 深度为 的二叉树的结点总数 最多为个 k 1 log2k k k 1 树 中各结点的度的最大值称为树 的 高度 层次 深度 度 D C C 3 深度为9的二叉树中至少有个结点 9 8 9 1 课堂练习 17 满二叉树 一棵深度为k且有2k 1个结点的二叉树 特点 每层都 充满 了结点 完全二叉树 深度为k的 有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应 为何要研究这两种特殊形式 完全二叉树的特点是只有最后一层叶子不满 且全部集中在左边 但这其实是顺序二叉树的含义 而图论中的 完全二叉树 是指n1 0的情况 因为它们在顺序存储方式下可以复原 18 对于两种特殊形式的二叉树 满二叉树和完全二叉树 还特别具备以下2个性质 性质4 具有n个结点的完全二叉树的深度必为 log2n 1 性质5 对完全二叉树 若从上至下 从左至右编号 则编号为i的结点 其左孩子编号必为2i 其右孩子编号为2i 1 其双亲的编号必为i 2 i 1时为根 除外 证明 根据性质2 深度为k的二叉树最多只有2k 1个结点 且完全二叉树的定义是与同深度的满二叉树前面编号相同 即它的总结点数n位于k层和k 1层满二叉树容量之间 即2k 1 1 n 2k 1或2k 1 n 2k三边同时取对数 于是有 k 1 log2n k因为k是整数 所以k log2n 1 可根据归纳法证明 19 5 2 3二叉树的存储结构 一 顺序存储结构按二叉树的结点 自上而下 从左至右 编号 用一组连续的存储单元存储 ABCDEFGHI 问 顺序存储后能否复原成唯一对应的二叉树形状 答 若是完全 满二叉树则可以做到唯一复原 而且有规律 下标值为i的双亲 其左孩子的下标值必为2i 其右孩子的下标值必为2i 1 即性质5 例如 对应 2 的两个孩子必为 4 和 5 即B的左孩子必是D 右孩子必为E T 0 一般不用 20 讨论 不是完全二叉树怎么办 答 一律转为完全二叉树 方法很简单 将各层空缺处统统补上 虚结点 其内容为空 AB C D E 缺点 浪费空间 插入 删除不便 21 二 链式存储结构用二叉链表即可方便表示 二叉树结点数据类型定义 typedefstructnode tree pointer typedefstructnode intdata tree pointerleft child right child node 一般从根结点开始存储 相应地 访问树中结点时也只能从根开始 注 如果需要倒查某结点的双亲 可以再增加一个双亲域 直接前趋 指针 将二叉链表变成三叉链表 22 例 23 5 3遍历二叉树 一 遍历二叉树 TraversingBinaryTree 遍历定义 遍历用途 遍历方法 指按某条搜索路线遍访每个结点且不重复 又称周游 它是树结构插入 删除 修改 查找和排序运算的前提 是二叉树一切运算的基础和核心 对每个结点的查看通常都是 先左后右 24 遍历规则 二叉树由根 左子树 右子树构成 定义为D L R 以根结点为参照系 注 先 中 后 的意思是指访问的结点D是先于子树出现还是后于子树出现 D L R的组合定义了六种可能的遍历方案 LDR LRD DLR DRL RDL RLD若限定先左后右 则有三种实现方案 DLRLDRLRD先根遍历中根遍历后根遍历 25 例1 先根遍历的结果是 中根遍历的结果是 后根遍历的结果是 DBEACDEBCA 口诀 DLR 先根遍历 即先根再左再右LDR 中根遍历 即先左再根再右LRD 后根遍历 即先左再右再根 A B D E C 26 先根遍历结果 ABCDE 前缀表示法中根遍历结果A B C D E 中缀表示法后根遍历结果AB C D E 后缀表示法层次遍历结果 E D CAB 例2 用二叉树表示算术表达式 27 遍历的算法实现 typedefstructnode tree pointer typedefstructnode intdata tree pointerleft child right child node 回忆2 递归函数 longintfact n 求n intn longf if n 1 f n fact n 1 elsef 1 return f 用递归形式格外简单 回忆1 二叉树结点的数据类型定义 则三种遍历算法可写出 28 中根遍历算法LDR node root if root NULL LDR root lchild printf d root data LDR root rchild return 0 后根遍历算法LRD node root if root NULL LRD root lchild LRD root rchild printf d root data return 0 结点数据类型自定义typedefstructnode intdata structnode lchild rchild node node root 先根遍历算法DLR node root if root NULL 非空二叉树 printf d root data 访问DDLR root lchild 递归遍历左子树DLR root rchild 递归遍历右子树 return 0 29 对遍历的分析 1 从前面的三种遍历算法可以知道 如果将print语句抹去 从递归的角度看 这三种算法是完全相同的 或者说这三种遍历算法的访问路径是相同的 只是访问结点的时机不同 从虚线的出发点到终点的路径上 每个结点经过3次 第1次经过时访问 是先根遍历第2次经过时访问 是中根遍历第3次经过时访问 是后根遍历 2 二叉树遍历的时间效率和空间效率时间效率 O n 每个结点只访问一次空间效率 O n 栈占用的最大辅助空间 精确值 树深为k的递归遍历需要k 1个辅助单元 30 用空格字符表示 无孩子 或指针为空 注 要实现遍历运算 必须先把二叉树存入电脑内 怎样建树 例 将下面的二叉树以二叉链表形式存入计算机内 考虑1 输入结点时怎样表示 无孩子 考虑2 以何种遍历方式来输入和建树 将二叉树按先序遍历次序输入 ABC DE G F 以先序遍历最为合适 让每个结点都能及时被连接到位 31 建树算法 StatusCreateBiTree BiTree CreateBiTree 输入序列 ABC DE G F 32 问 用二叉链表法 l child r child 存储包含n个结点的二叉树 结点的指针区域中会有多少个空指针 思考 二叉链表空间效率这么低 能否利用这些空闲区存放有用的信息或线索 我们可以用它来存放当前结点的直接前驱和后继等线索 以加快查找速度 所以 空指针数目 2n n 1 n 1个 n 1个 分析 用二叉链表存储包含n个结点的二叉树 结点必有2n个链域 见二叉链表数据类型说明 除根结点外 二叉树中每一个结点有且仅有一个双亲 直接前驱 所以只会有n 1个结点的链域存放指针 指向非空子女结点 即直接后继 线索二叉树 33 思考 二叉链表空间效率这么低 能否利用这些空闲区存放有用的信息或线索 我们可以用它来存放当前结点的直接前驱和后继等线索 以加快查找速度 用二叉链表法存储包含n个结点的二叉树 结点的指针区域中会有n 1个空指针 这就是线索二叉树 ThreadedBinaryTree 34 5 4线索二叉树 ThreadedBinaryTree 二叉树中容易找到结点的左右孩子信息 但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得 先依遍历规则把每个结点对应的前驱和后继线索预存起来 这叫做 线索化 意义 从任一结点出发都能快速找到其前驱和后继 且不必借助堆栈 对二叉树进行某种遍历之后 将得到一个线性有序的序列 例如对某二叉树的中序遍历结果是BDCEAFHG 意味着已将该树转为线性排列 显然其中结点具有唯一前驱和唯一后继 在此前提下 那n 1个空链域才可能装得下 线索 讨论1 二叉树是1 2的非线性结构 其直接后继可能不止一个 如何存放 讨论2 如何获得这种 直接前驱 或 直接后继 有何意义 35 每个结点增加两个域 fwd和bwd 存放前驱指针 存放后继指针 如何预存这类信息 有两种解决方法 与原有的左右孩子指针域 复用 充分利用那n 1个空链域 规定 1 若结点有左子树 则lchild指向其左孩子 否则 lchild指向其直接前驱 即线索 2 若结点有右子树 则rchild指向其右孩子 否则 rchild指向其直接后继 即线索 缺点 空间效率太低 问题 计算机如何判断是孩子指针还是线索指针 如何区别 36 约定 当Tag域为0时 表示正常情况 当Tag域为1时 表示线索情况 前驱 后继 左 右 孩子 为区别两种不同情况 特增加两个标志域 问 增加了前驱和后继等线索有什么好处 能方便找出当前结点的前驱和后继 不用堆栈 递归 也能遍历整个树 37 1 有关线索二叉树的几个术语 线索链表 线索 线索二叉树 线索化 用含Tag的结点样式所构成的二叉链表指向结点前驱和后继的指针加上线索的二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程 yyy 线索化过程就是在遍历过程中修改空指针的过程 将空的lchild改为结点的直接前驱 将空的rchild改为结点的直接后继 非空指针呢 仍然指向孩子结点 称为 正常情况 38 A G E I D J H C F B 例 带了两个标志的某先序遍历结果如下表所示 请画出对应的二叉树 A 39 悬空 NIL 悬空 NIL 解 对该二叉树中序遍历的结果为 H D I B E A F C G所以添加线索应当按如下路径进行 为避免悬空态 应增设一个头结点 例1 画出以下二叉树对应的中序线索二叉树 2 线索二叉树的生成 线索化 线索化过程就是在遍历过程中修改空指针的过程 40 注 此图中序遍历结果为 H D I B E A F C G 对应的中序线索二叉树存储结构如图所示 41 线索二叉树的生成算法 递归算法见教材 实质 在遍历二叉树的过程中修改空指针 添加前驱或后继的线索 使之成为线索二叉树 为了记下遍历过程中访问结点的先后次序 需要设置两个指针 p指针 当前结点之指针 pre指针 当前结点的前趋结点指针 设计技巧 依某种顺序遍历二叉树 对每个结点p 判断其左指针是否为空 以及其前驱结点的右指针是否为空 每次只修改前驱结点的右指针 后继 和本结点的左指针 前驱 参见算法 若p lchild NULL 则 p Ltag 1 p lchild pre p的前驱线索应存p结点的左边若pre rchild NULL 则 pre Rtag 1 pre rchild p pre的后继线索应存pre结点的右边 42 3 线索二叉树的遍历 无需堆栈 对于线索二叉树的遍历 只要找到序列中的第一个结点 然后依次访问结点的后继直到后继为空为止 因为建立线索时已遍历一次 相当于线性化了 难点 在线索化二叉树中 并不是每个结点都能直接找到其后继的 当标志为0时 则需要通过一定运算才能找到它的后继 以中根线索二叉树为例 当RTag 1时 直接后继指针就在其rchild域内 当RTag 0时 直接后继是当前结点右子树最左下方的结点 请注意中序遍历规则是LDR 先左再根再右 43 5 5树和森林 1 树和森林的存储方式2 树和森林与二叉树的转换3 树和森林的遍历 44 1 树和森林的存储方式 树有三种常用存储方式 双亲表示法 孩子表示法 孩子 兄弟表示法 1 用双亲表示法存储 思路 用一组连续空间来存储树的结点 同时在每个结点中附设一个指示器 指示其双亲结点在链表中的位置 45 1 0 0 0 例1 双亲表示法 缺点 求结点的孩子时需要遍历整个结构 113666 46 思路 对n个结点分别设立n个孩子链表 结点为表头 再将n个表头用数组存放起来 形成一个混合结构 例如 2 用孩子表示法存储 47 思路 用二叉链表来表示树 但链表中的两个指针域含义不同 左指针指向该结点的第一个孩子 右指针指向该结点的下一个兄弟结点 3 用孩子 兄弟表示法存储 指向左孩子 指向右兄弟 48 问 树 二叉树的 连线 抹线 旋转 如何由计算机自动实现 答 用 左孩子右兄弟 表示法来存储即可 例如 49 2 树和森林与二叉树的转换 转换步骤 step1 将树中同一结点的兄弟相连 加线 抹线 旋转 讨论1 树如何转为二叉树 孩子 兄弟表示法 step2 保留结点的最左孩子连线 删除其它孩子连线 step3 将同一孩子的连线绕左孩子旋转45度角 50 方法 加线 抹线 旋转 树转二叉树举例 兄弟相连 长兄为父 孩子靠左 根结点肯定没有右孩子 51 讨论2 二叉树怎样还原为树 要点 逆操作 把所有右孩子变为兄弟 52 法一 各森林先各自转为二叉树 依次连到前一个二叉树的右子树上 讨论3 森林如何转为二叉树 法二 森林直接变兄弟 再转为二叉树 参见教材 两种方法都有转换示意图 法一和法二得到的二叉树是完全相同的 惟一的 53 森林转二叉树举例 采用法二 兄弟相连长兄为父头树为根孩子靠左 A 54 讨论4 二叉树如何还原为森林 要点 把最右边的子树变为森林 其余右子树变为兄弟 55 5 6Huffman树及其应用 一 Huffman树二 Huffman编码 最优二叉树 Huffman树 Huffman编码 带权路径长度最短的树 不等长编码 是通信中最经典的压缩编码 56 一 最优二叉树 Huffman树 路径 路径长度 树的路径长度 带权路径长度 树的带权路径长度 Huffman树 由一结点到另一结点间的分支所构成 路径上的分支数目 从树根到每一结点的路径长度之和 结点到根的路径长度与结点上权的乘积 WPL 若干术语 树中所有叶子结点的带权路径长度之和 带权路径长度最小的树 a e的路径长度 树长度 2 10 Huffman常译为赫夫曼 霍夫曼 哈夫曼等 WeightedPathLength 57 树的带权路径长度如何计算 经典之例 WPL WPL WPL Huffman树是WPL最小的树 树中所有叶子结点的带权路径长度之和 36 46 35 58 1 构造Huffman树的基本思想 例 设有4个字符d i a n 出现的频度分别为7 5 2 4 怎样编码才能使它们组成的报文在网络中传得最快 法1 等长编码 如二进制编码 令d 00 i 01 a 10 n 11 则 WPL1 2bit 7 5 2 4 36法2 不等长编码 如Huffman编码 令d 0 i 10 a 110 n 111 则 明确 要实现Huffman编码 就要先构造Huffman树 讨论 Huffman树有什么用 权值大的结点用短路径 权值小的结点用长路径 WPL最小的树 频度高的信息用短码 反之用长码 传输效率肯定高 信息高效传输 WPL2 1bit 7 2bit 5 3bit 2 4 35 59 2 构造Huffman树的步骤 即Huffman算法 1 由给定的n个权值 w1 w2 wn 构成n棵二叉树的集合F T1 T2 Tn 即森林 其中每棵二叉树Ti中只有一个带权为wi的根结点 其左右子树均空 2 在F中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树 且让新二叉树根结点的权值等于其左右子树的根结点权值之和 3 在F中删去这两棵树 同时将新得到的二叉树加入F中 4 重复 2 和 3 直到F只含一棵树为止 这棵树便是Huffman树 怎样证明它就是WPL最小的最优二叉树 参考 信源编码 60 step1 对权值进行合并 删除与替换 在权值集合 7 5 2 4 中 总是合并当前值最小的两个权 具体操作步骤 a 初始 方框表示外结点 叶子 字符 圆框表示内结点 合并后的权值 b 合并 2 4 c 合并 5 6 d 合并 7 11 61 step2 按左 0 右 1 对Huffman树的所有分支编号 Huffman编码结果 d 0 i 10 a 110 n 111WPL 1bit 7 2bit 5 3bit 2 4 35 小于等长码的WPL 36 特征 每一码不会是另一码的前缀 译码时惟一 不会错 Huffman编码也称为前缀码 将Huffman树与Huffman编码挂钩 62 二 Huffman编码 由于哈夫曼树的WPL最小 说明编码所需要的比特数最少 这种编码已广泛应用于网络通信中 解 先将概率放大100倍 以方便构造哈夫曼树 放大后的权值集合w 7 19 2 6 32 3 21 10 按哈夫曼树构造规则 合并 删除 替换 可得到哈夫曼树 例1 假设用于通信的电文仅由8个字母 a b c d e f g h 构成 它们在电文中出现的概率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 试为这8个字母设计哈夫曼编码 如果用0 7的二进制编码方案又如何 哈夫曼编码的基本思想是 出现概率大的信息用短码 概率小的用长码 63 w 7 19 2 6 32 3 21 10 在机内存储形式为 b c a d e g f h 请注意 哈夫曼树样式不惟一 5 11 17 28 40 60 100 64 对应的哈夫曼编码 Huffman码的WPL 2 0 19 0 32 0 21 4 0 07 0 06 0 10 5 0 02 0 03 1 44 0 92 0 25 2 61 3 0 19 0 32 0 21 0 07 0 06 0 10 0 02 0 03 3 二进制等长码的WPL 65 本章小结 1 定义和性质 2 存储结构 3 遍历 4 线索化 1 2 性质有3 2条 孩子 兄弟 线索树 66 第五章树和二叉树 结束