c数据结构,二叉树DS5-BinaryTree(new)

《c数据结构,二叉树DS5-BinaryTree(new)》由会员分享，可在线阅读，更多相关《c数据结构,二叉树DS5-BinaryTree(new)（91页珍藏版）》请在装配图网上搜索。

1、第 五 章 二 叉 树 主 要 内 容 5 .1 定 义 与 主 要 特 性 5 .2 二 叉 树 的 实 现 5 .3 遍 历 二 叉 树 及 线 索 化 5 .4 二 叉 搜 索 树 5 .5 AVL树 5 .6 堆 5 .7 霍 夫 曼 编 码 树 2 5 .1 定 义 与 特 性 5.1.1 定 义 和 术 语 5.1.2 二 叉 树 的 性 质 3 5 .1 .1 定 义 和 术 语 一 、 树 的 定 义 5 定 义 ： 树 (Tree)是 n(n=0)个 结 点 的 有 限 集 T， T为 空时 称 为 空 树 ， 否 则 它 满 足 如 下 两 个 条 件 ： （ 1） 有 且

2、 仅 有 一 个 特 定 的 称 为 根 (Root)的 结 点 ； （ 2） 其 余 的 结 点 可 分 为 m(m=0)个 互 不 相 交 的 子 集T1,T2,T3Tm， 其 中 每 个 子 集 又 是 一 棵 树 ， 并 称 其 为 子 树(Subtree)p 这 是 一 个 递 归 定 义 。 二 、 二 叉 树 的 定 义 6 p 定 义 ： 二 叉 树 是 由 n(n=0)个 结 点 的 有 限 集 合 构 成 ，此 集 合 或 者 为 空 集 ， 或 者 由 一 个 根 结 点 及 两 棵 互不 相 交 的 左 右 子 树 组 成 ， 并 且 左 右 子 树 都 是 二 叉树

3、。p 这 也 是 一 个 递 归 定 义 。 二 叉 树 可 以 是 空 集 合 ，根 可 以 有 空 的 左 子 树 或 空 的 右 子 树 三 、 相 关 术 语 7 p 结 点 的 度p 树 的 度p 叶 结 点p 分 支 结 点p 左 孩 子 、 右 孩 子 、 双 亲p 路 径 、 路 径 长 度p 祖 先 、 子 孙p 结 点 的 深 度p 树 的 高 度 5 .1 .2 二 叉 树 的 性 质 99 一 、 二 叉 树 的 定 义 和 特 点 1、 定 义 ： 二 叉 树 是 有 限 个 结 点 的 集 合 ， 它 或 者 是 空 ， 或者 是 由 一 个 根 结 点 加 上 两

4、 棵 分 别 称 为 左 子 树 和 右 子 树 、 互 不相 交 的 二 叉 树 组 成 。2、 特 点 每 个 结 点 最 多 只 有 两 个 孩 子 结 点 ， 即 结 点 的 度 不 大 于 2。 子 树 有 左 右 之 别 ， 子 树 的 次 序 （ 位 置 ） 不 能 颠 倒 。3、 基 本 形 态 空 只 有 根 结 点 根 的 右 子 树 为 空 根 的 左 子 树 为 空 根 的 左 右 子 树 都 不 空 10 二 、 二 叉 树 的 性 质1、 若 层 次 从 0开 始 ， 则 第 i层 最 多 有 2 个 结 点i2、 高 度 为 h的 二 叉 树 最 多 有 2 -1

5、个 结 点 h 第 0层 （ 根 ）第 1层第 2层第 3层 11 如 果 二 叉 树 中 每 一 个 结 点 ， 或 者 是 叶 节 点 ，或 者 是 分 支 节 点 且 恰 有 两 个 非 空 子 结 点 。24 5 36 71图 满 二 叉 树三 、 满 二 叉 树 12 12 34 5 6 12 34 5 7 12 36 7(a)完 全 二 叉 树 (b)非 完 全 二 叉 树 ( c)非 完 全 二 叉 树图 完 全 二 叉 树四 、 完 全 二 叉 树一 棵 高 度 为 d的 二 叉 树 除 了 d-1层 以 外 每 一 层 都 是 满 的 ，并 且 每 一 层 都 是 从 左 到

6、 右 填 充 13 定 理 1： 非 空 满 二 叉 树 的 叶 结 点 数 等 于 其分 支 结 点 数 加 1四 、 满 二 叉 树 定 理定 理 2： 一 棵 非 空 二 叉 树 空 子 树 的 数 目 等 于 其 结点 数 目 加 1 14 如 图 5.11所 示 为 完 全 二 叉 树 上 结 点 及 其左 右 孩 子 结 点 之 间 的 关 系 。i/2i i+12i 2i+1 2(i+1) 2i+3 i+1/2i+12(i+1) 2i+3 i2i 2i+1图 5.11 完 全 二 叉 树 中 结 点 I和 i+1(a)I和 i+1结 点 在 同 一 层 (b)I和 i+1结 点

7、不 在 同 一 层 5 .2 二 叉 树 的 实 现 5.2.1 二 叉 树 抽 象 数 据 类 型 5.2.2 使 用 指 针 实 现 5.2.3 使 用 数 组 实 现 15 16 5 .2 .1 二 叉 树 的 抽 象 数 据 类 型二 叉 树 结 点 的 ADT template class BinNodepublic: virtual Elem/返 回 元 素 的 值 virtual void setVal(const Elem ;/设 置 元 素 的 值 virtual BinNode* left()=0 ; ;/返 回 左 结 点 的 指 针 virtual BinNode* r

8、ight()=0 ; /返 回 右 结 点 的 指 针 virtual void setLeft(BinNode*)=0 ; /设 置 左 结 点 virtual void setRight(BinNode*)=0 ; /设 置 右 结 点 virtual bool isLeaf()=0 ; /判 断 是 否 为 叶 结 点 16 17 5.2.2 使 用 指 针 实 现结 点 结 构 和 示 例 leftChild data rightChildABC D E Froot A B C D E F root 18 二 叉 树 的 二 叉 链 表 存 储 表 示template class Bi

9、naryTree;template class BinTreeNode firend class BinaryTree;private: Elem data;/数 据 域 BinTreeNode * lchild; /左 子 结 点 指 针 域 BinTreeNode * rchild; /右 子 结 点 指 针 域public: BinTreeNode()lchild=rchild=NULL; BinTreeNode(Elem e,BinNodePtr*l=NULL, BinNodePtr*r=NULL) data=e; lchild=l; rchild=r; BinTreeNode() 链

10、 式 存 储 的 特 点 动 态 建 立 ， 灵 活 性 高 结 构 性 开 销 大 19 20 5.2.3 使 用 数 组 实 现ab cd e f gh i j k lA B C D E F G H I J K L 1 2 3 4 5 6 7 8 9 10 11 12 21 一 般 二 叉 树 AB CD EF G 表 示 该 处 没 有 元 素存 在 仅 仅 为 了 好 理 解A B C D E F G 数 组 存 储 的 特 点 对 于 完 全 二 叉 树 空 间 利 用 率 很 高 从 树 根 起 ， 自 上 层 至 下 层 ， 每 层 自 左 至 右的 给 所 有 结 点 编 号

11、缺 点 是 有 可 能 对 存 储 空间 造 成 极 大 的 浪 费 在 最 坏 的 情 况 下 ， 一 个 深 度 为 H且 只 有 H个结 点 的 右 单 支 树 确 需 要 2 h-1 个 结 点 存 储 空 间 。而 且 ， 若 经 常 需 要 插 入 与 删 除 树 中 结 点 时 ，顺 序 存 储 方 式 不 是 很 好 22 5 .3 二 叉 树 的 遍 历 及 线 索 化 5.3.1 遍 历 二 叉 树 5.3.2 线 索 化 二 叉 树 23 24 5.3.1 遍 历 二 叉 树 （ Traversal Binary Tree）一 、 TBT概 述1、 定 义 按 某 种 次

12、 序 ， 访 问 所 有 结 点 ， 使 每 个 节 点 都 被 访 问 且尽 访 问 一 次 的 运 算 叫 TBT。 “访 问 ” 包 括 输 出 结 点 值 ， 修 改 值 ， 统 计 等 以 不 破 坏BT的 结 构 为 原 则 。 TBT是 对 二 叉 树 进 行 运 算 的 基 础 性 操 作 。 25 一 、 TBT概 述2、 次 序 （ V根 ， L左 子 树 ， R右 子 树 ） 先 序 遍 历 中 序 遍 历 后 序 遍 历先 右 后 左 ： VRL RVL RLV先 左 后 右 ： VLR LVR LRVbtAB CD E F G HI J VLR输 出 序 列 ： A

13、B D E G HI J C FLVR输 出 序 列 ： D B G EI H J A C FLRV输 出 序 列 ： D G I JH E B F C A 26 二 、 TBT的 递 归 算 法1、 中 序 遍 历 （ inorder traversal）template void BinaryTree : InOrder ( ) InOrder (root); /公 共 函 数 ， 调 用 私 有 函 数 完 成 遍 历template void BinaryTree : InOrder (BinTreeNode *current) if (current != NULL) /当 curr

14、ent = = NULL， 则 递 归 终 结 InOrder (current - leftChild); /中 序 遍 历 左 子 树 cout data; /访 问 根 结 点 InOrder (current - rightChild); /中 序 遍 历 右 子 树 / a b c de f 对 a+b*(c-d)-e/f 表 达 式 的 语法 树 ， 中 序 遍 历 得 到 其 中 缀 表示 ： a + b * c d e / f 27 2、 先 序 遍 历 （ preorder Traversal）template void BinaryTree : PreOrder (BinT

15、reeNode *current) /私 有 函 数 if (current != NULL) cout data; PreOrder (current - leftChild); PreOrder (current - rightChild); / a b c de f 对 表 达 式 a+b*(c-d)-e/f 的 语法 树 进 行 先 序 遍 历 得 到 其 前 缀表 示 ： + a * b c d / e f二 、 TBT的 递 归 算 法 28 3、 后 序 遍 历 （ postorder traversal）template void BinaryTree : PostOrder

16、(BinTreeNode *current) /私 有 函 数 if (current != NULL) PostOrder (current - leftChild); PostOrder (current - rightChild); cout data; 二 、 TBT的 递 归 算 法 / a b c de f 对 表 达 式 a+b*(c-d)-e/f 的 语法 树 进 行 后 序 遍 历 得 到 其 后 缀表 示 ： a b c d * + e f / 29 二 、 TBT的 递 归 算 法4、 TBT递 归 算 法 的 简 化traversal (BinTreeNode *cur

17、rent) if (current != NULL) traversal (current - leftChild); cout data; traversal (current - rightChild); 30 三 、 TBT的 非 递 归 算 法1、 递 归 算 法 中 栈 的 使 用 执 行 过 程 中 栈 的 情 况 和 current的 变 化 举 例 当 左 向 递 归 则 current的 值 进 栈 若 current = = NULL， 则 出 栈 ， current以 栈 顶 值 去 执 行 右 向 递 归 直 到 栈 空 （ top = -1） 和 current =

18、= NULL为 止current top ad1 ad2 ad345 stackAB C D E ad1ad2ad3 ad4 ad5 -1 0 1 2 3 31 2、 利 用 栈 的 前 序 和 中 序 遍 历 非 递 归 算 法template void BinaryTree : PreOrder ( ) stack BinTreeNode * st; BinTreeNode *p = root; do while (p != NULL) cout data; st. Push (p); p = p -leftChild; if ( St. length()!=0) st. pop (p )

19、; p = p - rightChild; while (p != NULL | | st.length ( )!=0); 算 法 描 述 p不 空 则 p进 栈 ， 沿 左 子 树 方 向 传 递 指 针 若 p空 但 栈 不 空 ， 出 栈 ， p以 栈 顶 值 沿 右 子 树 方 向 传 递 指 针 循 环 下 去 ， 直 到 p和 栈 都 空 为 止 执 行 中 栈 的 情 况 和 指 针 的 变 化 与 递 归 程 序 相 同三 、 TBT的 非 递 归 算 法 对 于 中 序 遍 历 只 需 调 整 输 出 语 句 位 置 即 可 32 3、 层 次 遍 历三 、 TBT的 非 递

20、 归 算 法AB CD E Frootad1ad2 ad3ad 4 ad5 ad6 33 3、 层 次 遍 历template void BinaryTree : LevelOrder ( ) queue BinTreeNode * qu; BinTreeNode *p = root; qu.Enqueue(p); while (qu.DeQueue (p ) cout data leftChild != NULL) qu.EnQueue (p - leftChild); if (p - rightChild != NULL) qu.EnQueue (p - rightChild);三 、 T

21、BT的 非 递 归 算 法 34 层 次 遍 历 是 指 直 上 至 下 ， 从 左 到 右 访 问 结 点 只 有 采 用 队 列 来 存 放 结 点 地 址 才 能 实 现 层 次 遍 历 3、 层 次 遍 历 示 例f r pad 1 ad2 ad3 ad4 ad5 ad60 1 2 3 4 5 6 7 AB CD E Frootad1ad2 ad3ad4 ad5 ad6 35 5.3.2 线 索 化 二 叉 树一 、 概 述1、 问 题 提 出 遍 历 是 二 叉 树 最 基 本 的 运 算 ， 为 避 免 再 次 遍 历 的麻 烦 ， 可 将 首 次 遍 历 得 到 的 信 息 存

22、于 一 个 线 性 结 构 中 。 具 有 n个 结 点 的 链 式 存 贮 的 二 叉 树 中 ， 有 n+1个 链域 是 空 的 ， 能 否 充 分 利 用 这 些 空 的 链 域 来 存 放 结 点 的前 趋 指 针 和 后 继 指 针 呢 ？ 36 一 、 概 述2、 实 现 策 略 结 点 中 增 加 两 个 标 记 域 两 标 记 域 取 值 范 围 是 0， 1。 各 只 占 一 个 二 进 制 位 ，只 增 加 很 少 的 额 外 空 间 开 销 。 rightChildleftChild leftThread data rightThread指 向 左 孩 子 0指 向 前

23、驱 1 指 向 右 孩 子0 指 向 后 继1 37 3、 线 索 二 叉 树 指 向 前 驱 和 指 向 后 继 的 指 针 叫 做 线 索 （ Thread） 。 具 有 线 索 的 二 叉 树 叫 做 线 索 二 叉 树 。 因 遍 历 的 次 序 有 三 种 ， 所 以 线 索 二 叉 树 也 分 前 、 中 、后 序 这 三 种 。 中 序 遍 历 线 索 二 叉 树 结 构 示 例 若 根 的 左 子 树 不 空 ， 则 其 最 左 下 角 的 结 点 为 中 序 遍 历 的 第 一 个 结 点 ， 否 则 根 为 中 序 遍 历 的 第 一 个 结 点 。 若 根 的 右 子 树

24、 不 空 ， 则 其 最 右 下 角 的 结 点 为 中 序 遍 历 的最 后 一 个 结 点 ， 否 则 根 为 中 序 遍 历 的 最 后 一 个 结 点 。0 E 0 0 B 0 1 F 0 0 D 1 1 G 1 1 C 1 1 A 1 root ED GrootBA FCNULL NULL 38 二 、 中 序 线 索 二 叉 树 的 类 定 义1、 类 声 明template class ThreadTree;template class ThreadNode friend class ThreadTree ;private: int leftThread, rightThread

25、; ThreadNode * leftChild, rightChild; Elem data;public: ThreadNode (const Elem item) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) Elem getData ( ) const return data; 39 template class ThreadTree private : ThreadNode *root; InThread (ThreadNode *current, ThreadN

26、ode *pre);public : ThreadTree( ) : root(NULL) ; ThreadNode *First(ThreadNode *current); ThreadNode *Last(ThreadNode * current); ThreadNode *Next(ThreadNode *current); ThreadNode *Prior(ThreadNode *current); void Inorder( ); /从 第 一 个 结 点 开 始 沿 着 后 继 方 向 遍 历 二 叉 树 40 5.4 二 叉 搜 索 树 （ Binary Search Tree

27、）一 、 基 本 概 念1、 定 义 或 是 空 、 或 是 具 有 下 列 性 质 的 二 叉 树 ：每 个 结 点 有 一 个 作 为 搜 索 依 据 的 关 键 码 （ Key） 。左 子 树 上 所 有 关 键 码 小 于 根 结 点 关 键 码 。右 子 树 上 所 有 关 键 码 大 于 根 结 点 关 键 码 。2、 举 例 中 序 遍 历 结 果 ：09， 17， 23， 45， 53， 65， 78， 81，87， 94显 然 是 有 序 的 ， 故 又 称 二 叉 排 序 树 。53 65 81 8709 452317 78 94 41 一 、 基 本 概 念 3、 BST

28、是 基 于 二 叉 树 的 动 态 搜 索 结 构 ， 其 删 除 和 插 入结 点 可 能 要 改 变 树 的 结 构 。 4、 BST类 定 义 特 点 类 定 义 基 于 二 叉 链 存 贮 表 示 与 一 般 二 叉 树 类 定 义 十 分 相 似 可 以 继 承 一 般 二 叉 树 类 的 定 义 基 本 运 算 Find, Insert 和 Remove 都 用 递 归 实 现 所 以 在类 定 义 中 包 括 私 有 和 公 用 两 种 性 质 的 声 明 42 二 叉 查 找 树 的 C+类 说 明template class BST: public Dictionarypri

29、vate: BinTreeNode * root; Elem RefValue int nodecount; void clearhelp(BinTreeNode*); BinTreeNode* inserthelp(BinTreeNode*,const Elem BinTreeNode* deletemin(BinTreeNode*,BinTreeNode* BinTreeNode* removehelp(BinTreeNode*, const Key bool findhelp(BinTreeNode*, int) const; void printhelp(BinTreeNode* ,i

30、nt) const; 43 public: BST( ) root=NULL; nodecount=0 ; BST()clearhelp(root); void clear()clearhelp(root); root=NULL; nodecount=0 ; bool insert(const Elem nodecount+; return true; bool remove(const Key root=removehelp(root, K, t); e=t-val(); nodecount-; delete t; return true; bool removeAny(Elem root=

31、deletemin(root, t); e=t-val(); delete t; nodecount-; return true; 44 bool find(counst Key int size()return nodecount; void print()const if(root=NULL) count“The BST is empty.n”; else printHelp(root, 0 ); ; 45 二 、 BST上 的 搜 索1、 基 本 方 法从 根 开 始 将 给 定 值 x 与 结 点 值 进 行 比 较若 x 小 ， 沿 着 左 子 树 继 续 搜 索若 x 大 ， 沿

32、着 右 子 树 继 续 搜 索若 与 x 等 则 成 功 返 回 结 点 地 址 ， 若 为 空 则 失 败2、 举 例 x = 235365 81 8709 452317 78 94 成 功 ， 比 较 次 数 为 4 x = 88 失 败 ， 比 较 次 数 为 4 比 较 次 数 不 大 于 h + 1 46 3、 递 归 算 法template bool BST:findHelp (BinNode*subroot, constKey else if (KEComp:lt(K,subroot-val() return findHelp (subroot-left(),K,e); else

33、 if (KEComp:gt(K,subroot-val() return findHelp (subroot-rightt(),K,e); else e=subroot-val(); return true; 该 算 法 的 递 归 调 用 语 句 都 于 程 序 的 最 尾 ， 称 为 尾 递 归 返 回 时 返 回 到 上 一 层 调 用 处 的 下 条 语 句 去 执 行 因 为 是 最 尾 语 句 ， 程 序 结 束 ， 不 必 用 栈 保 存 返 回 地 址 和 局 部 变 量 的 值 该 算 法 可 以 不 用 栈 ， 采 用 迭 代 方 法 改 写 成 非 递 归 程 序 二

34、、 BST上 的 搜 索 47 4、 迭 代 算 法template bool BST:findHelp (BinTreeNode*subroot, constKey while (temp != NULL) if (KEComp:eq(K, temp-val() e=temp-val(); return true; if (KEComp:gt(K, temp-val() temp = temp -rightChild; else temp = temp - leftChild; return false; 一 般 对 尾 递 归 或 单 向 递 归 的 情 形 ， 都 可 利 用 迭 代 方

35、 法 ， 不 使 用 栈 将 递 归 过 程 改 为 非 递 归 过 程 二 、 BST上 的 搜 索 48 三 、 BST中 的 插 入1、 方 法先 搜 索 BST中 有 无 该 结 点 ， 只 有 无 才 插 入插 入 是 作 为 叶 子 插 入 ， 插 入 后 仍 满 足 BST插 入 位 置 应 是 搜 索 操 作 停 止 （ 指 针 ptr为 空 ） 的 地 方2、 算 法template BinNode* BST: inserthelp(BinNode* subroot, const Elem if (EEComp:lt(val, subroot-val() subroot-se

36、tLeft(inserthelp(subroot-left(), val); else subroot-setRight(inserthelp(subroot-right(), val); / Return subtree with node inserted return subroot; 49 3、 建 BST 逐 次 输 入 关 键 码 序 列 建 一 棵 BST， 是 从 空 开 始 逐 步 插入 结 点 每 次 从 根 开 始 搜 索 插 入 位 置 ， 然 后 将 新 结 点 作 为 叶子 插 入 关 键 码 集 合 相 同 但 输 入 序 列 不 同 得 到 的 BST也 不 同

37、若 输 入 次 序 ：81, 65, 78, 94, 87, 88, 23, 45 , 09, 17, 538187 1723 7809 65 9445 53 88 三 、 BST中 的 插 入 50 四 、 BST中 的 结 点 删 除1、 原 则删 除 结 点 所 断 开 的 链 要 重 新 接 起 来删 除 链 接 后 仍 是 BST重 新 链 接 后 树 的 高 度 不 增 加2、 方 法 被 删 结 点 为 叶 子 ， 只 需 将 双 亲 结 点 的 相 应 指 针 置 为 空 被 删 结 点 无 右 子 树 ， 拿 左 孩 子 结 点 顶 替 它 的 位 置 被 删 结 点 无 左

38、 子 树 ， 拿 右 孩 子 结 点 顶 替 它 的 位 置 被 删 结 点 左 右 子 树 都 有 ， 在 右 子 树 中 找 中 序 遍 历 第 一个 结 点 ， 用 它 的 值 填 补 到 被 删 结 点 ， 然 后 再 来 删 这 个 结 点 结 点 删 除 是 一 个 递 归 的 过 程 51 3、 有 左 右 子 树 的 结 点 删 除 举 例 删 除 关 键 码 78的 结 点 右 子 树 中 序 第 一 结 点 是 8181复 盖 7881结 点 无 左 子 树 ， 用 右 孩 子 88顶 替5365 81 9409 452317 78 88四 、 BST中 的 结 点 删 除

39、818 BST中 deletemin函 数 的 实 现deletemin(BinTreeNode*subroot,BinTreeNode* return subroot-right();else subroot-SetLeft(deletemin(subroot-left(),min); return subroot; 52 53 removehelp(BinTreeNode*subroot, constKey else if(KEComp:lt(K,subroot-val() subroot-setLeft(removehelp(subroot-left(),K,t); else if(KE

40、Comp:gt(K,subroot-val() subroot-setRight(removehelp(subroot-right(),K,t); else BinTreeNode*temp; t=subroot; if(subroot-left()=NULL) subroot=subroot-right(); else if(subroot-right()=NULL) subroot=subroot-left(); else subroot-setRight(deletemin(subroot-right(),temp); Elem te=subroo-val(); subroot-setV

41、al(temp-val(); temp-setVal(te); t=temp return subroot; BST中 removehelp函 数 的 实 现 思 考 ： BST树 平 衡 性 如 何 ？ ？ 能 不 能 保 证 平 衡 ？ 54 55 5.5 AVL树一 、 AVL树 （ 高 度 平 衡 的 BST） 概 念 1、 定 义 AVL或 是 空 树 ， 或 是 具 有 下 列 性 质 的 BST：它 的 左 、 右 子 树 都 是 AVL树 ， 且 左 右 子 树 的 高 度 之 差 的 绝 对 值不 超 过 1。2、 举 例 是 二 叉 搜 索 树 树 和 所 有 子 树 的

42、左 右 子 树高 度 之 差 绝 对 值 不 超 过 1 属 AVL树111514 263 97 1816100 00 00 0 13、 平 衡 因 子 （ balance factor） 结 点 右 子 树 高 度 减 去 左 子 树 高 度 所 得 高 度 差 AVL树 中 所 有 结 点 的 平 衡 因 子 只 能 取 0， 1， 1 AVL树 的 ASL可 保 持 在 O(log2n) 56 二 、 平 衡 化 旋 转 1、 向 AVL树 插 入 结 点 可 能 造 成 不 平 衡 ， 此 时 要 调 整 树 的结 构 使 之 重 新 达 到 平 衡 2、 平 衡 化 旋 转 方 法

43、从 插 入 位 置 沿 通 向 根 的 路 径 回 溯 检 查 各 结 点 的 平 衡因 子 若 发 现 不 平 衡 结 点 ， 则 从 该 结 点 起 沿 刚 才 回 溯 路 径取 直 接 下 两 层 结 点 若 三 个 结 点 在 一 条 直 线 上 ， 则 采 用 单 旋 转 进 行 平 衡化 ； 若 三 结 点 在 一 条 折 线 上 ， 则 采 用 双 旋 转 进 行 平 衡 化 57 3、 平 衡 化 旋 转 示 例左 单 旋 转h h hAB CD E01(a)AVL树 h h h+1AB CD E12(b)E子 树 中 插 入 结 点 h h h+1AB CD E0 0(c)左

44、 向 旋 转 后 的 AVL树二 、 平 衡 化 旋 转 58 右 单 旋 转hhh AB CD E0 - 1(a)AVL树 hhh+1 AB CD E- 1 - 2(b)D子 树 中 插 入 结 点 hhh+1 AB CD E 00(c) 右 向 旋 转 后 的 AVL树3、 平 衡 化 旋 转 示 例二 、 平 衡 化 旋 转 59 先 左 后 右 双 旋 转h h h-1 hAB CD EF G插 入(a)F子 树 插 入 结 点高 度 变 为 h- 21 - 1 h h h-1 hAB CD EF G(b)绕 E， 将 B逆 时 针 转 后 h h h-1 hAB CD EF G(c)

45、绕 E， 将 A顺 时 针 转 后03、 平 衡 化 旋 转 示 例二 、 平 衡 化 旋 转 60Copyright 2004 by Li Rui 60 先 右 后 左 旋 转hhh-1h AB CD EF G插 入(a)G子 树 插 入 结 点高 度 变 为 h2 1- 1 hhh-1h AB CD EF G(b)绕 D， C顺 时针 转 之 后 hhh-1h AB CD EF G(c)绕 D， A逆 时针 转 之 后03、 平 衡 化 旋 转 示 例二 、 平 衡 化 旋 转 61 三 、 AVL树 的 建 立 对 于 一 组 关 键 码 的 输 入 序 列 ， 从 空 开 始 不 断

46、插 入结 点 ， 最 后 构 成 AVL树 每 插 入 一 个 结 点 后 就 应 判 断 从 该 结 点 到 根 的 路 径上 有 无 结 点 发 生 不 平 衡 如 有 不 平 衡 问 题 ， 利 用 旋 转 方 法 进 行 树 的 调 整 ，使 之 平 衡 化 建 AVL树 过 程 是 不 断 插 入 结 点 和 必 要 时 进 行 平 衡化 的 过 程 62 BST、 AVL树 在 Mini数 据 库 中 的 应 用 63Copyright 2004 by Li Rui 63 64 5.6 堆 （ Heap）一 、 堆 的 定 义1、 什 么 是 堆 ？ 若 有 n个 关 键 字 的

47、集 合 K=k0,k1,k2, ,kn-1将 其 所 有 元 素 按 完全 二 叉 树 的 顺 序 存 贮 方 式 存 于 一 个 一 维 数 组 中 ， 并 且 满 足 以 下条 件 ， 则 该 集 合 称 为 最 小 堆 （ 或 最 大 堆 ） 。 kik2i+1和 kik2i+2 或 kik2i+1和 kik2i+2 (其 中 ， i = 0,1, (n 2) / 2 ) 举 例09 17 65 23 45 78 87 53 31 0 1 2 3 4 5 6 7 8最 小 堆 87 78 53 45 65 09 31 17 23 0 1 2 3 4 5 6 7 8最 大 堆0917 65

48、23 45 78 8753 31 01 23 4 5 67 8堆 顶 元 素 值 最 小 8778 5345 65 09 3117 23 01 23 4 5 67 8堆 顶 元 素 值 最 大 65 2、 最 小 堆 的 类 声 明template class MinHeap private : Elem * heap; /存 放 堆 元 素 的 数 组 int n; /堆 当 前 元 素 个 数 int size; /堆 最 多 允 许 元 素 个 数 void siftdown (int i) public : MinHeap (Elem* h, int num ,int max) /构

49、造 堆 Heap=h; n=num; size=max; buildHeap(); int heapsize() const return n; MinHeap( ) delete heap; 66 bool Insert (const Elem bool RemoveMin (Elem bool isLeaf(int pos) constreturn (pos=n/2 ) i-) siftdown(i); ; 67 二 、 堆 的 建 立1、 自 下 向 上 逐 步 调 整 建 堆 的 举 例ij 5317 7809 45 87 6523 31 01 23 4 5 67 8i = (n 2)

50、 / 2 = 3 68 i j5317 7809 45 87 6523 31 01 23 4 5 67 8 i = 2二 、 堆 的 建 立1、 自 下 向 上 逐 步 调 整 建 堆 的 举 例 65 78 69 ij 5317 6509 45 87 7823 31 01 23 4 5 67 8 i = 1二 、 堆 的 建 立1、 自 下 向 上 逐 步 调 整 建 堆 的 举 例0917ij 70 ij ij二 、 堆 的 建 立1、 自 下 向 上 逐 步 调 整 建 堆 的 举 例ij 5309 6517 45 87 7823 31 01 23 4 5 67 8 i = 009531

51、75325 对 第 i个 关 键 字 进 行 筛 选 的 要 点 ： 在 第 （ 2 i + 1） 和 （ 2 i + 2） 中 选 小 者 定 为 第 j 若 第 i大 于 第 j则 交 换 向 下 继 续 ： i = j， j = 2 i + 1， 重 复 、 ， 直 到 j (n 1) 71 向 下 筛 选 的 算 法template void MinHeap :siftDown(int pos) while(!isLeaf(pos) int j=leftchild(pos); int rc=rightchild(pos); if(rcn) if(!Comp:gt(Heappos,Hea

52、pj) return; swap(Heap, pos, j); pos=j; 72 三 、 堆 的 插 入 与 删 除1、 插 入 插 入 是 插 到 最 小 堆 的 后 面 ， 这 样 整 体 可 能 不 是 堆 了 。 为 了 再 成 堆 ， 要 从 插 入 元 素 的 双 亲 开 始 逐 层 向 上 筛 选 。 向 上 筛 选 举 例 0917 6523 45 78 8753 31 01 23 4 5 6 7 8 (a)筛 选 示 意 图11 9 0911 6523 17 78 8753 31 (b)筛 选 后45 73 template bool MinHeap : Insert(co

53、nst Elem int curr=n+; /插 入 到 堆 的 最 后 位 置 while(curr!=0) curr=parent(curr); return true;三 、 堆 的 插 入 与 删 除1、 插 入 74 2、 删 除 最 小 元 素 删 除 是 指 删 除 最 小 关 键 字 者 ， 即 堆 顶 元 素 ， 也 就 是 数 组中 的 0号 元 素 。 删 除 之 后 常 将 堆 底 元 素 ， 即 原 来 的 第 （ n 1） 号 关 键 字置 于 堆 顶 处 ， 然 后 元 素 个 数 减 1。 删 除 处 理 后 ， 新 的 序 列 常 常 不 是 堆 了 ， 为

54、此 要 调 整 重 建堆 。 因 为 原 来 已 是 堆 ， 而 现 在 变 更 的 只 是 0号 位 上 的 元 素 ，所 以 只 需 对 0号 位 由 上 往 下 进 行 筛 选 就 可 以 重 建 堆 。 删 除 算 法三 、 堆 的 插 入 与 删 除 删 除 最 小 节 点templat bool MinHeap : RemoveMin(Elem swamp(Heap,0 ,-n); /最 小 节 点 和 最 后 一 个 节 点 交 换 if(n!=0 ) siftdown(0 ); it=Heapn; return true; 75 76 template bool MinHeap

55、:remove(int pos,Elem swap( Heap, pos, -n); /要 删 除 的 节 点 和 最 后 一 个 节 点 交 换 while(pos!=0 ) siftdown(pos); it=Heapn; return true;删 除 某 一 个 节 点 77 5.7 霍 夫 曼 树一 、 树 的 路 径 长 度 （ PL）1、 PL是 指 从 根 到 其 它 各 结 点 的 路 径 长 度 （ 分 支 数 ） 之 和01 43 25 6(a) PL = 137 (b) PL = 1501 43 25 6 7 78 2、 具 有 n个 结 点 的 路 径 长 度 分 析

56、 完 全 二 叉 树 各 结 点 的 路 径 长 度 分 别 是 数 列0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4, 的 前 n项 之 和 ， 具 有最 小 值 10 2 )1(logni iPL 若 n个 结 点 的 高 度 为 h的 二 叉 树 ， 从 根 到 h 1 层都 有 最 多 结 点 数 2h 1 ， 其 余 结 点 分 布 在 第 h 层 的 任意 位 置 上 ， 也 具 有 最 小 PL ， 这 种 树 称 为 理 想 平 衡 二叉 树 。一 、 树 的 路 径 长 度 （ PL） 79 二 、 霍 夫 曼 树1、 树 的 带 权 （ Weight

57、ed） 路 径 长 度 WPL 带 权 的 叶 子 结 点 又 名 外 结 点 ， 具 有 外 结 点 的 树 叫 扩充 二 叉 树 具 有 n个 外 结 点 ， 其 中 任 意 结 点 的 权 值 为 Wi， 到 根 的路 径 长 度 为 li ， 则 该 扩 充 二 叉 树 的 带 权 路 径 长 度 为 ： 具 有 最 小 WPL 的 扩 充 二 叉 树 叫 霍 夫 曼 树 10ni ii lWWPL2 4 5 7 (a) WPL = 36 (b) WPL = 462 4 5 7 7 5 2 4(c) WPL = 35 (霍 夫 曼 树 ) 80 2、 霍 夫 曼 树 的 构 造 方 法

58、 将 n个 权 值 视 为 具 有 n棵 扩 充 二 叉 树 的 森 林 F， 然 后 重 复 以下 步 骤 ， 直 到 F中 只 有 一 棵 树 为 止 ： 在 F中 选 根 的 权 值 最 小 的 两 棵 作 为 左 右 子 树 构 造 一 棵 新的 二 叉 树 ， 其 根 的 权 为 左 右 子 树 根 的 权 值 之 和 。 在 F中 删 除 那 两 棵 树 ， 并 把 新 的 二 叉 树 加 入 。二 、 霍 夫 曼 树2 5 4(a)7 ， ， (b)25 47 ， 6 (c)7 ， 625 411 6 (d)7 25 41118 81 三 、 Huffman树 的 实 现temp

59、lateclass HuffNodepublic: virtual int weight()=0 ; virtual bool isLeaf()=0 ; virtual HuffNode* left() const=0 ; virtual void setLeft(HuffNode*)=0 ; virtual HuffNode* right() const=0 ; virtual void setRight(HuffNode*)=0 ; 抽 象 基 类 82 template class LeafNode:public HuffNodeprivate: FreqPair* it;public:

60、 LeafNode(const Elem int weight()return it-weight(); FreqPair* val()return it; bool isLeaf()return true; virtual HuffNode* left()constreturn NULL; virtual void setLeft(HuffNode*) virtual HuffNode*right()constreturn NULL: virtual void setRight(HuffNode*)；三 、 Huffman树 的 实 现叶 结 点 类 83 template class In

61、tlNode:public HuffNodeprivate: HuffNode* lc; HuffNode* rc; int wgt;public: IntlNode(HuffNode* l,HuffNode* r) wgt=l-weight()+r-weight(); lc=l,rc=r; int weight()return wgt; bool isLeaf()return false; HuffNode* left()constreturn lc; void setLeft(HuffNode*b) lc=(HuffNode*)b; HuffNode*right()constreturn

62、rc: void setRight(HuffNode*b) rc=(HuffNode*)b; 三 、 Huffman树 的 实 现内 部 结 点 类 84 template class FreqPairprivate: Elem it; int freq;public: FreqPair(const Elem freq=f; FreqPair() int weight()return freq; Elem;三 、 Huffman树 的 实 现元 素 /频 率 对 的 类 85 templateclass HuffTreeprivate: HuffNode* theroot;public: Hu

63、ffTree(Elem HuffTree(HuffTree* l,HuffTree*r) theroot=new IntlNode(l-root(), r-root(); HuffTree() HuffNode * root()return theroot; int weight()return theroot-weight();三 、 Huffman树 的 实 现Huffman树 类 86 templateclass HHComparepublic: static bool lt(HuffTree* x,HuffTree*y) return x-weight()weight(); stati

64、c bool eq(HuffTree* x,HuffTree*y) return x-weight()=y-weight(); static bool gt(HuffTree* x,HuffTree*y) return x-weight()y-weight(); 87 templateHuffTree* buildHuff(SSListHuffTree*,HHCompaire*fl) HuffTree* temp1 ,*temp2 ,*temp3 ; for(fl-setStart();fl-leftLength()+fl-rightLength()1 ; fl-setStart() fl-r

65、emove(temp1 ); fl-remove(temp2 ); temp3 =new HuffTree(temp1 ,temp2 ); fl-insert(temp3 ); delete temp1 ; delete temp2 ; return temp3 ;构 造 霍 夫 曼 树 的 算 法 88 四 、 霍 夫 曼 编 码 霍 夫 曼 树 应 用 事 例1、 最 小 冗 余 编 码 问 题 设 用 0， 1码 来 对 一 串 字 符 信 息 进 行 等 长 编 码 ： T 00， A 01， D 10， S 11 对 于 信 息 串 “ ATTSTATADT ”所 得 到 的 编 码

66、 为 01,00,00,11,00,01,00,01,10,00 共 20位 编 码 字 母 集 合 T， A， D， S出 现 的 频 度 W = 5， 3， 1， 1， 若 采 用 不 等 长 编 码 表 示 T 0， A 10， D 110， S 111 所 得 到 的 编 码 是 10,0,0,111,0,10,0,10,110,0 共 17位 ， 这 是 最 小 冗 余 编 码 。 89 2、 霍 夫 曼 树 编 码 以 字 符 的 频 度 为 权 构 造 霍 夫 曼 树 左 分 支 表 示 0， 右 分 支 表 示 1 从 根 到 各 外 结 点 路 径 上 经 由 的 数字 序 列 构 成 各 字 符 的 编 码3、 霍 夫 曼 树 编 码 的 优 越 性 是 最 小 冗 余 码 非 前 缀 码 码 C i 不 是 码 Cj 的 前 缀 译 码 简 单 唯 一 不 断 从 根 开 始 沿 霍 夫 曼 编 码 树 查 找 。10001110100101100 译 码 得 到 的 只 能 是 报 文 串 ：ATTSTATADT四 、 霍 夫 曼 编 码 霍 夫 曼 树 应 用