非递归后序周游二叉树 非递归后序周游二叉树 栈中的元素类型定义 StackE| ement template<dass T> enum Tags(Left, Right》//特征标识定义 void Binary Tree<T>:: PostorderWithoutRecusion (BinaryTreeNode<T>* root) class stackElement /栈元囊的定义 /非递归中序遗历二叉树或其子树 using std: stack;//使用STL找部分 叉树结点的链接 StackElement<T> element; eeNode<T>* pointer; stack< StackElement<T>> a stack;//栈申明 识申明 Tags tag: 四 return;/空树即返回 非递归后序周游二叉树 非递归后序周游二叉树 whle(true)//进入左子树 pointer=element pointer; while(pointer=NULL) lement pointer=pointer //从右子树回来 while(element tag==Right a stack push(element); vsit( pointer> value();//访问当前结点 /沿左子树方向向下周游 pointer=pointer->leftchildo: if(a Stack.empty) /托出栈顶元素 =astack topo element=aStack topO: 叔有。轨印当究 张鲁写 非递归后序周游二叉树 44周游二叉树 a Stackpop(;//弹栈 pointer=element pointer; ■二叉树周游 7/1/end else y/end while //从左子树回来 441深度优先周游二叉树 element tag=Right; 442非递归深度优先周游二叉树 /转向访问右子树 pointer=pointer->rightchildo: 44.3广度优先周游二叉树 y/end while 真大_血单 大息7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 非递归后序周游二叉树 „ 栈中的元素类型定义StackElement enum Tags{Left,Right}; //特征标识定义 template <class T> class StackElement //栈元素的定义 { public: //指向二叉树结点的链接 BinaryTreeNode<T>* pointer; //特征标识申明 Tags tag; }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 非递归后序周游二叉树 template<class T> void BinaryTree<T>::PostOrderWithoutRecusion (BinaryTreeNode<T>* root) //非递归中序遍历二叉树或其子树 { using std::stack;//使用STL栈部分 StackElement<T> element; stack<StackElement<T > > aStack;//栈申明 BinaryTreeNode<T>* pointer; if(root==NULL) return;//空树即返回 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 非递归后序周游二叉树 //else pointer=root; while(true){//进入左子树 while(pointer!=NULL){ element.pointer=pointer; element.tag=Left; aStack.push(element); //沿左子树方向向下周游 pointer=pointer->leftchild(); } //托出栈顶元素 element=aStack.top(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 非递归后序周游二叉树 aStack.pop(); pointer=element.pointer; //从右子树回来 while(element.tag==Right){ Visit(pointer->value());//访问当前结点 if(aStack.empty()) return; //else{ element=aStack.top(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 非递归后序周游二叉树 aStack.pop();//弹栈 pointer=element.pointer; // }//end else }//end while //从左子树回来 element.tag=Right; aStack.push(element); //转向访问右子树 pointer=pointer->rightchild(); }//end while } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 4.4 周游二叉树 „ 二叉树周游 „ 4.4.1 深度优先周游二叉树 „ 4.4.2 非递归深度优先周游二叉树 „ 4.4.3 广度优先周游二叉树