[C++知识库]C++非递归中序遍历

template<class T>
void linktree<T>::inordertravle()//非递归中序遍历
{
	if (rootpt == nullptr)
	{
		cout << "该结点为空" << endl;
		return ;
	}
	linkstack< treenode<T>* >s;
	treenode<T>* ptem = rootpt;
	while (ptem != nullptr || !s.isempty())
	{
		if (ptem != nullptr)//ptem = ptem->rpt后ptem可能为空指针，这种情况下需要直接出栈（直接出栈即得到现在ptem的双亲结点的双亲结点），跳过入栈和输出环节。
		{
			while (ptem->lpt != nullptr)
			{
				s.push(ptem);
				ptem = ptem->lpt;
			}
			//循环入栈左孩子，当前一个入栈的结点的下个结点为叶子结点时退出（叶子结点不需要入栈）
			cout << ptem->data << endl;
		}
		if (!s.isempty())
		{//栈不为空，即根节点的左子树还没有访问完时
			s.pop(ptem);//出栈，此时ptem指向之前输出左结点的根节点
			cout << ptem->data << endl;
			ptem = ptem->rpt;
		}
		else//栈中元素都弹出时表示根结点及其左子树都被输出，需要输出右子树
		{
			ptem = ptem->rpt;
		}
	}
}