在二叉树的应用中，很多使用二叉树的操作都是通过遍历来进行节点的修改。

所以对于遍历而言是学习二叉树的要点，今天就来总结一下。


假设二叉树的结构为：

template<classT>structBinaryTreeNode{BinaryTreeNode(constT&x):_data(x),_left(NULL),_right(NULL){}T_data;BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;};


前序遍历：

voidPrevOrder(){_PrevOrder(_root);cout<<endl;}void_PrevOrder(BinaryTreeNode<T>*root){if(root==NULL)return;cout<<root->_data<<"";_PrevOrder(root->_left);_PrevOrder(root->_right);}voidPrevOrder_Non_R(){stack<BinaryTreeNode<T>*>s;if(_root)s.push(_root);while(!s.empty()){BinaryTreeNode<T>*top=s.top();cout<<top->_data<<"";s.pop();if(top->_right)s.push(top->_right);if(top->_left)s.push(top->_left);}cout<<endl;}

2.中序遍历：

voidInOrder(){_InOrder(_root);cout<<endl;}void_InOrder(BinaryTreeNode<T>*root){if(root==NULL)return;_InOrder(root->_left);cout<<root->_data<<"";_InOrder(root->_right);}voidInOrder_Non_R(){stack<BinaryTreeNode<T>*>s;BinaryTreeNode<T>*cur=_root;while(cur||!s.empty()){//1.压左节点while(cur){s.push(cur);cur=cur->_left;}//取栈顶节点数据访问//前序遍历top节点的右树if(!s.empty()){BinaryTreeNode<T>*top=s.top();s.pop();cout<<top->_data<<"";cur=top->_right;}}cout<<endl;}

3.后序遍历：

voidPostOrder(){_PostOrder(_root);cout<<endl;}void_PostOrder(BinaryTreeNode<T>*root){if(root==NULL)return;_PostOrder(root->_left);_PostOrder(root->_right);cout<<root->_data<<"";}voidPostOrder_Non_R(){stack<BinaryTreeNode<T>*>s;BinaryTreeNode<T>*cur=_root;BinaryTreeNode<T>*prevVisited=NULL;while(cur||!s.empty()){//1.压左节点while(cur){s.push(cur);cur=cur->_left;}BinaryTreeNode<T>*top=s.top();if(top->_right==NULL||top->_right==prevVisited){cout<<top->_data<<"";s.pop();prevVisited=top;}else{cur=top->_right;}}cout<<endl;}

4.层次遍历

voidLevelOrder(){queue<BinaryTreeNode<T>*>q;if(_root)q.push(_root);while(!q.empty()){BinaryTreeNode<T>*front=q.front();cout<<front->_data<<"";q.pop();if(front->_left)q.push(front->_left);if(front->_right)q.push(front->_right);}cout<<endl;}

以上