PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

乙粹随徐
7 years ago
Views:

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

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

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

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

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

6 5.1 的概念 A 相关术语 B C 边 : 两个结点的有序对, 称作边路径路径长度除结点 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 E G H F I 6

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

8 5.1 的概念满如果一棵的任何结点, 或者是树叶, 或者恰有两棵非空子树, 则此称作满 A C B D 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 A 的概念第五章 B C 的抽象数据类型深度优先搜索宽度优先搜索的存储结构 D E G 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 5.2 的抽象数据类型 22 表达式前序 ( 前缀 ): - + * 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 5.2 的抽象数据类型 template<class T> 深度优先遍历 ( 递归 ) 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 的抽象数据类型 A C B F D G I E H D B A E C F 非递归前序遍历 CF I G 栈访问结点 26 G H I 栈中结点已访问结点

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

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(); // 栈顶元素退栈 } } } 28

29 5.2 的抽象数据类型中序序列进栈序列 A A B D C E G F H I B C 栈 AC IF BE GH 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 { // 左子树访问完毕, 转向访问右子树 pointer = astack.top(); astack.pop(); // 栈顶元素退栈 Visit(pointer->value()); // 访问当前结点 // 当前链接结构指向右孩子 pointer=pointer->rightchild(); } //end else } //end while } 32

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

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

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

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

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

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

39 39 第五章 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;

40 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()); // 访问当前结点 40 pointer = NULL; // 置 point 指针为空, 以继续弹栈

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

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

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

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

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

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

47 宽度优先遍历算法 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());// 右子树进队列 } } 47

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

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

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

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

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

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

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

55 5.3 的存储结构 55 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); // 子树构造结点

56 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; } 56

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

58 58 第五章 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(); // 获得栈顶元素, 并退栈 } } }

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

60 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) 60

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

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

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

64 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 没有右兄弟 64

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

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

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