PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

铸林
6 years ago
Views:

数据结构与算法 ( 五 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008.

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

PowerPoint 演示文稿

PowerPoint 演示文稿数据结构与算法 ( 五 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第五章的概念的抽象数据类型深度优先搜索宽度优先搜索的存储结构 D B A E G C H F I 二叉搜索树堆与优先队列 Huffman 树及其应用 2 5.2