C/C++ 二叉树的非递归遍历（前序、中序、后序非递归遍历）-蒲公英云

C/C++ 二叉树的非递归遍历（前序、中序、后序非递归遍历）

二叉树的非递归遍历C/C++实现：

非递归先序遍历代码：

void PreOrderTraversal (struct tree* root) {  //非递归先序遍历
    struct tree* temp = root;
    while (temp != NULL || S.top > 0) {
        while (temp != NULL) {
            cout << temp->data << " ";
            Push(temp);
            temp = temp->left;
        }
        if (S.top != 0) {
            temp = Pop();
            temp = temp->right;
        }
    }
    cout << endl;
}

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTI2NDcx_size_16_color_FFFFFF_t_70

思路：例如上面这棵二叉树，前序遍历的序列为（根-左-右）：5 2 3 6 11 4 8；那么首先我们访问到5时先把5输出，然后再入栈，然后再去访问它的左子结点，直到访问到3这个结点往下再没有左结点时把栈顶元素出栈，然后在访问栈顶元素的右子结点。

非递归的中序遍历和后序遍历的思路和前序遍历差不多，大家自己看代码理解领悟，多思考，多动笔画一下结点入栈时栈内元素时怎样的，这样才能更加深入的理解树的遍历。

/* 完整代码 */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stack>
using namespace std;
#define ElementType string
#define MaxSize 100
struct tree{
    ElementType data;
    int tab;
    struct tree* left;
    struct tree* right;
};
typedef struct stack {
    struct tree* Stree[MaxSize];
    int top;
}Stack;
Stack S; //定义栈
void Initialize () { //初始化栈
    S.top = 0;
}
void Push(struct tree* dummy) { //入栈
    S.Stree[S.top++] = dummy;
}
struct tree* Pop() { //出栈
    return S.Stree[--S.top];
}
bool empty() { //判断栈是否为空
    return S.top == 0;
}
struct tree* creatTree (struct tree* root) { //创建二叉树
    ElementType val;
    cin >> val;
    if (val == ".")
        return NULL;
    root = (struct tree*)malloc(sizeof(struct tree));
    root->data = val;
    cout << "请输入" << root->data << "的左子树：";
    root->left =  creatTree(root->left);
    cout << "请输入" << root->data << "的右子树：";
    root->right = creatTree(root->right);
    return root;
}
void PreOrderTraversal (struct tree* root) {  //非递归先序遍历
    struct tree* temp = root;
    while (temp != NULL || S.top > 0) {
        while (temp != NULL) {
            cout << temp->data << " ";
            Push(temp);
            temp = temp->left;
        }
        if (S.top != 0) {
            temp = Pop();
            temp = temp->right;
        }
    }
    cout << endl;
}
void InOrderTraversal (struct tree* root) {  //非递归中序遍历
    struct tree* temp = root;
    while (temp != NULL || S.top > 0) {
        while (temp != NULL ) {
            Push(temp);
            temp = temp->left;
        }
        if (S.top != 0) {
            temp = Pop();
            cout << temp->data << " ";
            temp = temp->right;
        }
    }
    cout << endl;
}
void PostOrderTraversal (struct tree* root) { //非递归后序遍历
    struct tree* temp = root;
    while (temp != NULL || S.top > 0) {
        while (temp != NULL) {
            temp->tab = 1;
            Push(temp);
            temp = temp->left;
        }
        if (S.top > 0) {
            temp = Pop();
            if (temp->tab == 1) {
                temp->tab ++;
                Push(temp);
                temp = temp->right;
            }else {
                if (temp->tab == 2) {
                    cout << temp->data << " ";
                    temp = NULL;
                }
            }
        }
    }
    cout << endl;
}
void NotPostOrder(struct tree* root) { //非递归:后序遍历(双栈法，更简单，易理解)
    //思路：先放根然后放右孩子，最后放左孩子
    stack<struct tree*> ans;
    stack<struct tree*> out;
    struct tree* Node = root;
    while (Node != NULL || !ans.empty()) {
        if (Node != NULL) {
            ans.push(Node);
            out.push(Node);
            Node = Node->right;
        }else {
            Node = ans.top();
            Node = Node->left;
            ans.pop();
        }
    }
    while (!out.empty()) {
        cout << out.top()->val << " ";
        out.pop();
    }
}
int main() {
    cout << "请输入头节点：";
    struct tree* root = creatTree(root);
    Initialize();
    PreOrderTraversal(root);
    InOrderTraversal(root);
    PostOrderTraversal(root);
    return 0;
}