深度优先周游二叉树 变换根结点的周游顺序,得到三种方案 ①前序周游(tLR次序):访问根结点;前 序周游左子树;前序周游右子树 n①前序周游: ABDCEGFHI 2中序周游(tR次序):中序周游左子 树;访问根结点;中序周游右子树。 n②中序周游: DBAEGCHFI ③后序周游(LR次序):后序周游左子 树;后序周游右子树;访问根结点 n⑧后序周游: DBGEHIFCA 张写 深度优先周游二叉树(递归) 44周游二叉树 lass t> void Binary Tree<T>: DepthOrder(Binary TreeNode<T>* root)( ■二叉树周游 Visit(root) //前序 DepthOrder(root- leftchildo);∥问左子树 44.1深度优先周游二叉树 visit(root); //中序 442非递归深度优先周游二叉树 DepthOrdert(root> rightchildo/访问右子树 Visit(root; //后序 443广度优先周游二叉树 叔有。轨印当究 张鲁写 前有,聊脂究 非递归深度优先周游二叉树 非递归前序周游二叉树—简洁 深度优先二叉树周游是递归定义的 遇到一个结点,就访问该结点,并把此结点的非空右结点 推入梭中,然后下降去周游它的左子树 栈是实现递归的最常用的结构 周游完左子树后,从栈顶托出一个结点,并按照它的右链 接指示的地址再去周游该结点的右子树结构 记下尚待周游的结点或子树 BinaryTree<T>:: PreOrderwithoutRecusion 以备以后访问 (Binary TreeNode<T>k root /非递归前序遍历二叉树或其子树 真大_血单 大息 55 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 深度优先周游二叉树 变换根结点的周游顺序，得到三种方案： ① 前序周游(tLR次序)：访问根结点；前 序周游左子树；前序周游右子树。 ② 中序周游(LtR次序)：中序周游左子 树；访问根结点；中序周游右子树。 ③ 后序周游(LRt次序)：后序周游左子 树；后序周游右子树；访问根结点。 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 „ ① 前序周游：ABDCEGFHI „ ② 中序周游：DBAEGCHFI „ ③ 后序周游：DBGEHIFCA G H E A B C D F I 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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); //后序 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 4.4 周游二叉树 „ 二叉树周游 „ 4.4.1 深度优先周游二叉树 „ 4.4.2 非递归深度优先周游二叉树 „ 4.4.3 广度优先周游二叉树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 非递归深度优先周游二叉树 „ 深度优先二叉树周游是递归定义的 „ 栈是实现递归的最常用的结构 „ 记下尚待周游的结点或子树 „ 以备以后访问 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 非递归前序周游二叉树——简洁 „ 思想： „ 遇到一个结点，就访问该结点，并把此结点的非空右结点 推入栈中，然后下降去周游它的左子树； „ 周游完左子树后，从栈顶托出一个结点，并按照它的右链 接指示的地址再去周游该结点的右子树结构。 template<class T> void BinaryTree<T>::PreOrderWithoutRecusion (BinaryTreeNode<T>* root) //非递归前序遍历二叉树或其子树