广度优先周游二叉树 广度优先周游二叉树 ■从二叉树的第一层(根结点)开始,自上至下逐 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 穿线二叉树