前序遍历的非递归算法
<法一>
思路：
二叉树的前序遍历过程：
- 从树根开始沿着左子树一直深入，直到最左端无法深入时，返回；
- 进入最近深入时遇到结点的右子树，再进行如此的深入和返回；
- 直到最后从根节点的右子树返回到根节点为止；
由其深入返回的过程我们知道可以用一个栈来帮助我们消除递归
1.存入根结点：首先判断root（根节点）是否为空，如果为空则直接return，不为空就将根节点压入栈中。这里我随机生成一个树作为例子，
→
2.进行非递归前序遍历：将A弹出，打印出A结点存入的值，接着再依次检查A是否有右孩子（Rson）和左孩子（Lson）（因为是前序遍历，而栈的特点是先进后出，我们需要优先打印左孩子的值，所以先检查是否有右孩子，如果有的话将右孩子优先压入栈中），如果有的话依次存入栈中，此时栈中全是第二层的元素
随后我们再弹出栈顶结点B，打印他的值，接着依葫芦画瓢，分别再次检查B的右孩子和左孩子，如果有的话分别存入，因为B没有左孩子，所以第三次压栈存入D结点
再次弹出D结点，存入其右孩子和左孩子，栈更新为：
因为G，F为叶子结点，没有孩子，所以分别弹出F，G并打印值，目前为止打印出：ABDFG;
当栈中只剩C时，弹出C，打印值，因为C有右孩子，所以存入其右孩子E，栈更新为：
最后，弹出E，存入其右孩子H:
因为G是叶子结点，所以弹出G后栈为空，整个树也遍历完毕，由此可以得到循环的条件是当且仅当栈不为空时
3.观察特点进行总结：只要左子树还没有遍历完，就会弹出元素的同时，存入新的元素，直到左子树全部被遍历完没有新的元素存入，才会开始遍历右子树，这也构成我们的中序遍历。
代码实现如下：
typedef struct BiTNode
{
char data;
struct BiTNode *lson, *rson;
} BiTNode, *BiTree; //二叉树的结构体
// 二叉树的前序遍历算法1基于STL stack
void PreOrder1(BiTree bt)
{
stack<BiTree> Stack;
if (bt == NULL) //如果根结点为空，直接return
return;
Stack.push(bt); //根结点不为空将其压入栈中
while (!Stack.empty()) //循环条件：当栈不为空时
{
BiTree Cur = Stack.top();
cout << Cur->data << endl;
Stack.pop(); //取出并打印栈顶元素
if (Cur->rson)
Stack.push(Cur->rson);
if (Cur->lson)
Stack.push(Cur->lson); //分别将栈顶元素的右孩子和左孩子压入栈中
}
}<法二>
思路：
1.连续将结点的左孩子压入栈中：此处我仍用这个生成的树进行演示，法二的主要思路是只要当前节点指向左孩子的指针不为NULL，就一直打印当前节点值并压入栈中。
→
打印：AB
2.弹出栈顶元组：直到一个结点没有左孩子时，此时退出循环，此时只有从B的右孩子D进行入手，所以我们弹出栈顶元素B，并将指针指向该节点的右孩子D，重复第一步的操作：
3.重复1，2步：循环到F时又退出了，我们再重复第二步的操作，弹出F，而F也没有右孩子，所以继续弹出D，将节点指针指向D的右孩子G，继续循环：
→
→
→
注意：由于C，E，H只有右孩子没有左孩子所以只能弹出C后E才能进栈，弹出E后C才能进栈
3.循环结束条件：如果初始的根结点为空，则循环直接退出，进入循环后如果栈中没有新增元素，并且没有新增元素即将入栈（即当前指向的结点为空），代表遍历完成，此时退出循环。
代码实现如下：文章来源：https://www.toymoban.com/news/detail-413225.html
// 二叉树的前序遍历算法2基于STL stack
void PreOrder2(BiTree bt)
{
stack<BiTree> Stack;
BiTree Cur;
while (!Stack.empty() || bt != NULL) //循环终止条件
{
while (bt != NULL)
{
cout << bt->data << endl;
Stack.push(bt);
bt = bt->lson;
}
if (!Stack.empty())
{
Cur = Stack.top();
Stack.pop();
bt = Cur->rson;
}
}
}文章来源地址https://www.toymoban.com/news/detail-413225.html
到了这里，关于二叉树先序，中序，后序遍历的非递归算法（一）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
