二叉树的非递归实现-创新互联

之前一直觉得二叉树使用递归来实现就感觉有点绕，今天才发现二叉树使用非递归来实现更加的绕，但是考虑到我们得使用非递归来提高二叉树的遍历效率，使用非递归是一种比较好的方法。

 三种递归遍历对遍历的描述，思路非常简洁，最重要的是三种方法完全统一，大大减轻了我们理解的负担。现在非递归使用栈来实现，利用了栈的先进后出的特点，可以解决。

 二叉树的递归实现之前已经实现过了，我们直接实现非递归。并且都使用栈实现

（一）前序遍历

 对于前序遍历，我们要解决的问题是何时压入左右子树？先压左子树还是右子树？

 答案是显而易见的，因为是前序遍历，所以在压栈根节点，出栈后再压入左右子树。并且是先压右子树。然后出栈左子树，最后出栈右子树。直到栈为空。

void PrevOrder_Nrec()//前序非递归实现
	{
		stack s;
		if (_root)
			s.push(_root);
		while (!s.empty())
		{
			Node* top = s.top();
			cout << top->_data << " ";
			s.pop();
			if (top->_right)
			{
				s.push(top->_right);
			}
			if (top->_left)
			{
				s.push(top->_left);
			}
		}
	}

（二）中序遍历

  中序遍历是一直压栈，把最左节点都压入栈内，出栈最左子树的左节点，然后出栈根节点，然后才出栈右节点。当栈为空时结束。

void MideOrder_Nrec()//中序遍历非递归实现
	{
		stack s;
		Node* cur = _root;
		while (!s.empty()||cur)
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			if (!s.empty())
			{
				Node* tmp = s.top();
				s.pop();
				cout << tmp->_data << " ";
				cur = tmp->_right;
			}
		}
	}

（三）后序遍历

 后序遍历比较难办，因为我们要找到一棵树，首先遍历到的都是树的根节点，在后序遍历中，得先把左右子树都遍历以后才能输出根节点。左子树比较好办，我们可以把左节点看作是一颗子树的根节点，所以我们必须要创建一个指针来标识是否我们已经访问过右子树。我们把这个指针名为prev，表示上一个访问的节点，让他与根节点的右节点比如果相等说明已经访问过了，可以出栈根。否则访问右节点。

void RearOrder_Nrec()//后序遍历非递归实现
	{
		stack s;
		Node* cur = _root;
		Node* prev = NULL;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			if (!s.empty())
			{
				Node* top = s.top();
				if (top->_right == prev)//判断是否已经访问了根节点的右子树
				{
					s.pop();
					cout << top->_data << " ";
					prev = top;
				}
				else
				{
					cur = top->_right;//如果没有就去访问右子树
					prev = top->_right;
				}
			}
		}
	}

 如果一棵树深度很大，那么非递归比递归的效率高很多，但是递归比非递归好理解，怎样取舍看情况吧。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。