二叉树三种遍历方式之循环

using namespace std; template <class T> struct BinaryTreeNode//定义二叉树的节点 { BinaryTreeNode(const T& value) :_value(value) ,_pLeft(NULL) ,_pRight(NULL) {} T _value; BinaryTreeNode<T>* _pLeft; BinaryTreeNode<T>* _pRight; }; template<class T> class BinaryTree//定义二叉树 { typedef BinaryTreeNode<T> Node; public: BinaryTree() :_pRoot(NULL) {} private: Node* _pRoot;//根节点 };

1.先序遍历 根节点—->左子树—->右子树 void PreOrder_Nor() { cout<<”PreOrder_Nor”<

void InOrder_Nor1() { cout<<"InOrder_Nor1"<<endl; if(_pRoot == NULL) return ; stack<Node*> s; Node* pCur = _pRoot; while(pCur || !s.empty()) { while(pCur) { s.push(pCur); pCur = pCur->_pLeft; } pCur = s.top(); cout<<pCur->_value<<" "; s.pop(); pCur = pCur->_pRight; } cout<<endl; }

（1）.先找到最左边的结点，并保存路径 （2）.取栈顶元素并访问 （3）.出栈 （4）.取该节点的右孩子 方法二：当右孩子为空时需单独处理

void InOrder_Nor2() { cout<<"InOrder_Nor2"<<endl; if(_pRoot == NULL) return ; stack<Node*> s; Node* pCur = _pRoot; while(pCur || !s.empty()) { if(pCur->_pLeft)//如果pCur的左孩子不为空，就一直入栈 { s.push(pCur); pCur = pCur->_pLeft; } else//如果pCur的左孩子为空 { cout<<pCur->_value<<" ";//先输出当前节点的值 pCur = pCur->_pRight;//再查看pCur的右孩子 while(!pCur && !s.empty())//如果右孩子为空但栈不为空 { pCur = s.top(); cout<<pCur->_value<<" ";//因为当前节点的左孩子已经访问过, //所以输出当前栈顶元素的值， s.pop();//出栈 pCur = pCur->_pRight;//再查看当前栈顶元素的右孩子 } } } cout<<endl; }

3.后序遍历 左子树—->右子树—->根节点 方法一：简易版

void PostOrder_Nor1() { cout<<"PostOrder_Nor"<<endl; if(_pRoot == NULL) return ; stack<Node*> s; Node* pCur = _pRoot; Node* pPre = NULL; s.push(_pRoot); while(!s.empty()) { pCur = s.top(); //如果当前节点没有左孩子和右孩子或是当前节点的左孩子或是右孩子已经输出 if((pCur->_pLeft == NULL && pCur->_pRight == NULL) || \ ((pCur->_pLeft == pPre || pCur->_pRight == pPre))) { cout<<pCur->_value<<" "; s.pop(); pPre = pCur; } else { if(pCur->_pRight) s.push(pCur->_pRight); if(pCur->_pLeft) s.push(pCur->_pLeft); } } cout<<endl; }

方法二：容易理解

void PostOrder_Nor2() { cout<<"PostOrder_Nor"<<endl; if(_pRoot == NULL) return ; stack<Node*> s; Node* pCur = _pRoot; Node* pPre = NULL; while(pCur || !s.empty()) { while(pCur)//找最左节点 { s.push(pCur); pCur = pCur->_pLeft; } Node* pTop = s.top();//如果用pCur=s.top()，就会让最左边的结点陷入死循环 if(pTop->_pRight == NULL || pTop->_pRight == pPre) { cout<<pTop->_value<<" "; pPre = pTop; s.pop(); } else pCur = pTop->_pRight; } cout<<endl; }