北京大学：《数据结构与算法》课程教学资源（实验班讲义）第四章 二叉树

非递归前序周游二叉树 非递归中序周游二叉树 /使用STL中的 stack ■遇到一个结点 Binary TreeNode<T>* pointer=root; a. push(NULL);//栈底监视哨 hile( pointer)//或者 laStack. empty 把它推入栈中 Visit( pointer> valued);∥/访问当前结点 f( pointer-> rightchildo!=NUL)/右孩子入栈 周游其左子树 a Stack.pu if (pointer->leftchildo I= NULl) 周游完左子树 d(H法左子同冲转向访问右子下 从栈顶托出该结点并访问之 aStack popo;/機顶元纛退栈} |國·按照其右链地址周游该结点的右子树 非递归中序周游二叉树 非递归中序周游二叉树 template <class T> void //end if Binary Tree<T>: InOrderwithoutRecusion( Bina ese//左子树访问完毕,转向访问右子树 ryTreeNode<T>* root)t ng std: stack 使用STL中的 stack aStackpopO: /栈顶元素退栈 stack<Binary TreeNode<T>*> aStack; vsit( pointer-> value();//访问当前结点 /当前链接结构指向右孩 Stack. emptyol lpo pointer=pointer->nightchildo: y/end else /vsit( pointer-> value()前序访问点 a Stack push( pointer);//当前结点地址入栈 //当前链接结构指向左孩子 pointer=pointer->leftchildo 张鲁写 前有,聊脂究 非递归后序周游二叉树 非递归后序周游二叉树 遇到一个结点 左子树返回vs右子树返回? 把它推入栈中 周游它的左子树 给栈中元素加上一个特征位 左子树周游结束后 Lef表示已进入该结点的左子树,将从左边回来 按照其右链地址周游该结点的右子树 周游遍右子树后 Right表示已进入该结点的右子树,将从右边回来 从栈顶托出该结点并访问之 真大_血单 大息

6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 { 非递归前序周游二叉树 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(); //栈顶元素退栈 } } } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 非递归中序周游二叉树 „ 遇到一个结点 „ 把它推入栈中 „ 周游其左子树 „ 周游完左子树 „ 从栈顶托出该结点并访问之 „ 按照其右链地址周游该结点的右子树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 非递归中序周游二叉树 „ template<class T> void BinaryTree<T>::InOrderWithoutRecusion(Bina ryTreeNode<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(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 非递归中序周游二叉树 }//end if else {//左子树访问完毕，转向访问右子树 pointer=aStack.top(); aStack.pop(); //栈顶元素退栈 Visit(pointer->value());//访问当前结点 //当前链接结构指向右孩子 pointer=pointer->rightchild(); }//end else } //end while } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 非递归后序周游二叉树 „ 遇到一个结点 „ 把它推入栈中 „ 周游它的左子树 „ 左子树周游结束后 „ 按照其右链地址周游该结点的右子树 „ 周游遍右子树后 „ 从栈顶托出该结点并访问之 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 非递归后序周游二叉树 „ 左子树返回 vs 右子树返回 ? „ 给栈中元素加上一个特征位 „ Left表示已进入该结点的左子树，将从左边回来 „ Right表示已进入该结点的右子树，将从右边回来

非递归后序周游二叉树 非递归后序周游二叉树 栈中的元素类型定义 StackE| ement template<dass T> enum Tags(Left, Right》//特征标识定义 void Binary Tree<T>:: PostorderWithoutRecusion (BinaryTreeNode<T>* root) class stackElement /栈元囊的定义 /非递归中序遗历二叉树或其子树 using std: stack;//使用STL找部分 叉树结点的链接 StackElement<T> element; eeNode<T>* pointer; stack< StackElement<T>> a stack;//栈申明 识申明 Tags tag: 四 return;/空树即返回 非递归后序周游二叉树 非递归后序周游二叉树 whle(true)//进入左子树 pointer=element pointer; while(pointer=NULL) lement pointer=pointer //从右子树回来 while(element tag==Right a stack push(element); vsit( pointer> value();//访问当前结点 /沿左子树方向向下周游 pointer=pointer->leftchildo: if(a Stack.empty) /托出栈顶元素 =astack topo element=aStack topO: 叔有。轨印当究 张鲁写 非递归后序周游二叉树 44周游二叉树 a Stackpop(;//弹栈 pointer=element pointer; ■二叉树周游 7/1/end else y/end while //从左子树回来 441深度优先周游二叉树 element tag=Right; 442非递归深度优先周游二叉树 /转向访问右子树 pointer=pointer->rightchildo: 44.3广度优先周游二叉树 y/end while 真大_血单 大息

7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 非递归后序周游二叉树 „ 栈中的元素类型定义StackElement enum Tags{Left,Right}; //特征标识定义 template <class T> class StackElement //栈元素的定义 { public: //指向二叉树结点的链接 BinaryTreeNode<T>* pointer; //特征标识申明 Tags tag; }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 非递归后序周游二叉树 template<class T> void BinaryTree<T>::PostOrderWithoutRecusion (BinaryTreeNode<T>* root) //非递归中序遍历二叉树或其子树 { using std::stack;//使用STL栈部分 StackElement<T> element; stack<StackElement<T > > aStack;//栈申明 BinaryTreeNode<T>* pointer; if(root==NULL) return;//空树即返回 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 非递归后序周游二叉树 //else pointer=root; while(true){//进入左子树 while(pointer!=NULL){ element.pointer=pointer; element.tag=Left; aStack.push(element); //沿左子树方向向下周游 pointer=pointer->leftchild(); } //托出栈顶元素 element=aStack.top(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 非递归后序周游二叉树 aStack.pop(); pointer=element.pointer; //从右子树回来 while(element.tag==Right){ Visit(pointer->value());//访问当前结点 if(aStack.empty()) return; //else{ element=aStack.top(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 非递归后序周游二叉树 aStack.pop();//弹栈 pointer=element.pointer; // }//end else }//end while //从左子树回来 element.tag=Right; aStack.push(element); //转向访问右子树 pointer=pointer->rightchild(); }//end while } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 4.4 周游二叉树 „ 二叉树周游 „ 4.4.1 深度优先周游二叉树 „ 4.4.2 非递归深度优先周游二叉树 „ 4.4.3 广度优先周游二叉树

广度优先周游二叉树 广度优先周游二叉树 ■从二叉树的第一层(根结点)开始,自上至下逐 template<dass T> 层遍历;在同一层中,按照从左到右的顺序对结 Void Binary Tree<T>: LevelOrder 点逐一访问。 (Binary TreeNode<T>* root) { /使用ATL的队列 ■例如 queue<BinaryTreeNode<T>*> qUeue Binary TreeNode<T>* pointer=root; ABCDEFGH if(pointer) Queue. push(pointer); 四whe( qUeue empty 广度优先周游二叉树 算法代价分析 /取队列首结点 时间 pointer=qUeue. front(; 在各种周游中,每个结点都被访问且只被访问 inter-> value();//访闻当前结点 qUeue popo /左子树进队列 如果计算非递归保存入出栈(或队列)时间 f(pointer->leftchildo) 广度优先,正好每个结点入/出队一次,o(m) Queue. push(pointer->leftchildo) /右子树进队列 前序、中序,某些结点入/出栈一次,不超过o(n) if(pointer->rightchildO) 后序周游,每个结点分别从左、右边各入/出一次, aQueue. push(pointer->rightchildo) 四 end while 驰血端张帖物写 有轨申 张鲁写 前有,聊脂究 回 45二叉树的实现 空间 451用指针实现二叉树 最好o(logn),最坏o(n) 深度优先 452空间开销分析 栈的深度与树的高度有关 453用数组实现完全二叉树 广度优先 ■与树的最大宽度有关 454穿线二叉树 真大_血单 ② 大息

8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 43 广度优先周游二叉树 „ 从二叉树的第一层（根结点）开始，自上至下逐 层遍历；在同一层中，按照从左到右的顺序对结 点逐一访问。 „ 例如： A B C D E F G H I G H E A B C D F I 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 44 广度优先周游二叉树 template<class T> Void BinaryTree<T>::LevelOrder (BinaryTreeNode<T>* root) { using std::queue; //使用ATL的队列 queue<BinaryTreeNode<T>*> aQueue; BinaryTreeNode<T>* pointer=root; if(pointer) aQueue.push(pointer); while(!aQueue.empty()) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 45 广度优先周游二叉树 { //取队列首结点 pointer=aQueue.front(); Visit(pointer->value());//访问当前结点 aQueue.pop(); //左子树进队列 if(pointer->leftchild()) aQueue.push(pointer->leftchild()); //右子树进队列 if(pointer->rightchild()) aQueue.push(pointer->rightchild()); }//end while } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 46 算法代价分析 时间 „ 在各种周游中，每个结点都被访问且只被访问一 次，时间代价为O(n) „ 如果计算非递归保存入出栈（或队列）时间 „ 广度优先，正好每个结点入/出队一次，O(n) „ 前序、中序，某些结点入/出栈一次，不超过O(n) „ 后序周游，每个结点分别从左、右边各入/出一次， O(n) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 47 空间 „ 最好O(log n)，最坏O(n) „ 深度优先 „ 栈的深度与树的高度有关 „ 广度优先 „ 与树的最大宽度有关 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 48 4.5 二叉树的实现 „ 4.5.1 用指针实现二叉树 „ 4.5.2 空间开销分析 „ 4.5.3 用数组实现完全二叉树 „ 4.5.4 穿线二叉树

45二叉树的实现 用指针实现二叉树 451用指针实现二叉树 ■非线性结构最自然的方法是链接的方法 452空间开销分析 指针left和 right,分别指向结点的左子女 453用数组实现完全二叉树 和右子女 454穿线二叉树 空指针 张写 用指针实现二叉树 用指针实现二叉树 其他的链接表示法 z区 例如“三叉链表 增加一个指向父母的指针 parent 具有“向上”访问的能力 h I 叔有。轨印当究 张鲁写 前有,聊脂究 用指针实现二叉树 用指针实现二叉树 扩展二叉树结点抽象数据类型 BinaryTreeNode,.为每 个元素结点添加left和rght左右子结点结构 //以后序周游的方式删除二叉树或其子树 if(root /二叉树结点指向左子树的指针 DeleteBinaryTree(root->left)}//递归删除左子树 Delete Binary Tree(root-> right);//递归删除右子树 /二叉树结点指向左子树的指针 Delete root/删除根结点 d inaryTreeNode <Tss right, 真大_血单 大息

9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 4.5 二叉树的实现 „ 4.5.1 用指针实现二叉树 „ 4.5.2 空间开销分析 „ 4.5.3 用数组实现完全二叉树 „ 4.5.4 穿线二叉树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 用指针实现二叉树 „ 非线性结构最自然的方法是链接的方法 „ 指针left和right，分别指向结点的左子女 和右子女 „ 空指针 left info right 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 用指针实现二叉树 A B C E F D G H I A B ∧ C ∧ D ∧ ∧ E F ∧ G ∧ ∧ H ∧ ∧ I ∧ t 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 用指针实现二叉树 „ 其他的链接表示法 „ 例如“三叉链表” „ 增加一个指向父母的指针parent „ 具有“向上”访问的能力 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 用指针实现二叉树 „ 扩展二叉树结点抽象数据类型BinaryTreeNode,为每 个元素结点添加left和right左右子结点结构 private: //二叉树结点指向左子树的指针 BinaryTreeNode<T>* left; //二叉树结点指向左子树的指针 BinaryTreeNode<T>* right; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 用指针实现二叉树 template<class T>void BinaryTree<T>:: DeleteBinaryTree(BinaryTreeNode<T>* root) {//以后序周游的方式删除二叉树或其子树 if(root){ DeleteBinaryTree(root->left);//递归删除左子树 DeleteBinaryTree(root->right);//递归删除右子树 Delete root;//删除根结点 } };