树的非递归遍历

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