树/森林的ADT(2) 7返回 current结点的父结点 TreeNode<T>* Parent(TreeNode<t> current); //返回 current结点的前一个邻居结点 TreeNode<t>* Prevsibling(TreeNode<T>* current); /删除以 subroot为根的子树的所有结点 void Delete SubTree(TreeNode<T>* subroot) /先根深度优先周游树 void RootFirstTraverse(TreeNode<T>* root) //后根深度优先周游树 void RootLastTraverse(treeNode<T>* root) //广度优先周游树 void widthTraverse(treeNode<T>* root; 京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 26
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 树 /森林的ADT(2) //返回current结点的父结点 TreeNode<T>* Parent(TreeNode<T>* current); //返回current结点的前一个邻居结点 TreeNode<T>* PrevSibling(TreeNode<T>* current); //删除以subroot为根的子树的所有结点 void DeleteSubTree(TreeNode<T>* subroot); //先根深度优先周游树 void RootFirstTraverse(TreeNode<T>* root); //后根深度优先周游树 void RootLastTraverse(TreeNode<T>* root); //广度优先周游树 void WidthTraverse(TreeNode<T>* root); };
514森林的周游 ■按深度方向周游 先根次序 后根次序 按广度方向周游 宽度优先周游 ■层次周游 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 27
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 5.1.4 森林的周游 按深度方向周游 先根次序 后根次序 按广度方向周游 宽度优先周游 层次周游
森林的周游 Q BO OD C E ○○ KOOH OF k 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 森林的周游 A B C K F D E G H J G H F D C A B K E J
周游森林vs周游二叉树 先根次序周游森林 前序法周游二叉树 后根次序周游森林 按中序法周游对应的二叉树 中根周游? 无法明确规定根在哪两个子结点之间 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 29
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 周游森林vs周游二叉树 先根次序周游森林 前序法周游二叉树 后根次序周游森林 按中序法周游对应的二叉树 中根周游？ 无法明确规定根在哪两个子结点之间
补充:一种广度优先周游森林 B OD C E ○○ KOOH OF K a Prevsibling(函数采用本框架 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 30
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 补充：一种广度优先周游森林 A B C K F D E G H J G H F D C A B K E J PrevSibling()函数采用本框架