二叉樹的非遞歸遍歷也分為三種方式：前序、中序和后序。需要借助棧來實現(xiàn)。

那么新建個文件，把之前棧的代碼復(fù)制過來，再開始新的玩法。

二叉樹的創(chuàng)建可以繼續(xù)用之前的，借助棧其實也就是在遍歷時暫存一下結(jié)點，當左右子樹為空時再取出結(jié)點遍歷。原理想明白后其實也很簡單。

唯一一個有點區(qū)別和難點的就是后序遍歷，需要判斷棧頂?shù)膬煞N情況：

• 如果右子樹還未訪問或空，出站訪問結(jié)點
• 訪問棧頂結(jié)點，然后置空繼續(xù)訪問棧頂

完整代碼

//
// Created by wu on 19-1-24.
//
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 100


typedef struct BiNode {
    char data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

typedef BiTree ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

/**
 * 棧的初始化
 * @param S
 */
void init(SqStack *S) {
    S->top = -1;
}

/**
 * 創(chuàng)建二叉樹
 * @param T
 * @return
 */
bool created_tree(BiTree *T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL;
    } else {
        BiTree p = (BiTree) malloc(sizeof(BiNode));
        if (T == NULL) {
            printf("創(chuàng)建節(jié)點失敗，無法分配可用內(nèi)存...");
            exit(-1);
        } else {
            p->data = ch;
            *T = p;
            created_tree(&p->lchild);
            created_tree(&p->rchild);
        }
    }
    return true;
}

/**
 * 判空
 * @param S
 * @return
 */
bool stack_empty(SqStack *S) { // 結(jié)構(gòu)體操作，所以下邊用 . 操作
    return (S->top == -1) ? true : false;
}



/**
 * 進棧
 * @param S
 * @param x
 * @return
 */
bool push(SqStack *S, ElemType x) {
    if (S->top == MaxSize - 1) return false;
    S->top++;
    S->data[S->top] = x;
    return true;
}

/**
 * 出棧
 * @param S
 * @param x
 * @return
 */
ElemType pop(SqStack *S, ElemType x) {
    if (S->top == -1) return false;
    x = S->data[S->top--]; // x = S->top S.top = S->top -1
    return x;
}

/**
 * 先序遍歷
 * @param S
 * @param T
 */
void first_foreach_stack_tree(SqStack *S, BiTree T) {
    init(S);
    BiTree p = T;

    while (p || !stack_empty(S)) {
        while (p) {
            printf("%c ", p->data);
            push(S, p);
            p = p->lchild;
        }
        if (!stack_empty(S)) {
            p = pop(S, p);
            p = p->rchild;
        }
    }
}

void in_foreach_stack_tree(SqStack * S,BiTree T){
    init(S);
    BiTree p = T;

    while (p || !stack_empty(S)) {
        while (p) {
            push(S, p);
            p = p->lchild;
        }
        if (!stack_empty(S)) {
            p = pop(S, p);
            printf("%c ",p->data);
            p = p->rchild;
        }
    }
}


void rear_foreach_stack_tree(SqStack * S,BiTree T){
    init(S);
    BiTree p = T, r = NULL;

    while (p || !stack_empty(S)) {
        if(p){
            push(S, p);
            p=p->lchild;
        }else{
            p = S->data[S->top];
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                pop(S,p);
                printf("%c ",p->data);
                r = p;
                p = NULL;
            }
        }

    }
}