【数据结构】非递归遍历二叉树

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

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

【先序遍历】

下边看实现代码：

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;
	}

【中序遍历】

下边给出实现代码：<注明：图片中那是中序遍历，打错了>

<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;
	}

【后序遍历】

下边看代码：

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;
	}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!