首先定义结点：

typedef struct BTree
{
    int    value;         //值
    struct BTree *lchild; //左孩子
    struct BTree *rchild; //右孩子
}BTree;

前序遍历建立二叉树－－递归

/* num 存储二叉树的前序序列 
** index 下标
*/
BTree *CreateBTree(BTree *node,int *num,int& index)
{
    /*以0为结束条件*/
    if(num[index] == 0)
        return NULL;
    else
    {
        node = new BTree;
        node -> value = num[index];
        node -> lchild = CreateBTree(node->lchild,num,++index);
        node -> rchild = CreateBTree(node->rchild,num,++index);
    }
    return node;
}

几种遍历

/*递归－－前序遍历*/
void preOrder(BTree * root)
{
    if(root == NULL)
        return;
    cout << root -> value << " ";
    preOrder(root -> lchild);
    preOrder(root -> rchild);
}
/*非递归－－前序遍历*/
void preOrder_dxm(BTree * root)
{
    stack<BTree*> S;
    BTree *p = root;
    while(p != NULL || !S.empty())
    {
        while(p != NULL)
        {
            cout << p -> value << " ";
            S.push(p);
            p = p -> lchild;
        }
        if(!S.empty())
        {
            S.pop();
            if(S.empty())
                return ;
            p = S.top();
            S.pop();
            p = p -> rchild;
        }
    }
}

/*递归－－中序遍历*/
void inOrder(BTree * root)
{
    if(root == NULL)
        return;
    inOrder(root -> lchild);
    cout << root -> value << " ";
    inOrder(root -> rchild);
}
/*非递归－－中序遍历*/
void inOrder_dxm(BTree * root)
{
    stack<BTree*> S;
    BTree *p = root;
    while(p != NULL || !S.empty())
    {
        while(p != NULL)
        {
            S.push(p);
            p = p -> lchild;
        }
        if(!S.empty())
        {
            p = S.top();
            cout << p -> value << " ";
            S.pop();
            if(S.empty())
                return ;
            p = S.top();
            cout << p -> value << " ";
            S.pop();
            p = p -> rchild;
        }
    }
}
/*递归－－后序遍历*/
void postOrder(BTree * root)
{
    if(root == NULL)
        return;
    postOrder(root -> lchild);
    postOrder(root -> rchild);
    cout << root -> value << " ";
}
/*非递归－－后序遍历*/
void postOrder_dxm(BTree * root)
{
    stack<BTree*> S;
    BTree *cur;
    BTree *pre = NULL;
    S.push(root);
    while(!S.empty())
    {
        cur = S.top();  //取栈顶元素

        /*叶子结点 或者 刚才打印的结点是当前结点的左孩子或右孩子时 输出*/
        if((cur -> lchild == NULL && cur -> rchild == NULL) || 
           (pre != NULL && (pre == cur -> lchild || pre == cur ->rchild)))
        {
            cout << cur -> value << " ";
            S.pop();
            pre = cur;  //pre  记录打印的结点
        }
        else
        {
            if(cur -> rchild != NULL)
                S.push(cur -> rchild);
            if(cur -> lchild != NULL)
                S.push(cur -> lchild);
        }
    }
}

树状打印

void print(BTree *root,int h)
{
    if(root != NULL)
    {
        print(root -> rchild,h+1);
        for(int i=0; i<h; i++)
            cout << "   ";
        cout << root -> value;
        print(root -> lchild,h+1);
    }
    cout << endl;
}

计算二叉树叶子节点的个数

int getleaves(BTree *root)
{
    if(root == NULL)
        return 0;
    if(root -> lchild == NULL && root -> rchild == NULL)
        return 1;

    return getleaves(root -> lchild) + getleaves(root -> rchild);
}

计算二叉树的深度

int getdepth(BTree *root)
{
    if(root == NULL)
        return 0;
    int depthlchild = getdepth(root -> lchild);
    int depthrchild = getdepth(root -> rchild);
    return (depthlchild > depthrchild) ? (depthlchild + 1) : (depthrchild + 1);
}

---

主函数

int main()
{
    int num[] = {1,2,4,8,0,0,9,0,0,5,10,0,0,11,0,0,3,6,12,0,0,13,0,0,7,14,0,0,15,0,0};
    BTree *root = NULL;
    int index = 0;
    root = CreateBTree(root,num,index);

    cout << "前序非递归遍历: " << endl;
    preOrder_dxm(root);
    cout << endl;

    cout << "中序递归遍历: " << endl;
    inOrder(root);
    cout << endl;

    cout << "后续非递归遍历: " << endl;
    postOrder_dxm(root);
    cout << endl << endl;

    cout << "此二叉树的形状为: " << endl;
    print(root,1);

    return 0;
}

打印结果：

..

---

根据前序和中序序列　或者　后序和中序序列建立二叉树

首先我们总结一下三种序列的规律：

前序遍历：根在前；子树在根后，且左子树比右子树靠前
中序遍历：根在中，左子树在根左边，右子树在根右边
后序遍历：根在后，子树在根前，且左子树比右子树靠前

已知二叉树的前序序列和中序序列，构造该二叉树的过程：

1.根据前序序列的第一个元素建立根节点；
2.在中序序列中找到该元素，确定根节点的左右子树的中序序列；
3.在前序序列中确定左右子树的前序序列；
4.由左子树的前序序列和中序序列建立左子树；
5.由右子树的前序序列和中序序列建立右子树。

已知二叉树的后序序列和中序序列，构造该二叉树的过程：

1.根据后序序列的最后一个元素建立根节点；
2.在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3.在后序序列中确定左右子树的后序序列；
4.由左子树的后序序列和中序序列建立左子树；
5.由右子树的后序序列和中序序列建立右子树。

---

给出先序和中序序列来建立二叉树，并树状输出

/*************************************************************************
    > File Name: 中序＆先序建立二叉树.cpp
    > Author: Tanswer
    > Mail: 98duxm@gmail.com
    > Created Time: 2016年10月24日 星期一 17时33分24秒
 ************************************************************************/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
typedef struct BTree
{
    char value;
    struct BTree *lchild;
    struct BTree *rchild;
}BTree;

/*
**pre ---前序序列
**in  ---中序序列
*/
BTree *Created(BTree *root,string pre,string in)
{

    if(pre.length() == 0)
    {
        root = NULL;
        return NULL;
    }
    //前序的第一个值　为　根
    int root_value = pre[0];
    //找到根在中序中的位置 :下标
    int index = in.find(root_value);
    //左孩子的中序序列
    string lchild_in = in.substr(0,index);
    //右孩子的中序序列
    string rchild_in = in.substr(index+1);
    //左孩子结点个数
    int lchild_length = lchild_in.length();
    //右孩子结点个数
    int rchild_length = rchild_in.length();
    //左孩子的前序序列
    string lchild_pre = pre.substr(1,lchild_length);
    //右孩子的前序序列
    string rchild_pre = pre.substr(1+lchild_length);

    root = new BTree;
    if(root != NULL)
    {
        root -> value = root_value;

        root -> lchild = Created(root -> lchild,lchild_pre,lchild_in);

        root -> rchild = Created(root -> rchild,rchild_pre,rchild_in);
    }
    return root;
}

/*树状打印二叉树*/
void print(BTree *root,int h)
{
    if(root != NULL)
    {
        print(root -> rchild,h+1);
        for(int i=0; i<h; i++)
            cout << "   ";
        cout << root -> value;
        print(root -> lchild,h+1);
    }
    cout << endl;
}

int main()
{
    cout << "先序序列为:  ABDECFG" << endl;
    cout << "中序序列为:  DBEAFCG" << endl;
    cout << "二叉树为: " << endl;;
    string pre = "ABDECFG";
    string in = "DBEAFCG";
    BTree *root = NULL;
    root = Created(root,pre,in);
    print(root,1);

    return 0;
}

输出结果：

---

给出后序和中序序列来建立二叉树，并树状输出

代码实现和上面类似，只需稍作改动即可。

/*
**pre ---前序序列
**in  ---中序序列
*/
BTree *Created(BTree *root,string post,string in)
{

    if(post.length() == 0)
    {
       root = NULL;
        return NULL;
    }

    /*后序序列的结点个数*/
    int size = post.size();

    //后序的最后一个值　为　根
    int root_value = post[size - 1];
    //找到根在中序中的位置 :下标
    int index = in.find(root_value);
    //左孩子的中序序列
    string lchild_in = in.substr(0,index);
    //右孩子的中序序列
    string rchild_in = in.substr(index+1);
    //左孩子结点个数
    int lchild_length = lchild_in.length();
    //右孩子结点个数
    int rchild_length = rchild_in.length();
    //左孩子的后序序列
    string lchild_post = post.substr(0,lchild_length);
    //右孩子的后序序列
    string rchild_post = post.substr(lchild_length,rchild_length);

    root = new BTree;
    if(root != NULL)
    {
        root -> value = root_value;

        root -> lchild = Created(root -> lchild,lchild_post,lchild_in);

        root -> rchild = Created(root -> rchild,rchild_post,rchild_in);
    }
    return root;
}

输出结果：