二叉树的遍历（非递归）

由于二叉树的递归方法实际上是系统在使用栈进行操作，因此我们的迭代（非递归）方法也就需要使用栈进行模拟。

一、先序遍历

我们需要明白，进栈的元素都是树的根节点 root。
所以我们需要先访问该节点，再将该节点进栈。
【数据结构】树的非递归先序遍历、中序遍历算法_哔哩哔哩_bilibili二叉树的非递归后序遍历算法https://www.bilibili.com/video/BV1gV411U7XJ?from=search&seid=5899376191017226924&spm_id_from=333.337.0.0
感觉这个讲的很不错，其中使用了一个口诀：
1.无脑进栈
2.遇到NULL访问栈顶（也就是再找不到更小的左儿子了）
3.访问栈顶右孩子

只要是碰到新的结点（也就是新的root）那么就无脑进栈。

我们在编程的时候，先将结点输出，然后再进栈，也就是说，只要我们进栈的顺序就是我们的先序的数列顺序，那就实现了先序遍历。

最大的结束循环的条件就是：不仅仅它的左右儿子都是NULL了，而且栈里面是空的了（也就相当于将所有的结点都遍历了一遍）。

注意细节：root = s[top--]; //在访问某个结点D的右孩子的同时，也删掉了该结点D

//先序遍历
void PreOrder()
{
    s[NUM]; //构造的栈是为了存储左儿子的,因为右儿子不用存
    top = -1;
    while(root != NULL || top != -1) //先序(中左右):当到右侧的时候,就不需要保存右侧结点
    {
        while(root != NULL)
        {
            //一直向左侧找儿子，找到最小的左儿子
            printf("%d", root->data); //由于是先序，所以先输出根
            s[++top] = root;
            root = root->lchild;
        }
        if(top != -1)
        {
            //找到右侧的兄弟
            root = s[top--]; //在访问某个结点D的右孩子的同时，也删掉了该结点D
            root = root->rchild;
        }
    }
}

二、中序遍历

与先序遍历的大体都相同，唯一不同的点是：访问的时间不同（先序是在进栈的时候访问该节点，中序是在出栈的时候访问该节点）

出栈时候访问结点即可实现左中右顺序的原因：
由于我们循环无脑进栈（未碰到 root != NULL时）的最后一个一定是最左的儿子D，我们先让他出栈，然后我们在访问D的父结点以求得到D的兄弟时，也要将D的父亲结点出栈——这就是左中右的中，理所当然，当我们最后pop的结点时，就剩下右节点去pop了。

三、后序遍历