根据前序遍历序列和中序遍历序列创建二叉树-蒲公英云

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

悠悠 2022-07-15 01:15 229阅读 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");
}