PowerPoint 演示文稿

Transcription

1 数据结构与算法 ( 五 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五 国家级规划教材 )

2 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 2

3 的定义 5.1 的概念 的概念 (binary tree) 由结点的有限集合构成 这个有限集合或者为空集 (empty) D B A E G C H F I 或者为由一个根结点 (root) 及两棵互不相交 分别称作这个根的左子树 (left subtree) 和右子树 (right subtree) 的组成的集合 3

4 5.1 的概念 的五种基本形态 可以是空集合, 因此根可以有空的左子树或右子树, 或者左右子树皆为空 (a) 空 (b) 独根 (c) 空右 (d) 空左 (e) 左右都不空 4

5 结点 5 第五章 5.1 的概念 子结点 父结点 最左子结点 若 <k,k > r, 则称 k 是 k 的父结点 ( 或 父母 ), 而 k 则是 k 的子结点 ( 或 儿子 子女 ) 兄弟结点 左兄弟 右兄弟 若有序对 <k,k > 及 <k,k > r, 则称 k 和 k 互为兄弟 分支结点 叶结点 没有子树的结点称作叶结点 ( 或树叶 终端结点 ) 非终端结点称为分支结点 相关术语 D B A E G C H F I

6 6 第五章 边 : 两个结点的有序对, 称作边 路径 路径长度 5.1 的概念 相关术语 除结点 k 0 外的任何结点 k K, 都存在一个结点序列 k 0,k 1,,k s, 使得 k 0 就是树根, 且 k s =k, 其中有序对 <k i-1,k i > r (1 i s) 这样的结点序列称为从根到结点 k 的一条路径, 其路径长度为 s ( 包含的边数 ) 祖先 后代 若有一条由 k 到达 k s 的路径, 则称 k 是 k s 的祖先,k s 是 k 的子孙 D B A E G C H F I

7 5.1 的概念 A 相关术语 B C 层数 : 根为第 0 层 其他结点的层数等于其父结点的层数加 1 深度 : 层数最大的叶结点的层数 D E G H F I 高度 : 层数最大的叶结点的层数加 1 7

8 5.1 的概念 满 如果一棵的任何结点, 或者是树叶, 或者恰有两棵非空子树, 则 此称作满 A B D C E F G H I 8

9 5.1 的概念 最多只有最下面的两层结点度数可以小于 2 最下一层的结点都集中最左边 A 完全 D B E A F C B C D E F G H 9 I J L

10 5.1 的概念 扩充 xal 所有空子树, 都增加空树叶 外部路径长度 E 和内部路径长度 I 满足 :E = I + 2n (n 是内部结点个数 ) wan zol wen wil wim wul xem xul yo yum yon zi zom 10

11 5.1 的概念的主要性质 性质 1. 在中, 第 i 层上最多有 2 i 个结点 (i 0) 性质 2. 深度为 k 的至多有 2 k+1-1 个结点 (k 0) 其中深度 (depth) 定义为中层数最大的叶结点的层数 性质 3. 一棵, 若其终端结点数为 n 0, 度为 2 的结点数为 n 2, 则 n 0 =n 2 +1 性质 4. 满定理 : 非空满树叶数目等于其分支结点数加 1 性质 5. 满定理推论 : 一个非空的空子树数目等于其结点数加 1 性质 6. 有 n 个结点 (n>0) 的完全的高度为 log 2 (n+1) ( 深度为 log 2 (n+1) - 1) 11

12 5.1 的概念 思考 扩充和满的关系 主要六个性质的关系 12

13 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 13

14 5.2 的抽象数据类型抽象数据类型 逻辑结构 + 运算 : 针对整棵树 初始化 合并两棵 围绕结点 访问某个结点的左子结点 右子结点 父结点 访问结点存储的数据 14

15 5.2 的抽象数据类型 结点 ADT template <class T> class BinaryTreeNode { friend class BinaryTree<T>; // 声明类为友元类 private: T info; // 结点数据域 public: BinaryTreeNode(); // 缺省构造函数 BinaryTreeNode(const T& ele); // 给定数据的构造 BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l, BinaryTreeNode<T> *r); // 子树构造结点 15

16 5.2 的抽象数据类型 }; T value() const; BinaryTreeNode<T>* leftchild() const; BinaryTreeNode<T>* rightchild() const; void setleftchild(binarytreenode<t>*); void setrightchild(binarytreenode<t>*); void setvalue(const T& val); bool isleaf() const; BinaryTreeNode<T>& operator = (const BinaryTreeNode<T>& Node); // 返回当前结点数据 // 返回左子树 // 返回右子树 // 设置左子树 // 设置右子树 // 设置数据域 // 判断是否为叶结点 // 重载赋值操作符 16

17 5.2 的抽象数据类型 ADT template <class T> class BinaryTree { private: BinaryTreeNode<T>* root; // 根结点 public: BinaryTree() {root = NULL;}; // 构造函数 ~BinaryTree() {DeleteBinaryTree(root);}; // 析构函数 bool isempty() const; // 判定是否为空树 BinaryTreeNode<T>* Root() {return root;}; // 返回根结点 }; 17

18 5.2 的抽象数据类型 BinaryTreeNode<T>* Parent(BinaryTreeNode<T> *current); // 返回父 BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T> *current);// 左兄 BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T> *current); // 右兄 void CreateTree(const T& info, BinaryTree<T>& lefttree, BinaryTree<T>& righttree); // 构造新树 void PreOrder(BinaryTreeNode<T> *root); // 前序遍历或其子树 void InOrder(BinaryTreeNode<T> *root); // 中序遍历或其子树 void PostOrder(BinaryTreeNode<T> *root); // 后序遍历或其子树 void LevelOrder(BinaryTreeNode<T> *root); // 按层次遍历或其子树 void DeleteBinaryTree(BinaryTreeNode<T> *root); // 删除或其子树 18

19 5.2 的抽象数据类型 遍历 遍历 ( 或称周游,traversal) 系统地访问数据结构中的结点 每个结点都正好被访问到一次 的结点的线性化 19

20 5.2 的抽象数据类型 深度优先遍历 三种深度优先遍历的递归定义 : (1) 前序法 (tlr 次序,preorder traversal) 访问根结点 ; 按前序遍历左子树 ; 按前序遍历右子树 (2) 中序法 (LtR 次序,inorder traversal) 按中序遍历左子树 ; 访问根结点 ; 按中序遍历右子树 (3) 后序法 (LRt 次序,postorder traversal) 按后序遍历左子树 ; 按后序遍历右子树 ; 访问根结点 20

21 5.2 的抽象数据类型 深度优先遍历 B A C 前序序列是 :A B D E G C F H I 中序序列是 :D B G E A C H F I 后序序列是 :D G E B H I F C A D E F G H I 21

22 22 第五章 5.2 的抽象数据类型 表达式 前序 ( 前缀 ): - + * a b c * a + b c 中序 : a * b + c - a * b + c 后序 ( 后缀 ) :a b * c + a b c + * * * c a a b b + c

23 template<class T> 5.2 的抽象数据类型 深度优先遍历 ( 递归 ) void BinaryTree<T>::DepthOrder (BinaryTreeNode<T>* root) { if(root!=null) { Visit(root); DepthOrder(root->leftchild()); Visit(root); DepthOrder(root->rightchild()); // 前序 // 递归访问左子树 // 中序 // 递归访问右子树 } } Visit(root); // 后序 23

24 5.2 的抽象数据类型 思考 前 中 后序哪几种结合可以恢复的结构? 已知某的中序序列为 {A, B, C, D, E, F, G}, 后序序列为 {B, D, C, A, F, G, E}; 则其前序序列为 24

25 5.2 的抽象数据类型 DFS 遍历的非递归算法 递归算法非常简洁 推荐使用 当前的编译系统优化效率很不错了 特殊情况用栈模拟递归 理解编译栈的工作原理 理解深度优先遍历的回溯特点 有些应用环境资源限制不适合递归 25

26 5.2 的抽象数据类型 B 入栈序列 A C C F G I 非递归前序遍历 D E F 栈 C G 访问结点 G H I 栈中结点 26 已访问结点

27 思想 : 5.2 的抽象数据类型非递归前序遍历 遇到一个结点, 就访问该结点, 并把此结点的非空右结点推入栈中, 然后下降去遍历它的左子树 ; 遍历完左子树后, 从栈顶托出一个结点, 并按照它的右链接指示的地址再去遍历该结点的右子树结构 template<class T> void BinaryTree<T>::PreOrderWithoutRecusion (BinaryTreeNode<T>* root) { 27

28 28 第五章 5.2 的抽象数据类型 using std::stack; // 使用 STL 中的 stack stack<binarytreenode<t>* > astack; BinaryTreeNode<T>* pointer=root; astack.push(null); // 栈底监视哨 while(pointer) { // 或者!aStack.empty() Visit(pointer->value()); // 访问当前结点 if (pointer->rightchild()!= NULL) // 右孩子入栈 astack.push(pointer->rightchild()); if (pointer->leftchild()!= NULL) pointer = pointer->leftchild(); // 左路下降 else { // 左子树访问完毕, 转向访问右子树 pointer = astack.top(); astack.pop(); // 栈顶元素退栈 } } }

29 5.2 的抽象数据类型 中序序列进栈序列 A A B D C E G F H I B C 栈 A B E D D E G H F I 未访问结点栈中结点出栈结点 29

30 5.2 的抽象数据类型非递归中序遍历 遇到一个结点 把它推入栈中 遍历其左子树 遍历完左子树 从栈顶托出该结点并访问之 按照其右链地址遍历该结点的右子树 30

31 5.2 的抽象数据类型 template<class T> void BinaryTree<T>::InOrderWithoutRecusion(BinaryTreeNode<T>* root) { using std::stack; // 使用 STL 中的 stack stack<binarytreenode<t>* > astack; BinaryTreeNode<T>* pointer = root; while (!astack.empty() pointer) { if (pointer ) { // Visit(pointer->value()); // 前序访问点 astack.push(pointer); // 当前结点地址入栈 // 当前链接结构指向左孩子 pointer = pointer->leftchild(); 31

32 5.2 的抽象数据类型 } } //end if else { 32 // 左子树访问完毕, 转向访问右子树 pointer = astack.top(); astack.pop(); Visit(pointer->value()); // 当前链接结构指向右孩子 pointer=pointer->rightchild(); } //end else } //end while // 栈顶元素退栈 // 访问当前结点

33 5.2 的抽象数据类型非递归后序遍历 左子树返回 vs 右子树返回? 给栈中元素加上一个特征位 Left 表示已进入该结点的左子树, 将从左边回来 Right 表示已进入该结点的右子树, 将从右边回来 33

34 5.2 的抽象数据类型 后序序列 出栈序列 D B G (D,L) (D,R) (B,L) (B,R) (H,R) E H I F C A (A,L) (E,L) (G,L) (G,R) (E,R) (C,L) (H,L) (I,R) (I,L) A (F,R) (F,L) B C 栈 (C,R) (A,R) D 未访问结点 E F 栈中结点 G H I 出栈结点 34

35 35 第五章 5.2 的抽象数据类型 非递归后序遍历算法 enum Tags{Left,Right}; // 定义枚举类型标志位 template <class T> class StackElement { // 栈元素的定义 public: BinaryTreeNode<T>* pointer; // 指向结点的指针 Tags tag; // 标志位 }; template<class T> void BinaryTree<T>::PostOrderWithoutRecursion(BinaryTreeNode<T>* root) { using std::stack; // 使用 STL 的栈 StackElement<T> element; stack<stackelement<t > > astack; BinaryTreeNode<T>* pointer; pointer = root;

36 5.2 的抽象数据类型 while (!astack.empty() pointer) { while (pointer!= NULL) { // 沿非空指针压栈, 并左路下降 element.pointer = pointer; element.tag = Left; astack.push(element); // 把标志位为 Left 的结点压入栈 pointer = pointer->leftchild(); } element = astack.top(); astack.pop(); // 获得栈顶元素, 并退栈 pointer = element.pointer; if (element.tag == Left) { // 如果从左子树回来 element.tag = Right; astack.push(element); // 置标志位为 Right pointer = pointer->rightchild(); } else { // 如果从右子树回来 Visit(pointer->value()); // 访问当前结点 pointer = NULL; // 置 point 指针为空, 以继续弹栈 } } } 36

37 5.2 的抽象数据类型 遍历算法的时间代价分析 在各种遍历中, 每个结点都被访问且只被访问一次, 时间代价为 O(n) 非递归保存入出栈 ( 或队列 ) 时间 前序 中序, 某些结点入 / 出栈一次, 不超过 O(n) 后序, 每个结点分别从左 右边各入 / 出一次, O(n) 37

38 5.2 的抽象数据类型 遍历算法的空间代价分析 深搜 : 栈的深度与树的高度有关 最好 O(log n) 最坏 O(n) 38

39 5.2 的抽象数据类型 思考 非递归遍历的意义? 后序遍历时, 栈中结点有何规律? 栈中存放了什么? 前序 中序 后序框架的算法通用性? 例如后序框架是否支持前序 中序访问? 若支持, 怎么改动? 39

40 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 40

41 5.2 的抽象数据类型 宽度优先遍历 从的第 0 层 ( 根结点 ) 开始, 自上至下逐层遍历 ; 在同一层中, 按照从左到右的顺序对结点逐一访问 例如 :A B C D E F G H I A B C D E F 41 G H I

42 BFS 序列 5.2 的抽象数据类型宽度优先遍历 队列 B A A B C D E F G H I C 访问中结点队列中结点已访问结点 D E F 42 G H I

43 43 第五章 宽度优先遍历算法 void BinaryTree<T>::LevelOrder(BinaryTreeNode<T>* root){ using std::queue; // 使用 STL 的队列 queue<binarytreenode<t>*> aqueue; BinaryTreeNode<T>* pointer = root; // 保存输入参数 if (pointer) aqueue.push(pointer); // 根结点入队列 while (!aqueue.empty()) { // 队列非空 pointer = aqueue.front(); // 取队列首结点 aqueue.pop(); // 当前结点出队列 Visit(pointer->value()); // 访问当前结点 if(pointer->leftchild()) aqueue.push(pointer->leftchild()); // 左子树进队列 if(pointer->rightchild()) aqueue.push(pointer->rightchild());// 右子树进队列 } }

44 5.2 的抽象数据类型 遍历算法的时间代价分析 在各种遍历中, 每个结点都被访问且只被访问一次, 时间代价为 O(n) 非递归保存入出栈 ( 或队列 ) 时间 宽搜, 正好每个结点入 / 出队一次,O(n) 44

45 5.2 的抽象数据类型 遍历算法的空间代价分析 宽搜 : 与树的最大宽度有关 最好 O(1) 最坏 O(n) 45

46 5.2 的抽象数据类型 思考 试比较宽搜与非递归前序遍历算法框架 46

47 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 47

48 5.3 的存储结构的链式存储结构 的各结点随机地存储在内存空间中, 结点之间的逻辑关系用指针来链接 二叉链表 指针 left 和 right, 分别指向结点的左孩子和右孩子 left info right 三叉链表 指针 left 和 right, 分别指向结点的左孩子和右孩子 增加一个父指针 48 left info parent right

49 5.3 的存储结构 二叉链表 t D B A E C F G H I A B C D E F G H I 49 (a) (b)

50 第五章 5.3 的存储结构 三叉链表 指向父母的指针 parent, 向上 能力 t D A B E G C F H I A B C D E F G H I 50 (a) (b)

51 5.3 的存储结构 51 BinaryTreeNode 类中增加两个私有数据成员 private: BinaryTreeNode<T> *left; BinaryTreeNode<T> *right; template <class T> class BinaryTreeNode { friend class BinaryTree<T>; // 声明类为友元类 private: T info; // 结点数据域 public: BinaryTreeNode(); // 缺省构造函数 BinaryTreeNode(const T& ele); // 给定数据的构造 BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l, BinaryTreeNode<T> *r); // 子树构造结点. } // 指向左子树的指针 // 指向右子树的指针

52 5.3 的存储结构递归框架寻找父结点 注意返回 template<class T> BinaryTreeNode<T>* BinaryTree<T>:: Parent(BinaryTreeNode<T> *rt, BinaryTreeNode<T> *current) { BinaryTreeNode<T> *tmp, if (rt == NULL) return(null); if (current == rt ->leftchild() current == rt->rightchild()) return rt; // 如果孩子是 current 则返回 parent if ((tmp =Parent(rt- >leftchild(), current)!= NULL) return tmp; if ((tmp =Parent(rt- > rightchild(), current)!= NULL) return tmp; return NULL; } 52

53 5.3 的存储结构 思考 该算法是什么框架? 该算法是什么序遍历? 可以怎样改进? 可以用非递归吗? 可以用 BFS 吗? 怎样从这个算法出发, 寻找兄弟结点 53

54 5.3 的存储结构 非递归框架找父结点 BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *current) { using std::stack; // 使用 STL 中的栈 stack<binarytreenode<t>* > astack; BinaryTreeNode<T> *pointer = root; astack.push(null); // 栈底监视哨 while (pointer) { // 或者!aStack.empty() if (current == pointer->leftchild() current == pointer->rightchild()) return pointer; // 如果 pointer 的孩子是 current 则返回 parent if (pointer->rightchild()!= NULL) // 非空右孩子入栈 astack.push(pointer->rightchild()); if (pointer->leftchild()!= NULL) pointer = pointer->leftchild(); // 左路下降 else { // 左子树访问完毕, 转向访问右子树 pointer=astack.top(); astack.pop(); // 获得栈顶元素, 并退栈 } } } 54

55 5.3 的存储结构 空间开销分析 存储密度 ( 1) 表示数据结构存储的效率 ( 存储密度 ) 数据本身存储量整个结构占用的存储总量 结构性开销 = 1-55

56 5.3 的存储结构 空间开销分析 根据满定理 : 一半的指针是空的 t A 每个结点存两个指针 一个数据域 B C 总空间 (2p + d)n 结构性开销 :2pn D E F G H I 如果 p = d, 则结构性开销 2p/ (2p + d ) = 2/3 (a) (b) 56

57 5.3 的存储结构空间开销分析 C++ 可以用两种方法来实现不同的分支与叶结点 : 用 union 联合类型定义 使用 C++ 的子类来分别实现分支结点与叶结点, 并采用虚函数 isleaf 来区别分支结点与叶结点 早期节省内存资源 利用结点指针的一个空闲位 ( 一个 bit) 来标记结点所属的类型 利用指向叶的指针或者叶中的指针域来存储该叶结点的值 57

58 5.3 的存储结构 完全的下标公式 从结点的编号就可以推知其父母 孩子 兄弟的编号 当 2i+1<n 时, 结点 i 的左孩子是结点 2i+1, 否则结点 i 没有左孩子 当 2i+2<n 时, 结点 i 的右孩子是结点 2i+2, 否则结点 i 没有右孩子 58

59 5.3 的存储结构 完全的下标公式 当 0<i<n 时, 结点 i 的父亲是结点 (i-1)/2 7 8 当 i 为偶数且 0<i<n 时, 结点 i 的左兄弟是结点 i-1, 否则结点 i 没有左兄弟 当 i 为奇数且 i+1<n 时, 结点 i 的右兄弟是结点 i+1, 否则结点 i 没有右兄弟 59

60 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 60

61 5.4 二叉搜索树 二叉搜索树 Binary Search Tree(BST) 或者是一棵空树 ; 或者是具有下列性质的 : 对于任何一个结点, 设其值为 K 则该结点的左子树 ( 若不空 ) 的任意一个结点的值都小于 K; 该结点的右子树 ( 若不空 ) 的任意一个结点的值都大于 K; 而且它的左右子树也分别为 BST 性质 : 中序遍历是正序的 ( 由小到大的排列 ) 61

62 wan 第五章 5.4 二叉搜索树 BST 示意图 xal zol wen wil wim xul yo yum zom wul xem yon zi 62

63 5.4 二叉搜索树 检索 19 只需检索二个子树之一 直到 K 被找到 或遇上树叶仍找不到, 则不存在

64 5.4 二叉搜索树 插入 17 首先是检索, 若找到则不允许插入 若失败, 则在该位置插入一个新叶 保持 BST 性质和性能!

65 wan 第五章 xal zol wen wil wim wul xul xem yo yum yon zom zi zoo 删除 wan 删除 zol 65

66 5.4 二叉搜索树 BST 删除 ( 值替换 ) void BinarySearchTree<T>:::removehelp(BinaryTreeNode <T> *& rt, const T val) { if (rt==null) cout<<val<<" is not in the tree.\n"; else if (val < rt->value()) C removehelp(rt->leftchild(), val); else if (val > rt->value()) removehelp(rt->rightchild(), val); B else { // 真正的删除 BinaryTreeNode <T> * temp = rt; A if (rt->leftchild() == NULL) rt = rt->rightchild(); D else if (rt->rightchild() == NULL) rt = rt->leftchild(); else { F temp = deletemin(rt->rightchild()); E rt->setvalue(temp->value()); } delete temp; } } 66 G H J I K

67 5.4 二叉搜索树 67 找 rt 右子树中最小结点, 并删除 template <class T> BinaryTreeNode* BST::deletemin(BinaryTreeNode <T> *& rt) { if (rt->leftchild()!= NULL) return deletemin(rt->leftchild()); else { // 找到右子树中最小, 删除 B BinaryTreeNode <T> *temp = rt; rt = rt->rightchild(); A return temp; } } C D F E G H J I K

68 5.4 二叉搜索树二叉搜索树总结 组织内存索引 二叉搜索树是适用于内存储器的一种重要的树形索引 常用红黑树 伸展树等, 以维持平衡 外存常用 B/B+ 树 保持性质 vs 保持性能 插入新结点或删除已有结点, 要保证操作结束后仍符合二叉搜索树的定义 68

69 5.4 二叉搜索树 思考 怎样防止 BST 退化为线性结构?

70 5.4 二叉搜索树 思考 120 允许重复关键码吗? 插入 检索 删除

71 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 71

72 第五章 顺序方法存储 5.3 的存储结构 完全的顺序存储结构 把结点按一定的顺序存储到一片连续的存储单元使结点在序列中的位置反映出相应的结构信息 存储结构上是线性的 逻辑结构上它仍然是形结构

73 5.3 的存储结构 完全的下标公式 从结点的编号就可以推知其父母 孩子 兄弟的编号 当 2i+1<n 时, 结点 i 的左孩子是结点 2i+1, 否则结点 i 没有左孩子 当 2i+2<n 时, 结点 i 的右孩子是结点 2i+2, 否则结点 i 没有右孩子 73

74 5.3 的存储结构 完全的下标公式 当 0<i<n 时, 结点 i 的父亲是结点 (i-1)/2 7 8 当 i 为偶数且 0<i<n 时, 结点 i 的左兄弟是结点 i-1, 否则结点 i 没有左兄弟 当 i 为奇数且 i+1<n 时, 结点 i 的右兄弟是结点 i+1, 否则结点 i 没有右兄弟 74

75 5.4 二叉搜索树 思考 用三叉链的存储形式修改的相应算法 特别注意插入和删除结点, 维护父指针信息 完全三叉树的下标公式? 75

76 5.5 堆与优先队列 堆的定义及其实现 最小堆 : 最小堆是一个关键码序列 { K 0,K 1, K n-1 }, 它具有如下特性 : K i K 2i+1 (i=0,1,, n/2-1) K i K 2i 十 2 类似可以定义最大堆

77 5.5 堆与优先队列 堆的性质 完全的层次序列, 可以用数组表示 堆中储存的数是局部有序的, 堆不唯一 结点的值与其孩子的值之间存在限制 任何一个结点与其兄弟之间都没有直接的限制 从逻辑角度看, 堆实际上是一种树形结构 77

78 5.5 堆与优先队列 堆的类定义 template <class T> class MinHeap { // 最小堆 ADT 定义 private: T* heaparray; // 存放堆数据的数组 int CurrentSize; // 当前堆中元素数目 int MaxSize; // 堆所能容纳的最大元素数目 void BuildHeap(); // 建堆 public: MinHeap(const int n); // 构造函数,n 为最大元素数目 virtual ~MinHeap(){delete []heaparray;}; // 析构函数 bool isleaf(int pos) const; // 如果是叶结点, 返回 TRUE int leftchild(int pos) const; // 返回左孩子位置 int rightchild(int pos) const; // 返回右孩子位置 int parent(int pos) const; // 返回父结点位置 bool Remove(int pos, T& node); // 删除给定下标的元素 bool Insert(const T& newnode); // 向堆中插入新元素 newnode T& RemoveMin(); // 从堆顶删除最小值 void SiftUp(int position); // 从 position 向上开始调整, 使序列成为堆 void SiftDown(int left); // 筛选法函数, 参数 left 表示开始处理的数组下标 } 78

79 5.5 堆与优先队列 对最小堆用筛选法 SiftDown 调整 template <class T> void MinHeap<T>::SiftDown(int position) { int i = position; // 标识父结点 int j = 2*i+1; // 标识关键值较小的子结点 Ttemp = heaparray[i]; // 保存父结点

80 } 80 第五章 5.5 堆与优先队列 对最小堆用筛选法 SiftDown 调整 while (j < CurrentSize) { if((j < CurrentSize-1)&& (heaparray[j] > heaparray[j+1])) j++; // j 指向数值较小的子结点 if (temp > heaparray[j]) { heaparray[i] = heaparray[j]; i = j; j = 2*j + 1; } else break; } heaparray[i]=temp; // 向下继续

81 5.5 堆与优先队列 对最小堆用筛选法 SiftUp 向上调整 template<class T> void MinHeap<T>::SiftUp(int position) { // 从 position 向上开始调整, 使序列成为堆 int temppos=position; // 不是父子结点直接 swap T temp=heaparray[temppos]; while((temppos>0) && (heaparray[parent(temppos)] > temp)) { heaparray[temppos]=heaparray[parent(temppos)]; temppos=parent(temppos); } heaparray[temppos]=temp;// 找到最终位置 } 81

82 82 第五章 5.5 堆与优先队列 4 0 建最小堆过程 首先, 将 n 个关键码放到一维数组中 整体不是最小堆 所有叶结点子树本身是堆 当 i n/2 时, 以关键码 K i 为根的子树已经是堆 从倒数第二层,i = n/2-1 开始从右至左依次调整 直到整个过程到达树根 整棵完全就成为一个堆

83 5.5 堆与优先队列 72?23 < 05?72 < 05?23 < 94?73 < 23? 23 < 68? 73 < ? 72 < ?16 < 05?71 < i=0 i=1 i=2 i= 建最小堆过程示意图

84 5.5 堆与优先队列 建最小堆 从第一个分支结点 heaparray[currentsize/2-1] 开始, 自底向上逐步把以子树调整成堆 template<class T> void MinHeap<T>::BuildHeap() { // 反复调用筛选函数 for (int i=currentsize/2-1; i>=0; i--) SiftDown(i); } 84

85 5.5 堆与优先队列 最小堆插入新元素 16 1 template <class T> bool MinHeap<T>::Insert(const T& newnode) 2 28 // 向堆中插入新元素 newnode { if(currentsize==maxsize) 31 3 // 堆空间已经满 return false; heaparray[currentsize]=newnode; SiftUp(CurrentSize); // 向上调整 CurrentSize++; }

86 86 第五章 5.5 堆与优先队列 最小堆删除元素操作 template<class T> bool MinHeap<T>::Remove(int pos, T& node) { if((pos<0) (pos>=currentsize)) return false; T temp=heaparray[pos]; heaparray[pos]=heaparray[--currentsize]; if (heaparray[parent(pos)]> heaparray[pos]) SiftUp(pos); // 上升筛 else SiftDown(pos); // 向下筛 node=temp; return true; }

87 5.5 堆与优先队列 删除

88 5.5 堆与优先队列 删除

89 5.5 堆与优先队列 建堆效率分析 n 个结点的堆, 高度 d = log 2 n + 1 根为第 0 层, 则第 i 层结点个数为 2 i, 考虑一个元素在堆中向下移动的距离 大约一半的结点深度为 d-1, 不移动 ( 叶 ) 四分之一的结点深度为 d-2, 而它们至多能向下移动一层 树中每向上一层, 结点的数目为前一层的一半, 而子树高度加一 因而元素移动的最大距离的总数为 log n n ( i 1) O( n) i i

90 5.5 堆与优先队列 最小堆操作效率 建堆算法时间代价为 (n) 堆有 log n 层深 插入结点 删除普通元素和删除最小元素的平均 时间代价和最差时间代价都是 (log n) 90

91 5.5 堆与优先队列优先队列 堆可以用于实现优先队列 优先队列 根据需要释放具有最小 ( 大 ) 值的对象 最大树 左高树 HBLT WBLT MaxWBLT 改变已存储于优先队列中对象的优先权 辅助数据结构帮助找到对象 91

92 5.5 堆与优先队列 思考 在向下筛选 SiftDown 操作时, 若一旦发现逆序对, 就交换会怎么样? 能否在一个数据结构中同时维护最大值和最小值?( 提示 : 最大最小堆 ) 92

93 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 93

94 计算机二进制编码 ASCII 码 中文编码 5.6 Huffman 树及其应用等长编码 等长编码 假设所有编码都等长表示 n 个不同的字符需要 log 2 n 位 字符的使用频率相等 空间效率 94

95 5.6 Huffman 树及其应用数据压缩和不等长编码 频率不等的字符 Z K F C U D L E 可以利用字符的出现频率来编码 经常出现的字符的编码较短, 不常出现的字符编码较长 数据压缩既能节省磁盘空间, 又能提高运算速度 ( 外存时空权衡的规则 ) 95

96 5.6 Huffman 树及其应用前缀编码 任何一个字符的编码都不是另外一个字符编码的前缀 这种前缀特性保证了代码串被反编码时, 不会有多种可能 例如 右图是一种前缀编码, 对于 , 可以翻译出唯一的字符串 EEEL 若编码为 Z(00), K(01), F(11), C(0), U(1), D(10), L(110), E(010) 则对应 : ZKD, CCCUUC 等多种可能 96 编码 Z(111100), K(111101), F(11111), C(1110), U(100), D(101), L(110), E(0)

97 5.6 Huffman 树及其应用 Huffman 树与前缀编码 Huffman 编码将代码与字符相联系 不等长编码 代码长度取决于对应字符的相对使用 频率或 权 97

98 98 第五章 5.6 Huffman 树及其应用 建立 Huffman 编码树 对于 n 个字符 K 0,K 1,,K n-1, 它们的使用频率分别为 w 0, w 1,,w n-1, 给出它们的前缀编码, 使得总编码效率最高 给出一个具有 n 个外部结点的扩充 该每个外部结点 K i 有一个权 w i 外部路径长度为 l i 这个扩充的叶结点带权外部路径长度总和 权越大的叶结点离根越近 n 1 wi li i 0

99 5.6 Huffman 树及其应用建立 Huffman 编码树 首先, 按照 权 ( 例如频率 ) 将字符排为一列 接着, 拿走前两个字符 ( 权 最小的两个字符 ) 再将它们标记为 Huffman 树的树叶, 将这两个树叶标为一个分支结点的两个孩子, 而该结点的权即为两树叶的权之和 将所得 权 放回序列, 使 权 的顺序保持 重复上述步骤直至序列处理完毕 99

100 100 第五章 d 7 d 8 0 d 4 1 d Huffman 树及其应用 d 9 31 d d d d d d 11 d d 1

101 5.6 Huffman 树及其应用 频率越大其编码越短 各字符的二进制编码为 : d 0 : d 1 : d 2 : d 3 : d 4 : 0100 d 5 : 0101 d 6 : 1010 d 7 : 000 d 8 : 001 d 9 : 011 d 10 : 100 d 11 : 110 d 12 : d 7 d d 4 d 5 d 9 31 d d d d 2 d d 11 d d 1 101

102 5.6 Huffman 树及其应用 译码 : 从左至右逐位判别代码串, 直至确定一个字符 与编码过程相逆 从树的根结点开始 0 下降到左分支 1 下降到右分支 到达一个树叶结点, 对应的字符就是文本信息的字符 连续译码 译出了一个字符, 再回到树根, 从二进制位串中的下一位开始继续译码 d 7 d d 4 d 5 d 9 31 d d d d 2 d d 11 d d 1 102

103 103 第五章 译码 : d 7 d 8 0 d 4 1 d 5 d 9 31 d d d d d d 11 d d 12 d 1

104 5.6 Huffman 树及其应用 Huffman 树类 template <class T> class HuffmanTree { private: HuffmanTreeNode<T>* root;//huffman 树的树根 // 把 ht1 和 ht2 为根的合并成一棵以 parent 为根的 Huffman 子树 void MergeTree(HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T>* parent); public: // 构造 Huffman 树,weight 是存储权值的数组,n 是数组长度 HuffmanTree(T weight[],int n); virtual ~HuffmanTree(){DeleteTree(root);}; // 析构函数 } 104

105 5.6 Huffman 树及其应用 Huffman 树的构造 template<class T> HuffmanTree<T>::HuffmanTree(T weight[], int n) { MinHeap<HuffmanTreeNode<T>> heap; // 定义最小值堆 HuffmanTreeNode<T> *parent,&leftchild,&rightchild; HuffmanTreeNode<T>* NodeList = new HuffmanTreeNode<T>[n]; for(int i=0; i<n; i++) { NodeList[i].element =weight[i]; NodeList[i].parent = NodeList[i].left = NodeList[i].right = NULL; heap.insert(nodelist[i]); // 向堆中添加元素 } //end for 105

106 5.6 Huffman 树及其应用 Huffman 树的构造 for(i=0;i<n-1;i++) { // 通过 n-1 次合并建立 Huffman 树 parent=new HuffmanTreeNode<T>; firstchild=heap. RemoveMin(); // 选值最小的结点 secondchild=heap. RemoveMin(); // 选值次小的结点 MergeTree(firstchild,secondchild,parent); // 合并权值最小的两棵树 heap.insert(*parent); // 把 parent 插入到堆中去 root=parent; // 建立根结点 }//end for delete []NodeList; } 106

107 5.6 Huffman 树及其应用 Huffman 方法的正确性证明 是否前缀编码? 贪心法的一个例子 Huffman 树建立的每一步, 权 最小的两个子树被结合为一新子树 是否最优解? 107

108 5.6 Huffman 树及其应用 Huffman 性质 引理含有两个以上结点的一棵 Huffman 树中, 字符使用频率最小的两个字符是兄弟结点, 而且其深度不比树中其他任何叶结点浅 108

109 5.6 Huffman 树及其应用 证明 记使用频率最低的两个字符为 y1 和 y2 假设 x1, x2 是最深的结点 y1 和 y2 的父结点 Y 一定会有比 X 更大的 权 否则, 会选择 Y 而不是 X 作为结点 V 的子结点 Y V 然而, 由于 y1 和 y2 是频率最小的字符, 这种情况不可能发生 y1 y2 X x1 x2 109

110 5.6 Huffman 树及其应用 定理 : 对于给定的一组字符, 函数 HuffmanTree 实现了 最小外部路径权重 证明 : 对字符个数 n 作归纳进行证明 初始情况 : 令 n = 2, Huffman 树一定有最小外部路径权重 只可能有成镜面对称的两种树 两种树的叶结点加权路径长度相等 归纳假设 : 假设有 n-1 个叶结点的由函数 HuffmanTree 产生的 Huffman 树有最小外部路径权重 110

111 第五章 归纳步骤 : 5.6 Huffman 树及其应用 设一棵由函数 HuffmanTree 产生的树 T 有 n 个叶结 点,n 2, 并假设字符的 权 w 0 w 1 w n 记 V 是频率为 w 0 和 w 1 的两个字符的父结点 根据引理, 它们已经是树 T 中最深的结点 T 中结点 V 换为一个叶结点 V ( 权等于 w 0 + w 1 ), 得到另一棵树 T 根据归纳假设,T 具有最小的外部路径长度 把 V 展开为 V( w 0 + w 1 ), T 还原为 T, 则 T 也应该有最小的外部路径长度 因此, 根据归纳原理, 定理成立

112 5.6 Huffman 树及其应用 Huffman 树编码效率 估计 Huffman 编码所节省的空间 平均每个字符的代码长度等于每个代码的长度 c i 乘以其出现的概率 p i, 即 : c 0 p 0 + c 1 p c n-1 p n-1 或 (c 0 f 0 + c 1 f c n-1 f n-1 ) / f T 这里 f i 为第 i 个字符的出现频率, 而 f T 为所有字符出现的总次数 112

113 5.6 Huffman 树及其应用 Huffman 树编码效率 ( 续 ) 图中, 平均代码长度为 : (3*( ) + 4*( ) + 5*7 + 6*5 + 7*(2+3)) / 238 = 804/ 对于这 13 个字符, 等长编码每个字符需要 d 7 d 8 log 13 = 4 位, 而 Huffman 编码只需 3.38 位 Huffman 编码预计只需要等长编码 3.38/4 84% 的空间 d 4 d 5 d d d 11 d d d d d d 1 113

114 5.6 Huffman 树及其应用 Huffman 树的应用 Huffman 编码适合于字符频率不等, 差别较大的情况 数据通信的二进制编码 不同的频率分布, 会有不同的压缩比率 大多数的商业压缩程序都是采用几种编码方式以应付各种类型的文件 Zip 压缩就是 LZ77 与 Huffman 结合 归并法外排序, 合并顺串 114

115 5.6 Huffman 树及其应用 当外部的数目不能构成满 b 叉 Huffman 树时, 需附加多少个权为 0 的 虚 结点? 请推导 R 个外部结点,b 叉树 思考 若 (r-1)% (b-1)==0, 则不需要加 虚 结点 否则需要附加 b -(r-1)% (b-1) - 1 个 虚 结点 即第一次选取 (r-1)% (b-1) + 1 个非 0 权值 试调研常见压缩软件所使用的编码方式 115

116 编制一个将百分制转换成五分制的程序, 怎样才能使得程序中的比较次数最少? 成绩分布如下 : 5.6 Huffman 树及其应用思考 分数 比例数

117 0.05+2*0.15+3*0.4+( )*4 =3.15 比较判断次数 *2+0.15*3+( )*4 =2.05 A<60 Y N 不及格 A<70 Y N 及格 A<80 Y N 中等 A<90 Y N 70<=A<80 Y N 中等 80<=A<90 Y N 良好 60<=A<70 N Y A<60 及格 Y N 良好 优秀 不及格 优秀 117

118 数据结构与算法 谢谢聆听 国家精品课 数据结构与算法 张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五 国家级规划教材