树的非递归遍历

树使用递归遍历非常方便,如果将代码拉伸开来,我们能否是否非递归代码来实现呢?当然是可以的,我们只要把递归的循环步骤修改为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);

 

发表评论