二叉树是一种常见的数据结构，这里我们需要要注意的是，二叉树的非递归的遍历。

先序遍历，中序遍历，后序遍历

这三种遍历，如果用非递归的方式实现，我们则需要借助栈这个结构，首先我们需要遍历所有左子树的左节点。进行压栈，完成压栈之后，根据不同的需求，判断是否该继续访问或者弹出亦或者是压入该节点的右子树。

层序遍历

不同于其他的遍历方式，层序遍历是以根节点为开始，依次向下，每层从左到右依次访问。

这里我们需要借助与队列这种数据结构，层层入队，层层出队，完成遍历。

代码如下：

#pragmaonce#include<iostream>usingnamespacestd;#include<queue>#include<stack>typedefcharDataType;structBinaryTreeNode//节点结构体{BinaryTreeNode(DataTypedata=(DataType)0):_data(data),_leftChild(NULL),_rightChild(NULL){}DataType_data;BinaryTreeNode*_leftChild;BinaryTreeNode*_rightChild;};classBinaryTree{typedefBinaryTreeNode_NODE;public:BinaryTree(char*str)//通过先序的字符串构造二插树‘#’为空{_root=_CreatTree(_root,str);}BinaryTree(constBinaryTree&t){_root=_Copy(t._root);}BinaryTreeoperator=(BinaryTreet){swap(_root,t._root);return*this;}~BinaryTree(){_Destory(_root);}size_tSize()//求二叉树的大小{return_Size(_root);}size_tDepth()//求深度{return_Depth(_root);}voidLevelOrder()//层序遍历二叉树{queue<_NODE*>NodeQueue;_NODE*cur=_root;NodeQueue.push(cur);while(!NodeQueue.empty()){_NODE*tmp=NodeQueue.front();//取队头cout<<tmp->_data<<"";//访问NodeQueue.pop();if(tmp->_leftChild)//左不为空入左，右不为空入右NodeQueue.push(tmp->_leftChild);if(tmp->_rightChild)NodeQueue.push(tmp->_rightChild);}}voidBackOrder_NONREC()//后续非递归遍历{stack<_NODE*>s;_NODE*prev=NULL;_NODE*cur=_root;while(!s.empty()||cur)//压一颗树的左子树，直到最左{while(cur){s.push(cur);cur=cur->_leftChild;}_NODE*top=s.top();if(top->_rightChild==NULL||top->_rightChild==prev)//若栈顶节点的右节点为空，或者是已经访问过的节点，则不弹出栈顶节点{visitor(top);prev=top;//将最后一次访问过得节点保存s.pop();}else//否则压入以栈顶节的右节点点为根的左子树，直到最左{cur=top->_rightChild;}}}voidInOrder_NONREC()//中序非递归遍历{stack<_NODE*>s;_NODE*cur=_root;while(!s.empty()||cur){while(cur)//压一棵树的左节点直到最左，若为空则不进行压栈{s.push(cur);cur=cur->_leftChild;}_NODE*top=s.top();if(!s.empty())//访问栈顶节点，将另一颗被压的树，置为栈顶节点的右子树{visitor(top);s.pop();cur=top->_rightChild;}}}voidPrevOrder_NONREC()//先序非递归遍历{stack<_NODE*>s;_NODE*cur=NULL;s.push(_root);while(!s.empty()){cur=s.top();//先访问当前节点visitor(cur);s.pop();if(cur->_rightChild)//当前右节点不为空压入s.push(cur->_rightChild);if(cur->_leftChild)s.push(cur->_leftChild);}cout<<endl;}protected:staticvoidvisitor(_NODE*cur)//访问函数，为了满足测试，控制台打印数据{cout<<cur->_data<<"";}_NODE*_Copy(_NODE*root){_NODE*newRoot=NULL;if(root==NULL)returnNULL;else{newRoot=new_NODE(root->_data);newRoot->_leftChild=_Copy(root->_leftChild);newRoot->_rightChild=_Copy(root->_rightChild);}returnnewRoot;}size_t_Depth(_NODE*root){size_tdepth=0;if(root==NULL)returndepth;else{depth=_Depth(root->_leftChild)+1;size_tnewdepth=_Depth(root->_rightChild)+1;depth=depth>newdepth?depth:newdepth;}returndepth;}size_t_Size(_NODE*root){if(root==NULL)return0;elsereturn_Size(root->_leftChild)+_Size(root->_rightChild)+1;}void_Destory(_NODE*&root){if(root){if((root->_leftChild==NULL)&&(root->_rightChild==NULL)){deleteroot;root=NULL;}else{_Destory(root->_leftChild);_Destory(root->_rightChild);_Destory(root);}}}_NODE*_CreatTree(_NODE*root,char*&str){_NODE*cur=root;if(*str=='#'||*str==0){returnNULL;}else{cur=new_NODE(*str);cur->_leftChild=_CreatTree(cur->_leftChild,++str);cur->_rightChild=_CreatTree(cur->_rightChild,++str);}returncur;}protected:_NODE*_root;};

如有不足或疑问希望指正。