PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

瑕依舒
8 years ago
Views:

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

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

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

4 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); // 子树构造结点 4

5 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); // 返回当前结点数据 // 返回左子树 // 返回右子树 // 设置左子树 // 设置右子树 // 设置数据域 // 判断是否为叶结点 // 重载赋值操作符 5

6 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;}; // 返回根结点 }; 6

7 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); // 删除或其子树 7

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

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

10 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 10

11 11 第五章 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

12 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); // 后序 12

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

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

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

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

17 17 第五章 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(); // 栈顶元素退栈 } } }

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

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

20 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(); 20

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

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

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

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

25 D 25 后序序列出栈序列 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) 未访问结点栈中结点出栈结点

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

27 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 出栈结点 27

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

29 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 指针为空, 以继续弹栈 } } } 29

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

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

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

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

PowerPoint 演示文稿

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