深度优先周游森林 ■按先根次序周游森林正好等同于按前序法周游对应 的二叉树 按后根次序周游森林正好等同于按中序法周游对应 的二叉树 不方便仿照中序法定义树的中根周游,因为当一个 根多于两个子结点时无法明确给出根与这些子结点 的次序 北京大学信息学院 版权所有,转载或翻印必究 Page 26
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 深度优先周游森林 ◼ 按先根次序周游森林正好等同于按前序法周游对应 的二叉树 ◼ 按后根次序周游森林正好等同于按中序法周游对应 的二叉树 ◼ 不方便仿照中序法定义树的中根周游，因为当一个 根多于两个子结点时无法明确给出根与这些子结点 的次序
宽度优先周游森林 template <class T> void Tree<T>i: WidthTraverse2(TreeNode<T>* roott using std: :queue /使用STL队列 queue<TreeNode<t>k> aQueuei TreeNode<T>*k pointer=root if(pointer qUeue.push(pointer) while( Queue empty pointer= qUeue fronto;//取队列首结点指针 北京大学信息学院 版权所有,转载或翻印必究 Page 27
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 宽度优先周游森林 template <class T> void Tree<T>::WidthTraverse2(TreeNode<T>* root){ using std::queue; //使用STL队列 queue<TreeNode<T>*> aQueue; TreeNode<T>* pointer=root; if(pointer){ aQueue.push(pointer); while(!aQueue.empty()){ pointer=aQueue.front();//取队列首结点指针
宽度优先周游森林 Visit(pointer-> Valued)//访问当前结点 while(pointer-> RightsiblingO) if( pointer-> Leftmostchild(/左子结点进入队列 aQueue. push(pointer->LeftMostChildoi pointer=pointer->Rightsiblingo; Visit( pointer-> Value();//访问右兄弟结点 北京大学信息学院 版权所有,转载或翻印必究 Page 28
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 宽度优先周游森林 Visit(pointer->Value()); //访问当前结点 while(pointer->RightSibling()) { if(pointer->LeftMostChild())//左子结点进入队列 aQueue.push(pointer->LeftMostChild()); pointer=pointer->RightSibling(); Visit(pointer->Value()); //访问右兄弟结点 }
宽度优先周游森林 if(pointer->LeftMostChildo) qUeue.push(pointer >LeftMostChildoi qUeue popOi //出队列 f//end while 3//end if 北京大学信息学院 版权所有,转载或翻印必究 Page 29
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 宽度优先周游森林 if(pointer->LeftMostChild()) aQueue.push(pointer ->LeftMostChild()); aQueue.pop(); //出队列 }//end while }//end if }
52森林的链式存储 521子结点表表示法 522左子结点/右兄弟结点表示法 523动态结点表示法 524动态“左子结点/右兄弟结点”二叉链 表表示法 525父指针表示法 北京大学信息学院 版权所有,转载或翻印必究 Page 30
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 5.2 森林的链式存储 ◼ 5.2.1 子结点表表示法 ◼ 5.2.2 左子结点/右兄弟结点表示法 ◼ 5.2.3 动态结点表示法 ◼ 5.2.4 动态“左子结点/右兄弟结点”二叉链 表表示法 ◼ 5.2.5 父指针表示法