数据结构与算法 ( 五 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg
第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 2
5.2 的抽象数据类型抽象数据类型 逻辑结构 + 运算 : 针对整棵树 初始化 合并两棵 围绕结点 访问某个结点的左子结点 右子结点 父结点 访问结点存储的数据 3
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.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
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
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
5.2 的抽象数据类型 遍历 遍历 ( 或称周游,traversal) 系统地访问数据结构中的结点 每个结点都正好被访问到一次 的结点的线性化 8
5.2 的抽象数据类型 深度优先遍历 三种深度优先遍历的递归定义 : (1) 前序法 (tlr 次序,preorder traversal) 访问根结点 ; 按前序遍历左子树 ; 按前序遍历右子树 (2) 中序法 (LtR 次序,inorder traversal) 按中序遍历左子树 ; 访问根结点 ; 按中序遍历右子树 (3) 后序法 (LRt 次序,postorder traversal) 按后序遍历左子树 ; 按后序遍历右子树 ; 访问根结点 9
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 第五章 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
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
5.2 的抽象数据类型 思考 前 中 后序哪几种结合可以恢复的结构? 已知某的中序序列为 {A, B, C, D, E, F, G}, 后序序列为 {B, D, C, A, F, G, E}; 则其前序序列为 13
5.2 的抽象数据类型 DFS 遍历的非递归算法 递归算法非常简洁 推荐使用 当前的编译系统优化效率很不错了 特殊情况用栈模拟递归 理解编译栈的工作原理 理解深度优先遍历的回溯特点 有些应用环境资源限制不适合递归 14
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 栈访问结点栈中结点已访问结点
思想 : 5.2 的抽象数据类型非递归前序遍历 遇到一个结点, 就访问该结点, 并把此结点的非空右结点推入栈中, 然后下降去遍历它的左子树 ; 遍历完左子树后, 从栈顶托出一个结点, 并按照它的右链接指示的地址再去遍历该结点的右子树结构 template<class T> void BinaryTree<T>::PreOrderWithoutRecusion (BinaryTreeNode<T>* root) { 16
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(); // 栈顶元素退栈 } } }
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
5.2 的抽象数据类型非递归中序遍历 遇到一个结点 把它推入栈中 遍历其左子树 遍历完左子树 从栈顶托出该结点并访问之 按照其右链地址遍历该结点的右子树 19
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
5.2 的抽象数据类型 } } //end if else { 21 // 左子树访问完毕, 转向访问右子树 pointer = astack.top(); astack.pop(); Visit(pointer->value()); // 当前链接结构指向右孩子 pointer=pointer->rightchild(); } //end else } //end while // 栈顶元素退栈 // 访问当前结点
5.2 的抽象数据类型非递归后序遍历 左子树返回 vs 右子树返回? 给栈中元素加上一个特征位 Left 表示已进入该结点的左子树, 将从左边回来 Right 表示已进入该结点的右子树, 将从右边回来 22
D 23 第五章 后序序列目录出栈序列页 A B E 5.2 的抽象数据类型 G D C H F I 非递归后序遍历 栈 (D,L) (D,R) (B,L) (A,L) 未访问结点栈中结点出栈结点
后序序列出栈序列 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 未访问结点栈中结点出栈结点
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) 未访问结点栈中结点出栈结点
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) 未访问结点栈中结点出栈结点
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 第五章 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;
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
5.2 的抽象数据类型 遍历算法的时间代价分析 在各种遍历中, 每个结点都被访问且只被访问一次, 时间代价为 O(n) 非递归保存入出栈 ( 或队列 ) 时间 前序 中序, 某些结点入 / 出栈一次, 不超过 O(n) 后序, 每个结点分别从左 右边各入 / 出一次, O(n) 30
5.2 的抽象数据类型 遍历算法的空间代价分析 深搜 : 栈的深度与树的高度有关 最好 O(log n) 最坏 O(n) 31
5.2 的抽象数据类型 思考 非递归遍历的意义? 后序遍历时, 栈中结点有何规律? 栈中存放了什么? 前序 中序 后序框架的算法通用性? 例如后序框架是否支持前序 中序访问? 若支持, 怎么改动? 32
数据结构与算法 谢谢聆听 国家精品课 数据结构与算法 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 张铭, 王腾蛟, 赵海燕高等教育出版社,2008. 6 十一五 国家级规划教材