EO F GO dH ①前序周游: ABDCEGFHI 中序周游: DBAEGCHFI ③后序周游: DBGEHIFCA 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 ① 前序周游：ABDCEGFHI ② 中序周游：DBAEGCHFI ③ 后序周游：DBGEHIFCA G H E A B C D F I
深度优先周游二叉树(递归) template<class t> void Binary Tree<T>: DepthOrder(Binary TreeNode<T>* root)t if(root!=NULL Visit(root); //前序 Depth orderi(root-> eleftchildo);∥访问左子树 Visit(root); /中序 Depthordert(root-> erightchildo;/访问右子树 visit(root); //后序 京大学信息学院张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 深度优先周游二叉树（递归） template<class T> void BinaryTree<T>::DepthOrder (BinaryTreeNode<T>* root) ｛ if(root!=NULL){ DepthOrder(root->leftchild()); //访问左子树 DepthOrder(root->rightchild());//访问右子树 } ｝ Visit(root); //前序 Visit(root); //中序 Visit(root); //后序
44周游二叉树 ■二叉树周游 441深度优先周游二叉树 442非递归深度优先周游二叉树 443广度优先周游二叉树 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 。2
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 4.4 周游二叉树 二叉树周游 4.4.1 深度优先周游二叉树 4.4.2 非递归深度优先周游二叉树 4.4.3 广度优先周游二叉树
非递归深度优先周游二叉树 深度优先二叉树周游是递归定义的 栈是实现递归的最常用的结构 记下尚待周游的结点或子树 以备以后访问 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 。2
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 非递归深度优先周游二叉树 深度优先二叉树周游是递归定义的 栈是实现递归的最常用的结构 记下尚待周游的结点或子树 以备以后访问
非递归前序周游二叉树——简洁 思想: n遇到一个结点,就访问该结点,并把此结点的非空右结点 推入栈中,然后下降去周游它的左子树; 周游完左子树后,从栈顶托出一个结点,并按照它的右链 接指示的地址再去周游该结点的右子树结构。 template<class T> void BinaryTree<T>: PreOrderWithoutRecusion ( BinaryTreeNode<T>* root) /非递归前序遍历二叉树或其子树 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 非递归前序周游二叉树——简洁 思想： 遇到一个结点，就访问该结点，并把此结点的非空右结点 推入栈中，然后下降去周游它的左子树； 周游完左子树后，从栈顶托出一个结点，并按照它的右链 接指示的地址再去周游该结点的右子树结构。 template<class T> void BinaryTree<T>::PreOrderWithoutRecusion (BinaryTreeNode<T>* root) //非递归前序遍历二叉树或其子树