根据前序遍历序列和中序遍历序列创建二叉树

悠悠 2022-07-15 01:15 172阅读 0赞

**  一个前序遍历序列和一个中序遍历序列可以确定一颗唯一的二叉树。**

**       根据前序遍历的特点, 知前序序列(PreSequence)的首个元素(PreSequence\[0\])为二叉树的根(root),  然后在中序序列(InSequence)中查找此根(root),  根据中序遍历特点, 知在查找到的根(root) 前边的序列为根的左子树的中序遍历序列,  后边的序列为根的右子树的中序遍历序列。 设在中序遍历序列(InSequence)根前边有left个元素. 则在前序序列(PreSequence)中, 紧跟着根(root)的left个元素序列(即PreSequence\[1...left\]) 为根的左子树的前序遍历序列, 在后边的为根的右子树的前序遍历序列.而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为PreSequence\[1...left\]), 中序序列为InSequence\[0...left-1\], 分别为原序列的子串, 构造右子树同样, 显然可以用递归方法解决。每次将根结点的数据赋值，然后不断的递归调用创建左右子树，直到不存在左右子树时函数返回。**

**  二叉树的定义于下:**

typedef struct node
    {
        char data;    //结点数据
        struct node *Lchild;   //左孩子
        struct node *Rchild;  //右孩子
    }tree;   //树的结点

**  ** **完整代码如下：**

/*************************************************************************mZ
    	> Author: FengXin
    	> Mail: fengxinlinux@gmail.com
    	> Created Time: 2016年10月27日 星期四 20时01分43秒
     ************************************************************************/
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #include<sys/signal.h>
    #include<unistd.h>
    #include<sys/types.h>
    #include<sys/wait.h>
    #include<sys/stat.h>
    #include<fcntl.h>
    
    typedef struct node
    {
        char data;    //结点数据
        struct node *Lchild;    //左孩子
        struct node *Rchild;    //右孩子
    }tree;   //树的结点
    
    
    int  Lchild_len(char insequence[20],char root_data) //得到左孩子的长度
    {
        int len=strlen(insequence);
        int i=0;
        int sum=0;  //记录左孩子长度
        while(insequence[i]!=root_data)
        {
            i++;
            sum++;
        }
        return sum;
    }
    
    int Rchild_len(char insequence[20],char root_data)  //得到右孩子的长度
    {
        int i=0;
        int sum=0;   //记录右孩子长度
        while(insequence[i]!='\0'&&insequence[i++]!=root_data);
        while(insequence[i]!='\0')
        {
            sum++;
            i++;
        }
        return sum;
    }
    
    tree* create_tree(char presequence[20],char insequence[20]) //创建二叉树
    {
        tree* temp=(tree*)malloc(sizeof(tree));   //创建结点
        int L_len,R_len;      //储存左右孩子长度
        char L_presequence[20],L_insequece[20];   //创建左孩子时传入的左孩子的前序串和中序串
        char R_presequence[20],R_insequece[20];   //创建右孩子时传入的右孩子的前序串和中序串
        L_presequence[0]=L_insequece[0]=R_presequence[0]=R_insequece[0]='\0';
        if(strlen(presequence)!=0&&strlen(insequence)!=0)  //传入的序列串非空
        {
            temp->data=presequence[0];     //根结点数据赋值
            L_len=Lchild_len(insequence,presequence[0]);  //获得孩子的长度
            R_len=Rchild_len(insequence,presequence[0]);
            strncpy(L_presequence,presequence+1,L_len);    //得到要递归创建孩子时要传入的前序遍历串和中序遍历串
            *(L_presequence+L_len)='\0';              //字符串末尾加上'\0'
            strncpy(R_presequence,presequence+L_len+1,R_len);
            *(R_presequence+R_len)='\0';
            strncpy(L_insequece,insequence,L_len);
            *(L_insequece+L_len)='\0';
            strncpy(R_insequece,insequence+L_len+1,R_len);
            *(R_insequece+R_len)='\0';
            temp->Lchild=create_tree(L_presequence,L_insequece);   //递归创建左子树
            temp->Rchild=create_tree(R_presequence,R_insequece);   //递归创建右子树
            return temp;    //返回结点地址
        }
        else    //若根结点无孩子，则返回空指针
        {
            return NULL;
        }
    
    }
    
    void postorder(tree *root)  //后序遍历树输出
    {
        if(root!=NULL)
        {
            postorder(root->Lchild);
            postorder(root->Rchild);
            printf("%3c",root->data);           
        }
        else
        return;
    
    }
    
    int main()
    {
        char presequence[20];  //存先序序列
        char insequence[20];   //存中序序列
        tree *root;
    
        printf("请输入先序序列\n");
        scanf("%s",presequence);
        printf("请输入中序序列\n");
        scanf("%s",insequence);
        root=create_tree(presequence,insequence);
        printf("创建二叉树成功\n");
        printf("后序遍历输出为:\n");
        postorder(root);
        printf("\n");
        
    }