二叉樹(shù)的非遞歸遍歷

template<class T>
void BinaryTree<T>:: PrevOrderNoRec()
{
	if (_root == NULL)
	{
		return;
	}
	stack<Node*> 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<class T>
void BinaryTree<T>::InOrderNoRec()
{
	if (_root == NULL)
	{
		return;
	}
	Node* cur = _root;
	stack<Node*> s;
	while (cur||!s.empty())//如果棧為空并且cur==NULL跳出循環(huán)
	{
		//找到最左下方的節(jié)點(diǎn)訪問(wèn)
		while (cur)
		{
			s.push(cur);
			cur = cur->_leftChild;
		}
		
		Node* top = s.top();
		cout << top->_data << " ";
		s.pop();

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

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


template<class T>
void BinaryTree<T>::PosOrderNoRec()
{
	if (_root == NULL)
	{
		return;
	}

	Node* cur = _root;//當(dāng)前指針
	Node* prev = NULL;//棧內(nèi)的前驅(qū)指針
	stack<Node*> s;
	while (cur || !s.empty())
	{
		//找到最左下角節(jié)點(diǎn)
		while (cur)
		{
			s.push(cur);
			cur = cur->_leftChild;
		}

		Node* top = s.top();
		
		//如果右子樹(shù)為空，或者之前訪問(wèn)過(guò)則輸出
		if (top->_rightChild == NULL || prev == top->_rightChild)
		{
			cout << top->_data << " ";
			prev = top;//出棧之前更新prev
			s.pop();
		}
		else
		{
			cur = top->_rightChild;
		}
	}
	cout << endl;
}