用栈进行非递归实现前中后遍历二叉树

•  分析是用栈还是用队列进行先序遍历二叉树？

         如果用队列：先进先出。用下图所示二叉树进行举例分析：

       入队：a b d 还是a b c呢？本应该是进行abd的顺序出队（先进先出，队头出队），但是 这样的话C就没办法保存，想要存放左右孩子必须记录其根节点。因此就陷入了矛盾。而用栈访问的话，访问完左子树后，还问访问根节点a（a还未出栈），a就能保存起来进而通过a去访问右子树。所以只能用栈进行非递归遍历。

1. 先序遍历

•  先序：根->左->右
•  栈：先进后出
•  出栈顺序：出栈顶元素
•  步骤：

          ① 将根节点入栈 

          ② 判断树是否为空，不为空则获取栈顶元素并出栈

          ③ 将刚出栈元素的右、左孩子依次进行入栈

          ④ 将①②③循环，直至队列为空时，停止

•  举例上面的树图进行思路演绎：

               （说明：灰色字母是已经出栈元素，下划线代表目前栈顶元素，蓝色是刚入栈元素）

                入栈：a

                出栈：a  //判断栈是否为空，不为空则出栈

                入：a c b  //cb分别为a右、左孩子

                出：b   //出栈顶元素b

                入：a c b e d  //将刚出栈的元素b的右左孩子ed入栈

                出：d->e-> c   //出d,而d无左右孩子无序入栈，进而出e,e无左右孩子无序入栈，进而出c

                入：c b e d g  f      //将刚出栈的元素c的右左孩子gf入栈

                出：f  //出栈顶元素f

                入：c b e d g  f  h  //将刚出栈的元素f的左孩子h入栈

                出：h g

                此时所有元素均已出栈，栈内为空

• 非递先序归遍历代码：

 
typedef struct node
{
    char value;//当前节点值
    struct node* left;//指向当前节点左孩子指针
    struct node* right;//指向当前节点右孩子指针
}Node;
 
//非递归前序遍历
void PreOrder_1(Node* root)
{
    stackss;//定义栈，存储指向结点的指针
    if (root == NULL)
    {
        return;
    }
    ss.push(root);//根节点入栈
    Node* top = NULL;//top指向栈顶元素
    while (!ss.empty())
    {
        top = ss.top();
        printf("%c", top->value);
        ss.pop();//出栈
        //将当前top结点的右左孩子依次入栈
        if (top->right != NULL)
            ss.push(top->right);
        if (top->left != NULL)
            ss.push(top->right);
    }
    printf("\n");
}

---

1. 中序遍历

• 中序：左->根->右
• 思路：一直往左走，走到左子树的最左端，访问该结点。中途在走到最左端结点的路途中访问的各个结点保存，将其压栈内先不出栈（也就是当前左子树的分支上所有节点都要入栈），否则无法访问左右孩子。
• 步骤：

          ① 定义p结点，指向根节点

          ② 从当前p开始，如果不为空，依次将左子树入栈

          ③ 判断栈是否为空，如果不为空，获取栈顶top，出栈并输出，然后用指针p记住当前出栈结点的右孩子。

          ④循环②③，直到p为空弄且栈为空时停止

        （请将思路结合下面的思路演绎和伪代码进行理解）

•  伪代码：

• 举例上面的树图进行思路演绎：

               （说明：灰色字母是已经出栈元素，下划线代表目前栈顶元素，蓝色是刚入栈元素）

                入栈：a b d   //首先p指向根节点a进行循环查找该子树的最左端数值d，途中b入队，d入队后发现此时d无左孩子，p=NULL,退出内while循环，进入if函数。

                出栈：d b  //栈不为空，栈顶元素d出栈，d无右孩子，p=NULL。下一步进入外while循环，此时p=null,栈不空,无法进入内while循环，可进入If循环，然后b元素作为此时的栈顶元素，出栈

                入：a b d e  //b出栈后，b有右孩子e,p指向e结点，p!=NULL,进入内while循环，e入栈

                出：e   //e入栈后，在内while循环中，e无左孩子，p=NULL。栈不为空进入if函数栈顶元素e出栈。e出栈后，e无右孩子，p=NULL。进入外while循环，p=NULL无法进屋内while循环，栈不空可进入if循环。对此时栈顶元素a进行出栈

                入：a b d e  c  f  h //a出栈后，p=a的右孩子，p指向c，进入外while循环满足条件进入内while循环，依次找到最左端结点，期间将c f h依次入栈内，直到h结点无左孩子,p=NULL,退出内while1循环，进入if条件内。

                出：h->f-> c   //if条件内,h作为栈顶元素，出栈。h无右孩子，p=NULL,不满足内while条件，在if函数内继续对栈顶元素f出栈。同理f无右孩子，p=NULL，c出栈。

                入：a b d e  c  f  h   g  //c出栈后,c有右孩子g，p指向g，p!=NULL,对g进行入栈

                出：g  //g无左孩子，p=NULL,退出内while循环，进入if条件内，g出栈

                此时所有元素均已出栈，栈内为空

• 代码：

 
typedef struct node
{
    char value;//当前节点值
    struct node* left;//指向当前节点左孩子指针
    struct node* right;//指向当前节点右孩子指针
}Node;
 
//非递归中序遍历输出二叉树
void InOrder_1(Node* root)
{   
    Node* p = root, * top = NULL;
    stackss;//定义栈，存储指向结点的指针
    if (root == NULL)
    {
        return;
    }
    while (p != NULL || !ss.empty())
    {
        //从p开始，所有分支入栈
        while (p != NULL)
        {
            ss.push(P);
            p = p->left;
        }
        if (!ss.empty())
        {
            top = ss.top();
            ss.top();
            printf("%c", top->value);
            p = p->right;
        }
 
    }
    printf("\n");
}

1. 后序遍历

• 步骤：

          ① 定义pre结点，指向上次一次出栈的结点，用来判断栈顶元素左右孩子是否出栈。

          ② 入栈：如果当前结点有孩子，则按照右左的顺序入栈

          ③ 出栈：1.当前栈顶结点没有孩子，则当前结点出栈

        （请将思路结合下面的思路演绎和伪代码进行理解）

•  伪代码：

•  举例上面的树图进行思路演绎：

               （说明：灰色字母是已经出栈元素，下划线代表目前栈顶元素，蓝色是刚入栈元素）

                入栈：a c b  e  d //先入根节点a，然后根、右、左的顺序将c b入栈，然后b作为栈顶元素，按照右、左的顺序将e d入栈，栈顶元素d既无左孩子又没右孩子，开始出栈。

                出栈：d e b  //栈顶元素d无孩子出栈，同理，e出栈。b左右孩子为de，均已出栈，b也出栈。

                入：a c b  e  d  g f h//c未出栈，将右左孩子gf入栈。f作为新栈顶元素，将其左孩子h入栈

                出：h  f g c a //h无左右孩子，h出栈。f的孩子h已经出栈，f出栈。g无左右孩子，g出栈。c的孩子fg已经出栈，c出栈。a的孩子bc已经出栈，a出栈。

                此时所有元素均已出栈，栈内为空

• 代码：

 
typedef struct node
{
    char value;//当前节点值
    struct node* left;//指向当前节点左孩子指针
    struct node* right;//指向当前节点右孩子指针
}Node;
//非递归后序遍历输出二叉树
void PostOrder(Node* root)
{
    Node* pre = NULL, * top = NULL;
    stackss;//定义栈，存储指向结点的指针
    if (root == NULL)
    {
        return;
    }
    ss.push(root);
    while (!ss.empty())
    {
        top = ss.top();
        if (top->left == NULL && top->right == NULL || pre != NULL && pre = top->left || pre == top->right)
        {
            printf("%c", top->value);
            ss.pop();
            pre = top;
        }
        else
        {
            if (top->right != NULL)
                ss.push(top->right);
            if (top->left != NULL)
                ss.push(top->right);
        }
    }
    printf("\n");
}

 完整代码：

（过两天补上，摸鱼..)

  注：上述代码中创建二叉树的代码参考：创建二叉树

运行结果：