二叉樹的非遞歸遍歷

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跳出循環(huán)
	{
		//找到最左下方的節(jié)點訪問
		while (cur)
		{
			s.push(cur);
			cur = cur->_leftChild;
		}
		
		Node* top = s.top();
		cout << top->_data << " ";
		s.pop();

		//如果右子樹不為空則按照中序遍歷，重新找到最左下角的繼續(xù)訪問
		if (top->_rightChild)
		{
			cur = top->_rightChild;
		}

		//如果右子樹為空，則cur==NULL,不會再次進入循環(huán)，直接出棧訪問
	}
	cout << endl;
}


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

	Node* cur = _root;//當前指針
	Node* prev = NULL;//棧內的前驅指針
	stack s;
	while (cur || !s.empty())
	{
		//找到最左下角節(jié)點
		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://m.jiaotiyi.com/article/gojccd.html