广度优先周游森林 广度优先周游森林(续) 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
452森林的链式存储52子结点表示法 521子结点表表示法 ①522左子结点/右兄弟结点表示法 523动态结点表示法 524动态左子/右兄弟”二又链表表示法 △525父指针表示法 ■第140页图56 北大啦 机新有,食 大息单 张铭 有,盛 522左子结点/右兄弟结点表示法 523动态结点表示法 第140页图57 第142页图59 练度皮右兄 山a國 张铭鷾 叔有,印鱼究 第142页图510 动态表示法 5.24动态“左子/右兄弟二叉链表 左结点/右兄弟:最常用 □ [ △E ①@弟①① 泅□d b)左子女一右兄弟表示Ma 新有,食邮岛究 张铭帖 有,即究
7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 5.2 森林的链式存储 5.2.1 子结点表表示法 5.2.2 左子结点/右兄弟结点表示法 5.2.3 动态结点表示法 5.2.4 动态“左子/右兄弟”二叉链表表示法 5.2.5 父指针表示法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 5.2.1 子结点表表示法 A 1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 J 4 2 3 4 5 6 7 8 9 索引 值 父节点 0 1 2 3 4 5 6 7 8 9 第140页图5.6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 5.2.2 左子结点/右兄弟结点表示法 第140页图5.7 值 父 右兄弟 1 A 左子 结点 3 B 0 2 6 C 0 D 1 4 8 E 1 5 F 1 G 2 7 H 2 I 4 9 J 4 I J E F G A B C D H A’ X 11 A' X 10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 5.2.3 动态结点表示法 第142页图5.9 大小 A B 3 I J E F G A B C D H 2 值 C 2 D 0 E 2 F 0 G H 0 I 0 J 0 （a）树 （b）树的实现 0 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 第142页图5.10 动态表示法 J I E F G A B C D H （a）树 （b）树的实现 A B D E F I J C G H 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 5.2.4 动态“左子/右兄弟”二叉链表 左结点/右兄弟：最常用