篇二：二叉树-创建、重建、

对于二叉树的创建，一般我们只熟悉最简单的二叉树创建方式，即逐个输入节点，然后按照先序遍历或者中序、后序遍历方式来递归建立二叉树。但是，光掌握这个是不够的，我们还得掌握二叉树的重建（先序中序重建二叉树，后序中序重建二叉树），数组转换为二叉树，链表转换为二叉树等等。

1、最简单的创建方式

我们可以根据先序遍历递归创建二叉树，当然也可以中序或者后序遍历方式创建二叉树。

struct node *creat() //前序建立
{
    struct node *root;
    char c;
    c = a[l1++];//li在int main函数里表现出来
    if(c == ',')
        return NULL;
    else
    {
        root = (struct node *)malloc(sizeof(struct node));
        root->data = c;
        root->l=creat();
        root->r=creat();
    }
    return root;

2、根据前序序列和中序序列建二叉树

根据二叉树的前序后中序遍历的结果来重建二叉树。 
前序：A B D E H I C F G 
中序：D B H E I A F C G

怎么做了？注意，前序遍历第一个节点A肯定是根节点；那么，我们可以在中序遍历中找到这个根节点A，那么中序遍历中根节点A左边的点（D B H E I）就是A的左子树的节点，右边的点（F C G）就是A节点右子树的节点。再看前序遍历的节点B，对于节点B也是一样，中序遍历中根节点B左边的点（D）就是B的左子树的节点，右边的点（H E I）就是B节点右子树的节点………

根据上述这种思想递归下去，可以逐步找到每个点的位置，然后就可以将树建立起来，具体看代码

struct node *creat(char a[], char b[], int n)//前序和中序建立二叉树
{
    int i;
    if(n == 0)
    {
        return NULL;
    }
    struct node *root;
    root = (struct node *)malloc(sizeof(struct node));
    root->data = a[0];
    for(i = 0; i < n; i++)
    {
        if(b[i] == a[0])
        {
            break;
        }
    }
    root->lc = creat(a+1,b,i);
    root->rc = creat(a+i+1,b+1+i,n-1-i);
    return root;
};

3、根据后序序列和中序序列建二叉树

struct node *creat(char a[], char b[], int n)//中序和后序建立二叉树
{
    int i;
    struct node *root;
    if(n == 0)
    {
        return NULL;
    }
    root = (struct node *)malloc(sizeof(struct node));
    root->data = b[n-1];
    for(i = 0; i < n; i++)
    {
        if(a[i] == b[n-1])
        {
            break;
        }
    }
    root->lc = creat(a,b,i);
    root->rc = creat(a+i+1,b+i,n-1-i);
    return root;
};