非递归前序周游二叉树 非递归中序周游二叉树 /使用STL中的 stack ■遇到一个结点 Binary TreeNode<T>* pointer=root; a. push(NULL);//栈底监视哨 hile( pointer)//或者 laStack. empty 把它推入栈中 Visit( pointer> valued);∥/访问当前结点 f( pointer-> rightchildo!=NUL)/右孩子入栈 周游其左子树 a Stack.pu if (pointer->leftchildo I= NULl) 周游完左子树 d(H法左子同冲转向访问右子下 从栈顶托出该结点并访问之 aStack popo;/機顶元纛退栈} |國·按照其右链地址周游该结点的右子树 非递归中序周游二叉树 非递归中序周游二叉树 template <class T> void //end if Binary Tree<T>: InOrderwithoutRecusion( Bina ese//左子树访问完毕,转向访问右子树 ryTreeNode<T>* root)t ng std: stack 使用STL中的 stack aStackpopO: /栈顶元素退栈 stack<Binary TreeNode<T>*> aStack; vsit( pointer-> value();//访问当前结点 /当前链接结构指向右孩 Stack. emptyol lpo pointer=pointer->nightchildo: y/end else /vsit( pointer-> value()前序访问点 a Stack push( pointer);//当前结点地址入栈 //当前链接结构指向左孩子 pointer=pointer->leftchildo 张鲁写 前有,聊脂究 非递归后序周游二叉树 非递归后序周游二叉树 遇到一个结点 左子树返回vs右子树返回? 把它推入栈中 周游它的左子树 给栈中元素加上一个特征位 左子树周游结束后 Lef表示已进入该结点的左子树,将从左边回来 按照其右链地址周游该结点的右子树 周游遍右子树后 Right表示已进入该结点的右子树,将从右边回来 从栈顶托出该结点并访问之 真大_血单 大息6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 { 非递归前序周游二叉树 using std::stack; //使用STL中的stack stack<BinaryTreeNode<T>* > aStack; BinaryTreeNode<T>* pointer=root; aStack.push(NULL); // 栈底监视哨 while(pointer){ // 或者!aStack.empty() Visit(pointer->value()); //访问当前结点 if (pointer->rightchild() != NULL) //右孩子入栈 aStack.push(pointer->rightchild()); if (pointer->leftchild() != NULL) pointer = pointer->leftchild(); //左路下降 else { //左子树访问完毕，转向访问右子树 pointer=aStack.top(); aStack.pop(); //栈顶元素退栈 } } } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 非递归中序周游二叉树 „ 遇到一个结点 „ 把它推入栈中 „ 周游其左子树 „ 周游完左子树 „ 从栈顶托出该结点并访问之 „ 按照其右链地址周游该结点的右子树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 非递归中序周游二叉树 „ template<class T> void BinaryTree<T>::InOrderWithoutRecusion(Bina ryTreeNode<T>* root) { using std::stack; //使用STL中的stack stack<BinaryTreeNode<T>* > aStack; BinaryTreeNode<T>* pointer=root; while(!aStack.empty()||pointer) { if(pointer){ // Visit(pointer->value()); 前序访问点 aStack.push(pointer); //当前结点地址入栈 //当前链接结构指向左孩子 pointer=pointer->leftchild(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 非递归中序周游二叉树 }//end if else {//左子树访问完毕，转向访问右子树 pointer=aStack.top(); aStack.pop(); //栈顶元素退栈 Visit(pointer->value());//访问当前结点 //当前链接结构指向右孩子 pointer=pointer->rightchild(); }//end else } //end while } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 非递归后序周游二叉树 „ 遇到一个结点 „ 把它推入栈中 „ 周游它的左子树 „ 左子树周游结束后 „ 按照其右链地址周游该结点的右子树 „ 周游遍右子树后 „ 从栈顶托出该结点并访问之 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 非递归后序周游二叉树 „ 左子树返回 vs 右子树返回 ? „ 给栈中元素加上一个特征位 „ Left表示已进入该结点的左子树，将从左边回来 „ Right表示已进入该结点的右子树，将从右边回来