树的非递归遍历

树使用递归遍历非常方便，如果将代码拉伸开来，我们能否是否非递归代码来实现呢？当然是可以的，我们只要把递归的循环步骤修改为while就可以了。但我们需要借用到STL的栈模型来实现这个需求，具体的步骤如下：

• 步骤1：
  如果结点有左子树，该结点入栈，并放弃其左子树；
  如果结点没有左子树，访问该结点；
• 步骤2：
  如果结点有右子树，重复步骤1；
  如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1
  如果栈为空，表示遍历结束。

【实现代码】

TirTNode* findLeft(TirTNode* tree, std::stack<TirTNode*>& st)
{
	if (nullptr == tree) return nullptr;

	// 持续遍历，到没有左子树为止
	while (tree->leftChild != nullptr)
	{
		// 该结点入栈
		st.push(tree);
		// 并继续向下找左子树
		tree = tree->leftChild;
	}
	// 返回传递进来的 tree 最深的左子树
	return tree;
}

void myTreeOrder(TirTNode* tree)
{
	std::stack<TirTNode*> st;
	TirTNode* pLeft = findLeft(tree, st);
	// 返回回来的是没有左子树的节点
	while (nullptr != pLeft)
	{
		// 打印没有左子树的节点
		printf("%c ", pLeft->data);
		// 判断节点是否有右子树
		if (nullptr != pLeft->rightChild)
		{
			// 如果有，则遍历这个树下最深的左子树
			pLeft = findLeft(pLeft->rightChild, st);
		}
		else
		//如果节点没有右子树（节点访问完毕），弹出并访问栈顶元素，并且访问右子树
		{
			// 判断栈是否为空
			if (!st.empty())
			{
				// 访问栈顶元素
				pLeft = st.top();
				// 弹出
				st.pop();
			}
			else
			{
				// 遍历完成
				return;
			}
		}
	}
}

调用时，只需给 myTreeOrder 函数传递一个树根节点的地址就可以了。在函数内部会自动打印出每个节点的内容。

myTreeOrder(&treeA);