由于递归时通过栈来实现的，虽然递归代码有时候看起来比较简单，然后递归太深就会造

成栈溢出。所以我们可以通过栈来实现二叉树的非递归遍历。下边看解析：

【先序遍历】

下边看实现代码：

void PreOrderTraverseNonR()
	{
		stack<Node*> s;
		Node* cur = _root;
		if (cur == NULL)
			return;

		while (cur || !s.empty())
		{
			while (cur)
			{
				cout << cur->_data << " ";
				s.push(cur);
				cur = cur->_left;
			}
			
			Node* top = s.top();
			s.pop();
			cur = top->_right;
		}
		cout << endl;
	}@H_403_31@ 

 

 
 

 
 
【中序遍历】
 

 
 
下边给出实现代码：<注明：图片中那是中序遍历，打错了>
 
 
<pre name="code" class="cpp">void InOrderTraverseNonR()
	{
		stack<Node*> s;
		Node* cur = _root;
		if (cur == NULL)
			return;

		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			
			Node* top = s.top();
			cout << top->_data<<" ";
			s.pop();
			cur = top->_right;
		}
		cout << endl;
	}@H_403_31@ 

 

 
 
@H_403_31@ 
 

 
 
【后序遍历】
 

 
 
下边看代码：
 
 
void PostOrderTraverseNonR()
	{
		if (NULL == _root)
			return;
		Node* prev = NULL;
		Node* cur = _root;
		stack<Node*> s;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			Node* top = s.top();
			if (top->_right == NULL || top->_right == prev)
			{
				cout << top->_data << " ";
				prev = top;
				s.pop();
			}
			else
			{
				cur = top->_right;
			}
		}
		cout << endl;
	}@H_403_31@ 原文链接：https://www.f2er.com/datastructure/382442.html