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

￡神魔★判官ぃ 2024-02-18 22:36 34阅读 0赞

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

#### **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;
    };