二叉树的非递归遍历

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跳出循环
	{
		//找到最左下方的节点访问
		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<class T>
void BinaryTree<T>::PosOrderNoRec()
{
	if (_root == NULL)
	{
		return;
	}

	Node* cur = _root;//当前指针
	Node* prev = NULL;//栈内的前驱指针
	stack<Node*> 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;
}