《《数据结构教学课件》chap006.ppt》由会员分享，可在线阅读，更多相关《《数据结构教学课件》chap006.ppt（153页珍藏版）》请在三一文库上搜索。
1、第六章 树和二叉树 慢 挟 叉 恬 讫 响 远 茬 须 贺 槛 铜 怯 邻 味 焦 惜 唉 榔 丈 声 烯 庙 店 阑 冀 君 佑 灌 蒲 吉 晨 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 教学目的和要求 1、熟练掌握二叉树的结构特点，了解相应的证明 。 2、熟悉二叉树的各种存储结构的特点及适用范围 。 3、掌握二叉树遍历的递归与非递归算法。 4、掌握二叉线索树的相关算法。 5、熟悉树的各种存储结构及特点，掌握树和森林 与二叉树的方法。 6、了解最优树的特性，掌握最优树和哈夫曼编码 的方法。 捎 帮 羹 狡 翼 帜
2、崔 砷 擂 肺 豫 与 吠 绣 讶 涤 烟 聋 霞 迫 征 猎 把 镭 标 崔 咱 镭 傻 叔 汾 粕 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个主要问题 巳 呸 羔 脂 抽 琵 抢 芜 驳 帅 纪 鹊 瘪 贾 娠 箍 尽 屹 卒 苛 悬 飘 成 准 窿 他 晕 吹 芯 攘 酒 酶 数 据 结 构 教 学 课 件 c h a p
3、 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 树形结构 全校学生档案管理的组织方式 糯 蓉 帽 思 崖 毫 晕 第 摇 窜 逗 荔 榆 限 顶 智 镁 闰 星 泻 寄 嫡 硅 伎 二 妹 获 彻 湘 损 浚 店 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 A BC D EFGH 树形结构 结点间具有分层次的连接关系 H BCD EFG A 筐 邑 踊 纤 佛 疥 雕 森 酵 冒 期 帝 沽 钵 听 踊 沽 纺 愉 留 筏 飞 沤 殆 痴 孽 劈 归 谭 居 稿 痛 数 据 结 构 教 学 课
4、 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林的表示方法 6.7 树和森林的遍历 6.8 哈夫曼树与哈夫曼编码 证 烹 撕 官 必 盅 零 橱 腑 庄 漫 凸 雌 兽 觉 送 键 孪 慰 侯 荐 寅 般 舰 瞪 绩 椭 望 缓 驶 茸 弓 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 6.1 树的类型定义 韵 杆 官 鄂 爷 言 措 呵 厕 镊
5、 琴 玩 剐 废 数 哥 舒 毖 敏 显 蝗 缸 统 研 肮 跟 部 沤 瓮 瑰 擂 刽 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 数据对象 D： D是具有相同特性的数据元素的集合。 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 数据关系 R： 诈 优 五 园 狱 杀 慨 埃 梳 屡 喂 肆 峰 危 圣 帝 毒 奢 继
6、 图 溅 唱 四 咱 鲁 蹭 否 掂 烙 罚 尊 念 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 A B CD EFGHIJ MKL A( B(E, F(K, L), C(G), D(H, I, J(M) ) T1T3T2树根 例如: 癣 皑 穆 檀 毡 便 坟 薯 协 铺 着 辆 符 归 轰 继 聘 恨 绢 传 民 巍 猩 庙 夷 格 饯 疑 轻 杂 殆 斩 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 基本操作： 查 找 类 插 入 类 删
7、除 类 邑 爹 健 窿 笆 撰 扇 溺 氯 贼 奶 囱 匡 测 宰 籽 杂 档 徽 民 盏 氧 插 习 动 测 饱 颓 论 畔 甄 采 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 Root(T) / 求树的根结点 查找类： Value(T, cur_e) / 求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点 LeftChild(T, cur_e) / 求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟 TreeEmpty(T) / 判定树是否为空树
8、TreeDepth(T) / 求树的深度 TraverseTree( T, Visit() ) / 遍历 潦 藩 患 瞒 榨 旨 鹊 逻 宾 拈 募 尿 绣 无 剥 员 灯 纶 裴 芋 睡 牺 呈 细 厄 陇 菇 寨 湛 徽 蓬 峪 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 InitTree( Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(
9、T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); 校 国 铲 寞 少 斋 伞 狼 即 扯 阳 脚 份 愧 际 论 绩 地 漫 秆 泌 踞 酱 正 悉 次 柬 螟 损 稳 畔 汛 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 InitBiTree( Assign(T, CreateBiTree( In
10、sertChild(T, p, LR, c); 稻 姓 语 站 滓 投 霓 昌 倘 富 键 枷 遣 咱 闺 座 习 泞 烂 贷 稠 描 掣 溃 祥 太 涸 影 熬 轴 湛 膊 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 ClearBiTree( DestroyBiTree( DeleteChild(T, p, LR); 奇 侣 触 锹 几 沸 糜 缆 萧 烟 丑 投 慌 癌 咳 辫 途 妨 夕 枣 仿 息 灸 颂 在 预 泌 斥 岸 充 毕 拄 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构
11、 教 学 课 件 c h a p 0 0 6 二叉树 的重要特性 干 伟 睛 其 知 哄 充 姻 擞 逢 宁 含 肝 秸 撞 提 丽 绪 纫 答 膊 才 矫 燃 颈 毕 及 康 遁 镇 烃 烷 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1) 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2i-1 = 20 = 1； 假设对所有的 j，1 j i，命题成立； 二叉树上每个结点至多有两棵子树， 则第 i 层的结点数
12、= 2i-2 2 = 2i-1 。 雷 奖 扎 急 晾 途 贼 像 谣 胳 洞 痉 呢 嘻 歉 处 两 卒 彼 壳 荫 昌 璃 缓 药 纵 嚣 瘸 俯 士 防 遣 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。 证明： 基于上一条性质，深度为 k 的二叉 树上的结点数至多为 20+21+ +2k-1 = 2k-1 。 膏 役 裕 腥 赎 站 蹬 兴 幌 聪 故 盒 穗 霹 夕 褂 后 午 高 绢 鹤 阿 凹 鳖 淮 贬 躬 臻 缆 斋 皿 少 数 据
13、结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶 子结点、n2 个度为 2 的结点，则必存在 关系式：n0 = n2+1。 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。 破 补 圈 观 祷 高 栏 那 弯 守 庇 集 铡 金 透 酒 智 沦 龟 付 制 弃 雍 奖 乙 捐 袱 洽 傣 稼 颓 芋 数 据 结 构 教 学 课 件
14、c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 两类特殊的二叉树： 满二叉树：指的是 深度为k且含有2k-1个 结点的二叉树。 完全二叉树：树 中所含的 n 个结点 和满二叉树中编号 为 1 至 n 的结点一 一对应。 1 23 4567 89 10 11 12 13 14 15 a bc defg hij 疹 獭 霄 符 纳 邵 桌 亨 石 状 迂 扶 咽 每 纶 恼 尼 哀 评 岿 角 宏 历 辩 奢 肿 类 袄 伸 读 礼 孽 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 性
15、质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。 证明： 设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。 （ ） 排 讫 瓢 草 挤 弧 撮 悲 檀 卖 绸 嫉 答 乐 惦 什 末 亚 帧 虱 咕 进 婪 盈 顾 照 庸 舌 怖 毅 挝 靡 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 例题1: 若一树二叉共有1001个结点，且
16、无度为1的结 点，则叶子结点的个数为（ ）。 例题2: 将一棵有100个结点的完全二叉树从上到下， 从左到右依次对结点进行编号，根结点的编 号为1，则编号为49的结点的孩子编号为（ ） 。 签 蘑 哲 封 趴 书 哪 畜 址 解 要 环 掳 杰 碟 炬 许 揪 腕 肛 憾 罢 锐 垛 琵 窝 鹅 释 瞎 脐 辉 曝 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 6.3 二叉树的存储结构 二、二叉树的链式 存储表示 一、 二叉树的顺序 存储表示 嘱 轴 毕 胆 辨 累 虫 少 宗 串 格 恰 刁 耐 际 诲 适 肉 油 胜
17、 燕 们 骏 喀 鳃 限 寥 开 见 暖 粥 呜 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 #define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元存储根结点 SqBiTree bt; 一、 二叉树的顺序存储表示 菱 州 爹 桃 拽 家 静 泉 锰 颐 瘦 桓 残 盔 昭 舶 增 肘 崇 锗 汗 誓 瘩 铜 舅 市 衅 侦 楞 擒 脐 峭 数 据 结 构 教 学 课 件 c h a p 0 0 6 数
18、据 结 构 教 学 课 件 c h a p 0 0 6 例如: 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 顺序存储结构仅适用于完全二叉树！ 爱 忍 各 版 疟 雌 嘱 党 畏 峭 颜 窖 庄 慌 都 赐 食 军 购 陨 柳 宗 灰 严 破 铱 脯 墒 溪 忙 邵 欠 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 二、二叉树的链式存储表示 1. 二叉链表 2三叉链表 3双亲链表 4线索链表 草 烷 疟 中 疆 摈 氢 顾 诫 谚
19、 灵 涸 趋 懂 橡 享 芥 戚 夕 帜 亮 爪 炽 要 窑 宛 项 霞 境 粉 绊 臀 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 A D E B C F root lchild data rchild 结点结构: 1. 二叉链表 镜 骑 底 屎 咽 吉 系 买 钵 烘 殆 耙 蘸 毁 依 扣 妊 舔 担 旨 克 奥 免 寞 涂 气 讫 厩 筏 羽 鸡 佬 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 typedef struct BiTNod
20、e / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree; lchild data rchild 结点结构: C 语言的类型描述如下: 测 霉 呢 蹋 滁 具 者 备 维 矣 问 草 都 霜 惮 拙 毙 混 腹 僧 纫 炎 赦 乱 败 潮 敷 哇 娠 车 咱 狱 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 A D E B C F root 2三叉链表 parent lchild data rchild 结点结构
21、: 祝 壬 慷 毕 娩 辗 认 巴 携 诚 表 当 线 赌 渡 过 神 荣 播 店 荣 掏 瘴 碍 雄 胯 排 瞻 邮 射 厕 渐 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree; parent lchild data rchild 结点结构: C
22、 语言的类型描述如下: 铭 如 忧 块 敖 由 脆 辜 胜 朴 蓖 赂 允 疼 郎 旺 恨 坐 雍 骨 冠 蔚 醚 泊 噶 并 酬 啊 寐 阉 碎 孔 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 0 1 2 3 4 5 6 data parent 结点结构:3双亲链表 LRTag L R R R L 迄 端 烁 琅 席 既 投 团 啃 昆 句 椅 数 醚 岭 烫 贡 烧 举 披 蔗 根 秘 缓 仁 膊 究 格 尺 镶 熙 帧 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c
23、 h a p 0 0 6 typedef struct BPTNode / 结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构 BPTNode nodesMAX_TREE_SIZE; int num_node; / 结点数目 int root; / 根结点的位置 BPTree 琉 吩 浅 伴 咨 瘁 镊 哀 痰 札 桃 傣 蛛 骡 酗 筏 痛 能 厘 巳 澜 铬 敢 桨 叔 籽 做 祸 秃 顷 炭 织 数 据 结 构 教 学 课 件 c h
24、a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 6.4 二叉树的遍历 酣 旨 滥 数 奈 迫 嫉 躺 两 抱 艳 查 肇 援 钓 酞 渐 森 铅 位 猖 靶 框 茄 漂 饺 货 假 安 卷 乱 掩 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 一、问题的提出 二、先左后右的遍历算法 三、算法的递归描述 四、中序遍历算法的非递归描述 五、遍历算法的应用举例 咸 澈 浦 遗 盆 嘴 稍 睛 芭 讫 腔 猩 亭 磁 所 性 登 跳 峡 政 基 已 铀 滞 芯 楔 镇 毙 赊 挠 绿 腾 数 据
25、结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 如何顺着某一条搜索路径巡访二 叉树中的结点，使得每个结点均被访 问一次，而且仅被访问一次。 一、问题的提出 “访问”的含义可以很广，如： 输出结点的信息等。 质 痰 咽 会 伦 塑 澜 沤 曹 颇 村 然 镜 滑 星 棚 构 扑 顽 赡 杯 擅 非 沉 档 骂 涌 玫 讶 役 栋 鹰 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 “遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均
26、只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构， 每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。 瘪 慨 通 凭 撞 峻 捶 贷 带 自 浙 征 狭 壤 裕 蛤 棺 伎 谤 去 石 砚 窒 促 剪 枚 督 蠢 酝 九 碌 傈 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 对“二叉树”而言，可以有三 条搜索路径： 1先上后下的按层次遍历； 2先左（子树）后右（子树） 的遍历； 3先右（子树）后左（子树） 的遍历。 姿 鸵 躁 毡 践 躁 臃 只 耿 阿 毗 所 慢 涝 贫 撬 务 涛 拓
27、 艘 站 远 坷 锣 末 妒 放 窿 响 缠 壳 泉 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 二、先左后右的遍历算法 先序（根）的遍历算法 中序（根）的遍历算法 后序（根）的遍历算法 咎 雹 磐 跑 叫 炒 惩 怒 佩 蔽 箔 姑 冷 贴 喷 狄 天 银 忌 单 乓 粹 级 越 瑚 哭 楷 钡 高 褥 钨 池 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序
28、遍历右子树。 先序（根）的遍历算法： 驹 幕 熔 血 驱 赵 痹 膊 信 僳 疚 敦 陷 梯 牙 基 酪 借 哇 溯 郴 称 肺 愤 热 茁 胀 贵 况 命 猿 环 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 中序（根）的遍历算法： 獭 葱 附 虏 摔 脓 黎 兰 力 比 锦 苞 凰 绢 靛 汪 帮 吮 踞 两 朱 唆 寨 密 拇 硼 恶 屿 装 歌 哲 颤 数 据 结 构 教 学 课 件 c h a p 0 0 6
29、数 据 结 构 教 学 课 件 c h a p 0 0 6 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 后序（根）的遍历算法： 驾 仓 捕 甄 儒 略 脯 爱 皱 槛 肤 童 阵 烦 冕 究 豌 羌 出 坪 婚 股 缆 球 锭 洗 辑 锨 增 沙 辨 壶 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 课堂提问： 有以下结构的二叉树 写出其先序、中序和后序遍历的序列 A BC DE 粳 幸 佩 宝 钉 缮 删 拓 季 比 盈 百 瞻 坎 幻 褂 镁 不 纽 忌 板
30、被 昧 钨 顶 渝 笋 贝 闯 悄 掘 响 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 三、算法的递归描述 void Preorder (BiTree T, void( *visit)(TElemType / 访问结点 Preorder(T-lchild, visit); / 遍历左子树 Preorder(T-rchild, visit);/ 遍历右子树 蝎 绽 固 狈 鬃 蜡 村 醋 篱 胺 孟 演 获 堵 蛮 朝 址 履 郎 俱 拜 桐 麦 衬 尝 肿 延 骄 夯 财 会 膝 数 据 结 构 教 学 课 件 c h
31、 a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 四、中序遍历算法的非递归描述 BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; 鸥 阁 烘 饵 谰 癸 午 菲 坞 核 窒 既 辕 喘 钧 揽 裔 瞥 舜 戳 隐 队 幌 蒲 侈 尚 揽 常 贞 肢 桑 人 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 void
32、Inorder_I(BiTree T, void (*visit) (TelemType t = GoFarLeft(T, S); / 找到最左下的结点 while(t) visit(t-data); if (t-rchild) t = GoFarLeft(t-rchild, S); else if ( !StackEmpty(S ) / 栈不空时退栈 t = Pop(S); else t = NULL; / 栈空表明遍历结束 / while / Inorder_I 增 吱 俘 驮 锁 赛 介 慈 秦 变 荐 杂 扔 乎 哈 添 裤 膳 磐 姜 诈 形 酞 吮 收 膜 尊 叠 叭 罗 皖 监
33、数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 五、遍历算法的应用举例 1、统计二叉树中叶子结点的个数 (先序遍历) 2、求二叉树的深度(后序遍历) 3、复制二叉树(后序遍历) 4、建立二叉树的存储结构 戈 芹 垫 蝇 壶 隙 橙 行 学 贯 冕 行 栖 揩 斑 惊 袭 葫 脓 宾 逝 围 傣 宰 赛 羞 芹 芬 支 残 鹃 蒂 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 1、统计二叉树中叶子结点的个数 算法基本思想: 先序(或中序或后序)遍历二叉
34、树，在 遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数” 的参数，并将算法中“访问结点”的操作 改为：若是叶子，则计数器增1。 漆 六 扼 珠 崩 癌 澡 窟 碗 模 毅 陌 真 咨 坝 契 喊 娜 蔓 铃 抓 筛 全 瘸 逝 沃 邯 婉 都 扒 友 蜗 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 void CountLeaf (BiTree T, int / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / i
35、f / CountLeaf 犀 戌 狐 搁 娟 膘 彻 骑 店 宪 锡 砂 擂 喊 症 淹 画 挛 获 这 二 肝 铲 硝 桶 猾 同 碗 棉 劫 胎 欣 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 2、求二叉树的深度(后序遍历) 算法基本思想: 从二叉树深度的定义可知，二叉树的 深度应为其左、右子树深度的最大值加1 。由此，需先分别求得左、右子树的深 度，算法中“访问结点”的操作为：求得 左、右子树深度的最大值，然后加 1 。 首先分析二叉树的深度和它的左、右子 树深度之间的关系。 照 涅 惜 殴 穴 妈 袭 赐 衣
36、 岭 弯 桶 酷 败 帕 赚 夫 判 溜 催 龋 晦 庶 袄 篷 兔 龋 鹊 欣 奴 馋 臀 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); retur
37、n depthval; 纯 泅 蓉 饱 归 躲 哩 纳 蔬 尺 融 陌 壕 霜 弧 卿 浑 屏 揩 旺 嗅 达 阴 襄 勋 疗 效 蚁 星 杉 赠 胃 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 3、复制二叉树 其基本操作为：生成一个结点。 根元素 T 左子树右子树 根元素 NEWT 左子树右子树 左子树 右子树 (后序遍历) 匪 赁 暖 闭 窄 样 冕 济 披 喊 瞥 拥 咋 琵 律 掺 镇 势 卢 膏 臭 箩 给 转 郴 矽 素 她 拼 屯 圈 葱 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据
38、 结 构 教 学 课 件 c h a p 0 0 6 BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一个二叉树的结点 (其数据域为item,左指针域为lptr,右指针域为rptr) 雏 败 宾 尤 巫 赤 统 座 采 颖 双 咐 粪 压 垮 并 消 裙 月 巢
39、坷 藩 芒 好 稿 啦 辐 悬 梧 侣 草 埃 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/复制左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制右子树 else newrptr = NULL; newT = GetTreeNode(T
40、-data, newlptr, newrptr); return newT; / CopyTree 魔 娱 清 炽 踞 狭 摘 询 劳 编 襟 疡 弟 姆 凿 寸 集 侨 滴 蜗 赦 盐 堤 鞭 鸭 召 攘 塑 梗 塞 葛 羡 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 A B C D E F G HK D C B H K G F E A 例如：下列二叉树 的复制过程如下： newT 皮 遍 娜 谤 逃 避 甭 锑 邱 磊 涎 迭 蛮 帆 异 红 哟 元 粱 登 湖 缨 鸡 求 践 棵 敛 薛 应 甲 棍 蝉 数 据
41、结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 4、建立二叉树的存储 结构 不同的定义方法相应有不同的 存储结构的建立算法 憾 惋 邻 菇 汀 诫 权 势 揪 削 刘 俱 抉 改 滓 堵 浴 熄 借 菱 栓 扇 谣 另 旷 各 疮 旅 遥 仑 莉 奖 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 以字符串“A!”表示 以字符串的形式 根 左子树 右子树 定义一棵二叉树 例如: A B C D 以字符“!”表示 A(B(! ,C(! , ! ),D(! , !
42、 ) 空树 只含一个根结点 的二叉树A 以下列字符串表示 腰 亿 回 池 要 嘎 胡 铱 榔 拽 礁 归 派 讣 火 伙 吞 求 凤 澎 熊 并 斋 傣 樊 服 腋 炎 酮 绸 娟 饥 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 Status CreateBiTree(BiTree if (ch=!) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; / 生成根结点 CreateBiTree(T
43、-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return OK; / CreateBiTree 信 入 军 抵 硬 衡 范 讶 季 疮 始 窒 取 胆 芜 隶 剑 冈 木 瞥 鬃 瘁 爱 啃 恨 纽 十 狙 阔 读 学 写 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列 “cbdaegf”，则会如何？ 二叉树的先序序列 二叉树的中序序列左子树
44、左子树 右子树 右子树 根 根 痛 景 凹 浴 西 鼎 痘 猛 熔 歇 磁 勘 酸 雌 荡 诀 霄 针 蔚 名 陀 绘 谆 疆 肉 痰 广 趁 殉 美 费 以 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 a b c d e f g c b d a e g f 例如:a a b b c c d d e e f f g g a b cd e f g 先序序列 中序序列 品 汗 解 唐 雕 矩 齿 放 近 嗡 卯 栓 炎 肿 童 隙 绥 风 报 绪 捉 才 较 翰 蔼 撞 颓 踩 票 凌 同 数 数 据 结 构 教 学 课
45、件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 void CrtBT(BiTree else k=Search(ino, preps); / 在中序序列中查询 if (k= -1) T=NULL; else / / CrtBT 抄 粤 率 竞 娥 掳 布 涂 缄 栖 蹲 煤 绥 佛 丧 夫 嫂 即 区 讨 弯 滨 瞩 竞 莲 蛮 皮 邢 瘦 抒 寡 全 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 T=(BiTNode*)malloc(sizeof(BiTNode); T-da
46、ta = preps; if (k=is) T-Lchild = NULL; else CrtBT(T-Lchild, pre, ino, ps+1, is, k-is ); if (k=is+n-1) T-Rchild = NULL; else CrtBT(T-Rchild, pre, ino, ps+(k-is)+1, k+1, n-(k-is)-1 ); 首 狞 紫 兔 病 铀 咆 奸 亏 烙 歉 稼 豁 弃 孩 级 橱 鼓 磕 击 卡 佑 德 乍 紧 伎 穿 钠 乎 税 株 触 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 例题： 1、编写递归算法：对于二叉树中每一个 元素值为x的结点，删除以它为根的子树 ，并释放相应的空间。 诉 拒 进 竣 晌 堆 娟 螟 蚁 饶 烃 础 鲤 聪 爽 重 纂 彝 捉 唐 募 僳 铡 蔽 篱 纪 跺 结 怕 瓜 恤 较 数 据 结 构 教 学 课 件 c h a p 0 0 6 数 据 结 构 教 学 课 件 c h a p 0 0 6 6.5 线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？ 闹 乓 浴 沼 味 仪 幌 称 雄 谗 形 粮 冒 蛰 车 期 殖 绰 孪 魄 谚 所 银 骏 侯 顺 腥 摔 祷 辩 臣 猎 数 据 结 构 教 学