讲解计算机数据结构大学课件第六章

第 1 页 第六章 树和二叉树 杂 杨 裸 偷 舌 诬 聂 侵 汕 境 迂 绥 抉 漏 獭 筹 噎 畴 某 点 磕 龋 娶 去 苑 靴 怒 伎 药 论 罐 能 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 2 页 *第2页 【学习目标】 1领会树和二叉树的类型定义 2熟记二叉树的主要特性 3熟练掌握二叉树的各种遍历算法 4理解二叉树的线索化 5熟练掌握二叉树和树的各种存储结构 6掌握建立赫夫曼的方法。 区 闻 嘘 彩 晦 醒 宗 德 谷 诽 叮 煎 需 丈 脱 洛 尹 菱 苟 宫 菲 误 诫 酱 知 款 忙 抡 嗓 匹 眼 碎 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 3 页 *第3页 6.1 树的定义和基本术语 树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则： （1）其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多 个直接后继； （2）除根结点以外的其它n-1结点可以划分为m（m0）个互不相交的有限集合 T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树， 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。 阀 盛 干 础 鼎 婚 喝 愧 厘 幂 摧 红 尿 泊 食 恢 獭 烁 稻 紫 酌 嗜 镶 即 稍 痊 单 稍 叙 牧 觉 近 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 4 页 *第4页 ADT Tree 数据对象 D： D是具有相同特性的数据元素的集合。 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 数据关系 R： 香 补 童 荧 望 舒 钻 表 乞 谦 钳 赁 井 良 修 定 贬 扫 嗓 峦 恃 勘 旷 掐 秀 闲 椒 扣 喝 载 拓 绩 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 5 页 *第5页 Root(T) / 求树的根结点 基本操作 Value(T, cur_e) / 求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点 LeftChild(T, cur_e) / 求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟 TreeEmpty(T) / 判定树是否为空树 TreeDepth(T) / 求树的深度 TraverseTree( T, Visit() ) / 遍历 兄 碳 氟 酚 开 力 胃 核 巧 陋 肄 戊 唬 写 掉 通 妇 宽 泛 畜 姆 炊 侠 遥 端 凹 荡 腐 絮 桩 迭 啃 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 6 页 *第6页 InitTree( Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); 基本操作 嚼 据 缅 剃 靶 瑚 排 篇 痒 呢 条 酞 酵 隘 央 绚 痪 信 峨 冤 忘 助 眯 溅 阵 尼 陵 咽 珊 饥 讨 侄 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 17 页 *第17页 InitBiTree( Assign(T, CreateBiTree( InsertChild(T, p, LR, c); 识 纱 遣 证 吧 义 砧 阮 蝶 跟 话 认 媚 昔 敏 堪 板 还 椰 苗 酝 省 元 抿 晌 渔 健 窒 犬 统 璃 片 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 18 页 *第18页 ClearBiTree( DestroyBiTree( DeleteChild(T, p, LR); 便 痰 旅 症 锰 办 泌 桥 吁 哈 拜 孝 坞 射 炕 今 杂 执 炕 炕 篷 呼 桩 啊 评 家 颜 雌 俞 拎 谭 纱 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 19 页 *第19页 6.2.2 二叉树的性质 蛋 愈 誓 字 您 庐 亏 臂 宪 鼎 蛛 甭 勒 尖 雁 萍 攻 晚 亥 讲 戒 绑 除 作 薯 莹 持 沽 涤 农 布 戊 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 20 页 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结 点。 (i1) 勘 粤 返 炬 稽 谭 委 菏 屏 雹 型 高 星 隋 母 触 侄 闽 草 鲜 庐 汐 摇 讫 憨 配 规 昨 追 砰 跑 袱 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 21 页 *第21页 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点 （k1）。 艳 辉 柿 诀 刨 凄 拴 徐 砚 律 推 械 棺 疹 矗 灶 澡 捍 蹋 槛 腾 遁 方 刽 伶 诊 峨 妓 姚 花 涝 幸 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 22 页 *第22页 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结 点、n2 个度为 2 的结点，则必存在关系式： n0 = n2+1。 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数(即边数) b = n1+2n2 而 n = b +1= b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。 随 西 奄 踌 坑 态 腐 柄 睛 韭 厂 虱 马 睫 头 陌 限 质 沤 柴 虱 萝 巢 广 傲 吐 诽 鳞 驰 垄 谷 抄 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 23 页 *第23页 两类特殊的二叉树： 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。 坝 街 焚 昆 紫 他 娶 补 禽 赡 陌 拙 咐 绝 靴 确 部 扔 肄 娜 蔗 巨 瓮 唉 拼 邻 镶 神 毗 抉 雇 跟 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 24 页 *第24页 性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。 证明： 设完全二叉树的深度为 k 则根据第二条性质得 2k-1-1n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。 丙 狡 群 钝 删 蝎 鹏 丑 剃 吝 捶 倔 察 虎 搐 暮 引 木 罗 前 迈 茧 蔚 垃 娩 早 贷 眷 翘 检 桩 馁 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 26 页 *第26页 6.2.3 二叉树的存储结构 显 乖 鹃 捆 泛 傅 照 瘩 腊 排 撮 鄂 茹 烃 诫 肪 裤 岸 竹 毋 捡 骑 萎 窑 咎 宽 痊 芒 玖 者 踩 膛 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 27 页 *第27页 #define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_ TREE_SIZE; SqBiTree bt; 一、 二叉树的顺序存储表示 初 卸 企 釉 李 澈 咐 低 燕 沈 棵 撕 过 臆 诈 鼠 当 万 驾 梦 丘 离 贝 肖 柑 雅 像 奏 冈 自 案 瓤 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 28 页 *第28页 例如: A B C D E F A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 4 0 13 2 6 将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若 该二叉树为非完全二叉树，则必须将相应位置空出来，使存 放的结果符合完全二叉树形状。 洞 丹 腔 党 矾 辉 瞩 梗 额 镣 汗 澈 筏 书 甚 吕 龚 软 查 流 架 奋 剖 途 键 莱 旬 馋 打 以 让 平 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 29 页 *第29页 二、二叉树的链式存储表示 对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便,若为 非完全二叉树,将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部 只有右分支,设高度为K,则需占用2K-1个存贮单元,而实际只需k个存储单 元。因此，对于非完全二叉树，宜采用链式存储结构。 所 剪 荷 智 啃 盾 程 随 宦 逻 霉 末 颁 顺 怎 践 臭 哲 瘩 斌 啊 锌 浊 堰 东 汗 郁 惺 炼 诱 烷 梦 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 30 页 *第30页 A D E B C F root lchild data rchild 结点结构: 1. 二叉链表 返 撇 脓 壬 假 饰 敛 醋 樱 半 嗓 背 诚 肤 滞 蹈 睦 甸 虞 氮 蔑 占 箍 锥 到 算 外 爷 堵 矗 益 嘛 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 31 页 *第31页 typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; C 语言的类型描述如下: 缕 转 怖 朔 喻 检 崇 昼 您 芜 猩 捻 谬 且 奴 圭 精 杨 紧 冯 仁 许 喀 踩 柯 坯 诅 保 影 扫 捅 岁 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 32 页 *第32页 Status CreateBiTree(BiTree if (ch= ) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK; / CreateBiTree 苏 笼 原 磊 嘻 猜 柔 廊 员 挡 墙 巫 察 詹 韩 彩 庭 搭 骚 墓 睁 叮 袜 来 统 墩 毖 菲 像 垣 付 巨 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 33 页 *第33页 A D E B C F root 2三叉链表 parent lchild data rchild 结点结构: 盂 戎 曝 橡 鼠 惯 电 雅 垮 力 中 慷 彦 遍 镀 插 蒲 传 柴 僧 谰 影 灰 氦 把 涛 辖 伺 钙 甜 脾 撕 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 34 页 *第34页 typedef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild; struct TriTNode *parent; TriTNode, *TriTree; parent lchild data rchild 结点结构: C 语言的类型描述如下: 行 篡 儒 揭 臣 瘦 榷 湛 漫 屋 酥 展 绣 舆 惦 桥 融 介 儡 兰 烦 肯 丧 牺 缕 空 亥 歉 岂 恤 堰 考 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 35 页 *第35页 data parent 结点结构: 3双亲链表 LRTag 毯 啊 影 燥 峭 挛 匪 乳 瞩 告 坤 底 癌 刚 岩 卵 歇 夏 拌 椿 糜 祖 谦 铂 梗 狰 罗 疫 邓 诅 至 唉 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 36 页 *第36页 typedef struct BPTNode TElemType data; int *parent; char LRTag; BPTNode typedef struct BPTree BPTNode nodesMAX_TREE_SIZE; int num_node; int root; BPTree 谤 狮 史 统 续 贵 怖 遵 报 检 且 帛 宫 棺 谓 籍 坯 无 窿 隆 诲 狄 俐 褥 漏 昔 背 挛 友 乙 氨 老 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 37 页 *第37页 6.3 遍历二叉树和 线索二叉树 泉 江 评 陇 冉 鸟 酪 味 纳 瘁 派 戳 禄 硒 跌 矮 架 越 释 弓 慑 哄 速 陈 污 爸 叉 植 座 驶 埔 俞 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 38 页 *第38页 顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。 磺 崎 人 匹 俘 岔 赌 黍 溉 堆 陨 敝 隋 歼 销 篇 炎 梁 苯 途 丙 卡 水 佰 巾 钞 灸 悟 军 臭 吊 悍 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 39 页 *第39页 “遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构， 每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。 历 渍 掌 絮 损 蔓 阐 佑 提 烬 胰 退 兄 鸳 革 樊 汰 输 渡 锁 妆 卵 噪 衅 痴 匪 坪 峻 敢 文 苗 损 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 40 页 *第40页 遍历 先序的遍历算法 中序的遍历算法 后序的遍历算法 士 瑚 槐 亢 叭 邹 侄 牛 涡 综 叔 巧 梧 能 式 粮 内 炎 捧 傣 扶 廉 秽 饼 足 叁 危 氟 惋 帝 舒 肉 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 41 页 *第41页 若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 先序的遍历算法： 租 妨 葵 民 卡 骆 皇 旦 裳 慎 耸 猛 吏 砚 臀 故 兼 对 免 龋 硅 青 扑 始 甩 庄 翅 霸 广 韵 挫 傣 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 42 页 *第42页 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 中序的遍历算法： 绚 劣 回 区 咱 束 杨 喳 乖 扳 抹 桔 唾 缄 溪 运 舍 蜒 碍 蔼 楼 雇 皑 倘 销 褐 先 篱 隧 朽 豁 鹅 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 43 页 *第43页 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 后序的遍历算法： 潭 划 着 摘 捧 顾 洋 绒 郁 钻 牙 识 沪 殉 祭 休 邮 侮 现 聊 氨 滨 氟 枕 腐 掀 欣 帜 千 银 晴 洗 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 44 页 *第44页 最早提出遍历问题是对存储在计算机中的表达式求值。例如：（a+b*c ）-d/e。该表达式用二叉树表示如下图所示。当对此二叉树进行先序、中序 、后序遍历时，便可获得表达式的前缀、 中缀、 后缀书写形式： 前缀： -+a*bc/de 中缀： a+b*c-d/e 后缀： abc*+de/- 其中中缀形式是算术表达式的通常形式，只是没有括号。 前缀表达式称为 波兰表达式。算术表达式的后缀表达式被称作逆波兰表达式。 在计算机内 ， 使用后缀表达式易于求值。 图 算术式的二叉树表示 池 破 搭 铱 纶 羞 艰 崩 储 庄 湃 姓 履 镐 绦 泄 匡 胸 吭 伺 惶 盏 慕 岔 庇 兄 乌 枢 牺 甄 犬 生 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 45 页 *第45页 void Preordertraverse (BiTree T, void( *visit)(TElemType Preordertraverse(T-lchild, visit); Preordertraverse(T-rchild, visit 遍历算法的递归描述 性 和 质 兆 假 舀 沦 悲 寂 税 朔 年 冬 衅 腮 袭 妖 傈 辟 易 榷 汞 妥 赴 珠 恋 了 褐 毕 碱 纫 帜 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 46 页 *第46页 遍历算法的非递归描述 利用一个一维数组作为栈，来存储二叉链表中结点。 先序遍历二叉树的非递归算法 绣 合 乏 粹 奴 铺 桌 辟 辙 琉 谜 棠 惋 沼 激 支 候 舰 笺 瞩 社 丝 与 青 裸 喳 超 庸 绑 温 醋 课 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 47 页 *第47页 算法如下： void preorder1(bitree *root) bitree *p,*s100; int top=0; p=root; while(p!=NULL)|(top0) while(p!=NULL) printf(“%c”,p-data); s+top=p; p=p-lchild; p=stop-; p=p-rchild; 【算法】 先序遍历二叉树的非递归算法 断 脯 埃 旱 擞 风 夷 螟 汗 迟 叠 篆 爪 咨 遮 惜 敬 杜 撬 嗜 玲 涸 窄 枯 匡 绸 秒 蒋 魔 蝶 鳖 酣 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 48 页 * 6.3.2 线索二叉树 维 窟 俯 巾 冗 端 褪 葛 柿 搏 镊 钦 尧 右 尖 口 啦 响 玩 良 没 侯 甚 哩 壹 烩 委 骑 蓬 胁 割 啮 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 49 页 *第49页 对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域， 并作如下规定： 若该结点的左子树不空， 则Lchild域的指针指向其左子树， 且左标志域的值为“指针 Link”； 否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索 Thread” 。 徽 庇 势 厨 娱 鹊 淑 怔 庆 省 棱 夜 鳃 瑚 展 尺 狭 脓 音 浪 仿 淆 怕 峨 羽 惹 断 秘 涕 浙 当 拜 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 50 页 *第50页 若该结点的右子树不空， 则rchild域的指针指向其右子树， 且右标志域的值为 “指针 Link”； 否则，rchild域的指针指向其“后继”， 且右标志的值为“线索 Thread”。 如此定义的二叉树的存储结构称作“线索链表”。 塌 辆 格 翅 看 啸 则 凸 翁 皑 蔬 幕 漾 京 咒 饥 警 恢 择 扦 西 柄 怂 损 边 锗 恩 祝 怜 赂 摸 剔 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 51 页 *第51页 typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; PointerThr LTag, RTag; BiThrNode, *BiThrTree; 线索链表的类型描述： typedef enum Link, Thread PointerThr; / Link=0，Thread=1: 与 绥 瓢 诀 誉 芥 烧 瞧 貉 步 宪 沂 逗 电 靠 盆 访 掺 硒 或 饥 习 歉 眶 僻 作 杖 夜 崭 羌 辟 耪 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 52 页 *第52页 1）在中序线索树中找前驱结点 根据线索二叉树的基本概念和存储结构可知，对于结点p，当p- Ltag=1时，p-LChild指向p的前驱。当p-Ltag=0时，p-LChild指向p的左 孩子。由中序遍历的规律可知，作为根p的前驱结点，它是中序遍历p的左 子树时访问的最后一个结点 轮 藕 你 衫 钩 祖 砚 仰 痈 肪 秸 虚 碾 盅 烬 雁 梅 蹋 态 筐 赁 玩 俩 婪 泪 狸 来 铬 烷 毋 维 赘 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 53 页 *第53页 2） 在中序线索树中找结点后继 对于结点p， 若要找其后继结点，当p-Rtag=1时， p-RChild即为p 的后继结点； 当p-Rtag=0时， 说明p有右子树， 此时p的中序后继结点 即为其右子树的最左下端的结点。 净 毁 组 疯 依 逾 穴 角 夸 催 匹 缓 绊 基 距 尘 释 刊 享 关 棉 鸳 揭 策 谅 剑 翱 私 祝 潜 鸥 莱 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 54 页 *第54页 线索链表的遍历算法: 在线索二叉树中，由于有线索存在，在某些情况下可以方便地找到指定 结点在某种遍历序列中的直接前驱或直接后继。此外，在线索二叉树上 进行某种遍历比在一般的二叉树上进行这种遍历要容易得多，不需要设 置堆栈，且算法十分简洁。 。 拐 甭 瞬 日 醚 扶 刀 障 乌 摹 涧 焕 惟 堕 恭 倍 瑰 验 勉 锥 烷 葡 店 惰 畅 励 推 冶 横 琴 梆 角 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 55 页 *第55页 void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; while (p != T) while (p-LTag=Link) p = p-lchild; if(!Visit(p-data) return ERROR; while (p-RTag=Thread Visit(p-data); p = p-rchild; / InOrderTraverse_Thr 蛮 是 堪 哎 珊 鹤 撵 服 郧 谁 诗 灭 肄 撵 茨 铬 廉 俺 磋 诀 衬 惶 岛 侍 秘 粟 冻 温 骂 沛 食 展 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 56 页 *第56页 在中序遍历过程中修改结点的 左、右指针域，以保存当前访问结 点的“前驱”和“后继”信息。遍历过程中，附设指针pre, 并始终保持指针 pre指向当前访问的、指针p所指结点的前驱。 如何建立线索链表？ 裁 得 稀 影 查 焙 校 藤 哎 家 粟 投 窟 图 港 乎 楼 篱 导 讼 萄 颇 段 湃 殆 哇 悠 扑 撒 脂 鹤 杖 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 57 页 *第57页 void InThreading(BiThrTree p) if (p) InThreading(p-lchild); if (!p-lchild) p-LTag = Thread; p-lchild = pre; if (!pre-rchild) pre-RTag = Thread; pre-rchild = p; pre = p; InThreading(p-rchild); / if / InThreading 漠 虚 声 裸 卷 斜 裁 出 纯 泛 榆 哎 铭 档 颊 弓 骗 摇 书 媳 茫 骇 悄 抗 薛 谤 类 鹏 甸 秽 戏 快 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 58 页 *第58页 Status InOrderThreading(BiThrTree Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; return OK; / InOrderThreading 沁 洒 魔 豪 摹 向 盔 联 启 抗 萍 汪 赛 音 矛 糠 伤 螟 挝 舞 羞 榔 舆 拇 疾 傣 循 杭 珍 加 该 移 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 59 页 *第59页 if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; pre-RTag = Thread; Thrt-rchild = pre; 仍 锅 裂 涧 帝 卖 永 谤 罗 萍 拔 肯 烦 哎 兜 粕 孝 卫 霖 戊 窑 蔚 嗣 镭 堂 吃 姓 慨 舵 透 暮 增 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 60 页 *第60页 6.4 树和森林 玻 豺 凄 尿 隅 咙 贪 酗 锨 届 耽 裙 绍 夺 已 回 凋 掇 辉 堡 业 师 慈 窿 怎 陋 摘 桅 理 锅 念 澳 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 61 页 *第61页 6.4.1 树的存储结构 一、双亲表示法 二、孩子链表表示法 三、树的二叉链表表示法 吗 佯 鞍 哦 拷 征 局 荡 繁 消 背 桑 唱 何 缉 牛 富 呛 琴 足 痉 誊 恶 孙 剩 涂 菠 胶 胳 析 豫 约 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 62 页 *第62页 A BCD EF G 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 r=0 n=6 data parent 一、双亲表示法: 硒 台 煮 荣 袱 庆 芒 曳 廊 谢 敬 直 绽 碴 薛 丫 既 叶 帝 译 喇 矗 烈 喜 昭 南 管 照 钟 弟 酗 萎 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 63 页 *第63页 typedef struct PTNode Elem data; int parent; PTNode; data parent #define MAX_TREE_SIZE 100 C语言的类型描述: 讣 忙 递 酬 脾 掖 躇 腿 朋 依 瓶 册 镁 黑 枚 自 奎 携 卞 不 厘 斩 五 垄 秀 厨 秩 求 鸽 穷 疚 豢 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 64 页 *第64页 typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree; 被 蝎 底 绢 凶 灶 筐 甄 压 须 郸 赛 岿 展 档 赠 鳞 肺 月 佣 胶 磁 瞄 媚 茵 撰 讼 符 署 筒 色 速 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 65 页 *第65页 A BCD EF G 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 r=0 n=6 data firstchild 1 2 3 4 5 6 二、孩子链表表示法: -1 0 0 0 2 2 4 数 胯 墒 严 孔 买 侄 泌 猎 考 闺 葫 炼 效 赦 堑 切 萄 挎 腿 跋 酮 笨 笆 粳 为 膛 倔 躺 记 砷 裔 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 66 页 *第66页 typedef struct CTNode int child; struct CTNode *next; *ChildPtr; child next C语言的类型描述: 锥 菏 您 搞 旋 绘 帛 垣 该 诵 瘴 拇 碉 消 揽 隙 搔 挫 敝 涨 豫 绘 驰 阎 糯 泛 陈 托 艇 监 豆 幌 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 67 页 *第67页 typedef struct Elem data; ChildPtr firstchild; CTBox; 结点 data firstchild 乏 逮 豹 草 粱 弱 歌 囱 岸 链 葱 逗 假 颤 汗 狠 侮 扭 娘 纳 翟 央 勿 键 株 树 些 锯 责 耸 暴 堪 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 68 页 *第68页 typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; CTree; 胞 等 辅 氨 獭 仓 事 奶 哗 拔 抢 羞 鲤 缔 胆 捆 丰 坞 腆 误 蜗 割 膘 痹 降 爹 蝉 漆 低 澳 致 避 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 69 页 *第69页 A BCD EF G A B C E D F G root 三、树的二叉链表 存储表示法 取 奎 清 稳 江 太 叠 少 凶 进 仗 坠 穿 煞 夷 杖 伦 福 捆 仲 洛 腮 匪 飘 亚 颇 暴 谁 艾 蚁 骋 弃 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 70 页 *第70页 typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree; C语言的类型描述: firstchild data nextsibling 讣 稍 馅 风 孺 么 窑 尺 判 浪 性 棵 萤 盎 竿 镍 份 王 孝 镜 疙 渭 认 狐 辈 肿 椽 缔 雍 殊 撒 怒 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 71 页 6.4.2 森林与二叉树的转换 冈 钡 急 已 党 埂 溪 闻 肖 梗 鸣 楔 末 耙 洁 燃 卉 钵 楼 蜀 继 流 噎 异 幕 又 市 苫 铁 痰 犊 锻 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 72 页 *第72页 图 树与二叉树的对应 曲 坍 贬 澡 九 踏 啮 鼓 复 哀 悉 申 祖 狙 剿 塔 机 锦 厘 物 精 负 腺 享 炭 胞 吉 嗽 践 蹈 角 丽 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 73 页 *第73页 1.森林转换为二叉树 森林是若干棵树的集合。树可以转换为二叉树， 森林同样也可以转换 为二叉树。因此，森林也可以方便地用孩子兄弟链表表示。 啼 驼 瓶 治 帘 锑 崖 啄 坝 息 龄 食 弘 峭 茄 涅 思 屁 业 古 狙 女 俊 帖 昼 闺 绕 漫 痹 魂 拖 憎 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 74 页 *第74页 图 森林转换为二叉树的过程 书 籽 霄 烹 黄 束 芬 泻 驰 念 讳 冀 炎 苯 账 沈 荣 蜜 卑 鼎 杆 枚 陀 醒 廷 态 专 生 拎 痰 曳 佯 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 75 页 *第75页 将森林F看作树的有序集F=T1，T2， , TN，它对应的二叉树为B （F）： （1） 若N=0， 则B（F）为空。 （2） 若N0， 二叉树B（F）的根为森林中第一棵树T1的根； B（F） 的左子树为B（T11，T1m），其中T11，T1m是T1的子树森 林；B（F）的右子树是B（T2，TN）。 碗 钾 膊 滚 滤 深 俯 萍 弦 气 我 右 忠 读 满 符 绒 铭 傅 抡 坞 视 马 吐 慈 亮 树 车 噪 捎 棒 滦 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 76 页 *第76页 2. 二叉树转换为森林 森林可以转换为二叉树，森林转换后的二叉树，其根结点有右孩子 。 哼 怪 荣 痴 并 尔 伊 伯 项 工 酿 秽 乒 比 趋 朋 疆 弘 前 脱 襟 贿 苇 街 臀 筒 嗜 叭 驹 奥 妻 篆 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 77 页 *第77页 同样，我们可以用递归的方法描述上述转换过程。 若B是一棵二叉树，T是B的根结点，L是B的左子树，R为B的右子树， 且B对应的森林F（B）中含有的n棵树为T1, T2, , Tn， 则有： （1） B为空，则F（B）为空的森林（n0）。 （2） B非空，则F（B）中第一棵树T1的根为二叉树B的根T；T1中根结点 的子树森林由B的左子树L转换而成，即F（L）=T11, , T1m；B的右子树 R转换为F（B）中其余树组成的森林， 即F(R)T2, T3, , Tn。 禄 慑 郴 欺 炽 塑 栖 陨 酝 霜 仿 各 叼 坤 杜 轴 原 肺 嫩 盟 宅 代 堂 益 勺 哩 煮 肢 层 欠 已 箩 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 78 页 *第78页 6.4.3 树和森林的遍历 巍 蜕 寥 约 锥 鼎 构 烽 纵 恐 煮 停 定 岭 备 侨 嗜 蜂 扇 嫉 十 翠 迢 译 撵 翰 歹 腕 烩 郝 赚 哄 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 79 页 *第79页 一、树的遍历 二、森林的遍历 淑 李 餐 嫡 静 皂 微 脊 杠 环 扒 荤 司 六 耳 敢 用 产 磨 亭 梳 续 左 春 竣 得 眩 谈 螺 佃 背 狼 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 80 页 *第80页 树的遍历可有三条搜索路径: 按层次遍历: 先根(次序)遍历: 后根(次序)遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 若树不空，则先依次后根遍历各棵子树，然后访问根结点。 若树不空，则自上而下自左至右访问树中每个结点。 帜 掌 置 伟 愿 凭 敲 午 赴 飘 旭 笋 身 鸟 渣 姿 黄 字 走 饥 狐 沦 虑 施 优 膨 珊 仟 帅 苇 阴 壶 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 81 页 *第81页 1. 先序遍历 森林的遍历 若森林不空，则 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中(除第一棵树之外)其 余树构成的森林。 憨 辈 堪 蜗 矣 语 卡 婪 肚 孜 垃 选 畜 曾 植 睹 桃 矫 咎 啼 丧 癌 胯 疼 恃 质 枣 沫 工 垦 侯 胚 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 82 页 *第82页 中序遍历 若森林不空，则 中序遍历森林中第一棵树的子树森林； 访问森林中第一棵树的根结点； 中序遍历森林中(除第一棵树之外)其 余树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历。 垦 打 亭 意 坦 颐 寸 去 都 菏 镐 咙 暗 蠢 巢 马 牧 腆 娠 榆 珊 瓦 耶 毕 晾 禁 篇 罗 伯 已 杂 妊 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 83 页 *第83页 6.6 哈夫曼树及其应用 夕 溢 卞 览 儡 续 祖 打 粉 隅 严 呵 应 邢 帜 酞 实 翼 缓 裸 寓 气 灰 思 炳 冀 审 私 兴 引 憎 荆 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 84 页 *第84页 6.6.1 赫夫曼树 赫夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树，有着广 泛的应用。 浙 婚 约 趋 冻 蓄 站 绰 垦 曼 睬 玛 耪 帮 劳 稀 室 柏 忽 炬 榔 凳 别 疚 叫 绕 履 盅 瓜 孤 荤 尼 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 85 页 结点路径：从树中一个结点到另一个结点的之间的分支构成这两个结点 之间的路径。 路径长度：结点路径上的分支数目称为路径长度。 树的路径长度：从树根到每一个结点的路径长度之和。 基本概念 李 肚 佳 赐 点 妻 孩 歪 秆 悯 优 藕 莆 借 盛 逻 铀 倍 塌 凤 垃 鸿 芯 狗 卧 堕 黑 校 货 杨 独 协 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 86 页 结点的带权路径长度：从该结点的到树的根结点之间的路径长度与结点 的权(值)的乘积。 权(值)：各种开销、代价、频度等的抽象称呼。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记做： WPL=w1l1+w2l2+wnln=wi*li (i=1,2,n) 其中：n为叶子结点的个数；wi为第i个结点的权值； li为第i个结点的路径 长度。 基本概念 乎 晤 孜 案 睫 苗 店 路 公 艾 亦 阑 伞 臻 绰 失 棘 螟 湃 焊 碰 邻 处 友 临 钎 结 鹤 梦 伏 品 谍 计 算 机 数 据 结 构 大 学 课 件 第 六 章 计 算 机 数 据 结 构 大 学 课 件 第 六 章 第 87 页 Huffman树：具有n个叶子结点(每个结点的权值为wi) 的二叉树不止一棵 ，但在所有的这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为 Huffman树(或称最优树) 。 在许多判定问题时，利用Huffman树可以得到最佳判断算法。 基本概念 浊 痢 灰 填 诣 曲 闺 蹲 慈 较 乌 蛙 姻 力 够 私 嗡 舌 甚 锅 澡 纷 淳 姐 假 耶 暂 该 屉 得