广度优先周游森林 广度优先周游森林(续) template <class T> while (laQueue empty o void Tree<T>: WidthTraverse2(TreeNode<T>* pointer=qUeue. fronto /取队首 /使用STL队列 qUeue popO; //出队列 using st Visit(pointer> value();/访问 queue<TreeNode<T>k> qUeue de<t>k pointer=root pointer pointer->LeftMostchildo; while(pointer qUeue. push(pointer) aQueue. push (pointer); pointer= pointer-> Rightsiblingo pointer pointer->Rightsiblingo 机新有,食 大息单 张铭 有,盛 教材广度优先周游图示 广度优先周游森林(教材) void Tree<T>: WidthTraverse1(TreeNode<T>*k using sta::q /使用STL队列 queue<TreeNode<t>*> qUeue if ( pointer) return; qUeue. push (pointer) while laQueue empty ot pointer≡ qUeue. fronto;/取队列首结点指针 北大位 张 新有,究 张铭鷾 叔有,印鱼究 广度优先周游森林 广度优先周游森林 Visit( pointer> Value0)//访问当前结点 if (pointer->LeftMostchildo d while(pointer->Rightsiblingo) qUeue. push(pointer f( pointer-> LeftMostchildo)//左子结点进入队列 >LeftMostchildoi aQueue. push(pointer->LeftMostchildo; qUeue popo;∥出队列 pointer=pointer->RightsiblingO; Visit(pointer-> Value();//访问右兄弟结点 f/end while 物歌抗 新有,食邮岛究 张铭·票有,气即必究6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 广度优先周游森林 template <class T> void Tree<T>::WidthTraverse2(TreeNode<T>* root){ using std::queue; //使用STL队列 queue<TreeNode<T>*> aQueue; TreeNode<T>* pointer=root; while (pointer) { aQueue.push(pointer); pointer = pointer-> RightSibling()； } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 广度优先周游森林(续) while(!aQueue.empty()){ pointer=aQueue.front(); //取队首 aQueue.pop(); //出队列 Visit(pointer->Value()); //访问 pointer = pointer->LeftMostChild(); while (pointer) { aQueue.push(pointer); pointer = pointer-> RightSibling()； } } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 教材广度优先周游图示 A B C K F D E G H J G H F D C A B K E J 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 广度优先周游森林（教材） template <class T> void Tree<T>::WidthTraverse1(TreeNode<T>* root){ using std::queue; //使用STL队列 queue<TreeNode<T>*> aQueue; TreeNode<T>* pointer=root; if (!pointer) return; aQueue.push(pointer); while(!aQueue.empty()) { pointer=aQueue.front();//取队列首结点指针 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 广度优先周游森林 Visit(pointer->Value()); //访问当前结点 while(pointer->RightSibling()) { if(pointer->LeftMostChild())//左子结点进入队列 aQueue.push(pointer->LeftMostChild()); pointer=pointer->RightSibling(); Visit(pointer->Value()); //访问右兄弟结点 } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 广度优先周游森林 if (pointer->LeftMostChild()) aQueue.push(pointer ->LeftMostChild()); aQueue.pop(); //出队列 }//end while } F D E G A B