二叉树创建、递归和非递归前序、中序、后序遍历

二叉树的的创建和遍历是数据结构中的基本算法，在此统一归纳总结。
1.二叉树的定义

struct Node {
    //int data;
    char data;
    Node *left;
    Node *right;
}
;

打印方法：

void visit(char data) {
    //printf("%d", data);
    printf("%c", data);
}

2.前序遍历
前序遍历指的是先输出数据域，再左子树，最后右子树。
2.1递归遍历

void pre_order(Node *root) {
    if(root == NULL) {
        return;
    }
    visit(root->data);//数据域
    pre_order(root->left);//左子树
    pre_order(root->right);//右子树	
}

2.2非递归遍历
对于非递归遍历，需要采用栈存储数据，将已经访问的节点入栈，后续遍历完根节点和左子树之后需要出栈再遍历右子树。

void pre_order2(Node *root) {
    if(root == NULL)
        return;
    stack<node*> st;
    Node *p = root;
    while(p!= NULL || !st.empty()) {
        //边遍历边打印，并存入栈中，以后需要借助这些根节点进入右子树
        while(p!= NULL) {
            visit(p->data);
            st.push(p);
            p = p->left;
        }
        //当p为空时，说明根和左子树都遍历完了，该进入右子树了
        if(!st.empty()) {
            p = st.top();
            st.pop();
            p = p->right;
        }
    }
}

3.中序遍历
3.1递归遍历

/**
中序遍历
**/
void in_order(Node *root) {
    if(root == NULL)
        return;
    in_order(root->left);
    visit(root->data);
    in_order(root->right);
}

3.2非递归遍历

/**
中序非递归遍历
**/
//中序遍历
void in_order2(Node* root) {
    //空树
    if (root == NULL)
        return;
    //树非空
    Node* p = root;
    stack<node*> s;
    while (!s.empty() || p) {
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中
        while (p) {
            s.push(p);
            p = p->left;
        }
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        if (!s.empty()) {
            p = s.top();
            s.pop();
            visit(p->data);
            //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
            p = p->right;
        }
    }
}

4.后序遍历
4.1递归遍历

/**
后序遍历
**/
void post_order(Node *root) {
    if(root == NULL)
        return;
    post_order(root->left);
    post_order(root->right);
    visit(root->data);
}

4.2非递归遍历
非递归遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。

/**
后序遍历 非递归实现
**/
//后序遍历
void post_order2(Node* root) {
    if (root == NULL)
        return;
    stack<node*> s;
    //pCur:当前访问节点，pLastVisit:上次访问节点
    Node* pCur, *pLastVisit;
    //pCur = root;
    pCur = root;
    pLastVisit = NULL;
    //先把pCur移动到左子树最下边
    while (pCur) {
        s.push(pCur);
        pCur = pCur->left;
    }
    while (!s.empty()) {
        //走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
        pCur = s.top();
        s.pop();
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if (pCur->right == NULL || pCur->right == pLastVisit) {
            visit(pCur->data);
            //修改最近被访问的节点
            pLastVisit = pCur;
        }
        /*这里的else语句可换成带条件的else if:
else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
*/ else {
            //根节点再次入栈
            s.push(pCur);
            //进入右子树，且可肯定右子树一定不为空
            pCur = pCur->right;
            while (pCur) {
                s.push(pCur);
                pCur = pCur->left;
            }
        }
    }
}

5.创建二叉树

void creatBT(Node* &T)//建立一个二叉树 {
    char ch;
    scanf("%c",&ch);
    //读入字符
    if(ch=='#')//.代表空子树
        T = NULL; 
        else {
        T = (Node*)malloc(sizeof(Node));
        if(!T) {
            printf("开辟内存失败\n");
            exit(1);
        }
        T->data = ch;//给T赋值
        creatBT(T->left);//给左子树赋值
        creatBT(T->right);//给右子树赋值
        
    }
}

6.层次遍历二叉树

/**
层次遍历二叉树
**/
void PrintBFS(Node* root) {
    queue<node*> Q;
    Q.push(root);
    do {
        Node *node = Q.front();
        Q.pop();
        cout << node->data << " ";
        if (node->left)
            Q.push(node->left);
        if (node->right)
            Q.push(node->right);
    }
    while (!Q.empty());
}

7.二叉树的深度
我们可以从根节点即左右子树来理解二叉树的深度。对于任意一棵非空二叉树，有如下四种情况：
（1）如果一颗树只有一个节点，它的深度是1；
（2）如果根节点只有左子树而没有右子树，那么二叉树的深度应该是其左子树的深度加1；
（3）如果根节点只有右子树而没有左子树，那么二叉树的深度应该是其右树的深度加1；
（4）如果根节点既有左子树又有右子树，那么二叉树的深度应该是其左右子树的深度较大值加1；

/**
获取二叉树的深度
**/
int get_depth(Node *root) {
    if(root==NULL) {
        return 0;
    }
    int nLeft=get_depth(root->left);
    int nRight=get_depth(root->right);
    return nLeft>nRight?nLeft+1:nRight+1;
}

8.入口方法调用

int main() {
    cout << "开始创建二叉树" << endl;
    Node *root = NULL;
    //Create(root); 
    creatBT(root);
    if(root == NULL) {
        cout << "root is null, create fail!" << endl;
    }
    cout << "----先序遍历----" << endl;
    pre_order(root);
    cout << endl;
    cout << "----先序遍历非递归----" << endl;
    pre_order2(root);
    cout << endl;
    cout << "----中序遍历----" << endl;
    in_order(root);
    cout << endl;
    cout << "----中序遍历非递归----" << endl;
    in_order(root);
    cout << endl;
    cout << "----后序遍历----" << endl;
    post_order(root);
    cout << endl;
    cout << "----后序遍历非递归----" << endl;
    post_order2(root);
    cout << endl;
    cout << "----层次遍历----" << endl;
    PrintBFS(root);
    return 0;
}

创建如下图所示的二叉树。
输入节点：
ABDH##I##E##CF#J##G##（#表示空）
运行结果如下所示：

参考：
http://blog.csdn.net/zhangxiangdavaid/article/details/37115355
https://www.cnblogs.com/llhthinker/p/4906631.html
https://blog.csdn.net/K346K346/article/details/51076268