二叉树的非递归遍历

template
void BinaryTree:: PrevOrderNoRec()
{
	if (_root == NULL)
	{
		return;
	}
	stack s;
	s.push(_root);

	while (!s.empty())
	{
		Node* top = s.top();//获取栈顶
		cout << top->_data << " ";
		s.pop();

		//右孩子入栈
		if (top->_rightChild)
		{
			s.push(top->_rightChild);
		}
		
		//左孩子入栈
		if (top->_leftChild)
		{
			s.push(top->_leftChild);
		}
	}
	cout << endl;
}


template
void BinaryTree::InOrderNoRec()
{
	if (_root == NULL)
	{
		return;
	}
	Node* cur = _root;
	stack s;
	while (cur||!s.empty())//如果栈为空并且cur==NULL跳出循环
	{
		//找到最左下方的节点访问
		while (cur)
		{
			s.push(cur);
			cur = cur->_leftChild;
		}
		
		Node* top = s.top();
		cout << top->_data << " ";
		s.pop();

		//如果右子树不为空则按照中序遍历，重新找到最左下角的继续访问
		if (top->_rightChild)
		{
			cur = top->_rightChild;
		}

		//如果右子树为空，则cur==NULL,不会再次进入循环，直接出栈访问
	}
	cout << endl;
}


template
void BinaryTree::PosOrderNoRec()
{
	if (_root == NULL)
	{
		return;
	}

	Node* cur = _root;//当前指针
	Node* prev = NULL;//栈内的前驱指针
	stack s;
	while (cur || !s.empty())
	{
		//找到最左下角节点
		while (cur)
		{
			s.push(cur);
			cur = cur->_leftChild;
		}

		Node* top = s.top();
		
		//如果右子树为空，或者之前访问过则输出
		if (top->_rightChild == NULL || prev == top->_rightChild)
		{
			cout << top->_data << " ";
			prev = top;//出栈之前更新prev
			s.pop();
		}
		else
		{
			cur = top->_rightChild;
		}
	}
	cout << endl;
}

网站栏目：二叉树的非递归遍历
标题来源：http://bzwzjz.com/article/gojccd.html