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

Love The Way You Lie 2022-02-02 05:53 344阅读 0赞

### ** 二叉树的非递归遍历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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTI2NDcx_size_16_color_FFFFFF_t_70]: /images/20220202/cb3e2d812f0140bb82185b4dcbdac82f.png