• 前序遍历，中序遍历，后序遍历，层次遍历，深度遍历 参考
  深度遍历 本质上就是 前序遍历

C++ 实现

• 二叉树前序、中序、后序遍历非递归写法的透彻解析

// 2019.5.24 
// 二叉树的递归与非递归遍历

# include <stdio.h>
# include <stdlib.h>
# include <stack>
# include <iostream>
using namespace std;

// 节点信息
struct TreeNode{
    int val;
    struct TreeNode *left;   // 左孩子
    struct TreeNode *right;  // 右孩子
};

// 节点的数值
int node_of_tree[20] = {1, 2, 4, 0, 0, 5, 7, 0, 0, 8, 0, 0, 3, 0, 6, 0, 0}; 

// 创建二叉树树
struct TreeNode *create(struct TreeNode *root, int& x){
    if(node_of_tree[x] == 0){
        root = NULL;
        x += 1;
    }
    else{
        root = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
        root -> val = node_of_tree[x];
        x += 1;
        root -> left  = create(root -> left,  x);
        root -> right = create(root -> right, x);
    }
    return root;
}

// 前序遍历 -> 递归实现
void qianxu_digui_yes(struct TreeNode *root){
    if(root){
        printf("%d ", root -> val);
        qianxu_digui_yes(root -> left);
        qianxu_digui_yes(root -> right);
    }
}

// 前序遍历 -> 非递归实现
void qianxu_digui_no(struct TreeNode *root){
    if(root == NULL){
        cout << " 二叉树为空 " << endl;
        return;
    }

    stack<TreeNode *> sk;
    TreeNode *p = root;
    while(!sk.empty() || p){
        if(p){
            cout << p->val << " ";
            sk.push(p);
            p = p-> left;
        }
        else{
            p = sk.top();
            sk.pop();
            p = p -> right;
        }
    }
    printf("\n\n");
}

// 中序遍历 -> 递归实现
void zhongxu_digui_yes(struct TreeNode *root){
    if(root){
        zhongxu_digui_yes(root -> left);
        printf("%d ", root -> val);
        zhongxu_digui_yes(root -> right);
    }
}
// 中序遍历 -> 非递归实现
void zhongxu_digui_no(struct TreeNode *root){
    if(root == NULL){
        cout<<" 二叉树为空 " << endl;
        return;
    }

    stack<TreeNode *> sk;
    TreeNode *p = root;
    while(!sk.empty() || p){
        if(p){
            sk.push(p);
            p = p -> left;
        }
        else{
            p = sk.top();
            sk.pop();
            cout << p->val << " ";
            p = p -> right;
        }
    }
    printf("\n\n");
}

// 后序遍历 -> 递归实现
void houxu_digui_yes(struct TreeNode *root){
    if(root){
        houxu_digui_yes(root -> left);
        houxu_digui_yes(root -> right);
        printf("%d ", root -> val);
    }
}
// 后序遍历 -> 非递归实现
void houxu_digui_no(struct TreeNode *root){
    if(root == NULL){
        cout<<" 二叉树为空 " << endl;
        return;
    }

    stack<TreeNode *> sk;
    TreeNode *p, *lastvisit;
    p = root;
    lastvisit = NULL;

    while(p){
        sk.push(p);
        p = p->left;
    }

    while(!sk.empty()){
        p = sk.top();
        sk.pop();

        if(p->right == NULL || p->right == lastvisit){
            cout << p->val << " ";
            lastvisit = p;
        }
        // else if(p->left == lastvisit)
        else{
            sk.push(p);
            p = p -> right;

            while(p){
                sk.push(p);
                p = p -> left;
            }
        }
    }
    printf("\n\n");
}

// 主函数
int main(){
    struct TreeNode *root = NULL;
    int x = 0;
    root = create(root, x);

    printf(" 前序遍历递归实现   ->> ");
    qianxu_digui_yes(root); cout<<endl;
    printf(" 前序遍历非递归实现 ->> ");
    qianxu_digui_no(root);

    printf(" 中序遍历递归实现   ->> ");
    zhongxu_digui_yes(root); cout<<endl;
    printf(" 中序遍历非递归实现 ->> ");
    zhongxu_digui_no(root);

    printf(" 后序遍历递归实现   ->> ");
    houxu_digui_yes(root); cout<<endl;
    printf(" 后序遍历非递归实现 ->> ");
    houxu_digui_no(root);
    return 0;
}