先序中序还原二叉树 和 中序后序还原二叉树 总结

时间:2022-06-06 20:44:40

遍历二叉树有三种方法

①先序:先遍历根结点,后遍历左子树,最后遍历右子树

②中序:先遍历左子树,后遍历根结点,最后遍历右子树

③后序:先遍历左子树,后遍历右子树,最后遍历根结点

先序中序还原二叉树:

  给出的先序遍历的结点序列第一个结点肯定是二叉树的根结点,在中序遍历序列中找到该结点,然后对左子树和右子树进行相同的递归函数调用。

  左子树:中序序列取根结点右半边序列,设右半边长为n,先序序列取从根结点后面一个结点开始序列长为n的序列;

  右子树:中序序列取根结点左半边序列,先序序列取a+n+1;

代码:

struct node *create(char a[], char b[], int n)
{
    struct node *root;
    root = (struct node*)malloc(sizeof(struct node));
    if(n==0)
        return NULL;
    root->data = a[0];
    char *p;
    for(p=b; p!='\0'; p++)           // 在中序遍历序列中找到先序遍历序列的第一个值(根结点)
        if(*p==a[0])
        break;
    int t;
    t=p-b;                                  //t为左侧子树包含的结点个数
    root->l=create(a+1, b, t);                            //对根结点左侧序列进行遍历
    root->r=create(a+t+1, p+1, n-t-1);              //对根结点右侧序列进行遍历
    return root;
}


中序后序还原二叉树:

  与先序中序类似,后序序列最后一个结点是二叉树的根结点,在中序序列中找到该结点,然后对左子树和右子树进行相同的递归函数调用。

  左子树:中序序列取根结点左半部分,设左半部分结点数为n,后序序列取从头开始长度为n的序列;

  右子树:中序序列取根结点右半部分,后序序列取从n+1开始到倒数第二个结点结束的长度的序列

 代码:

struct node *create(char a[], char b[], int n)
{
    struct node *root;
    root = (struct node*)malloc(sizeof(struct node));
    if(n<=0)
        return NULL;
    else
    {
        root->data = b[n-1];
        char *p;
        for(p=a; p!='\0'; p++)
        {
            if(*p == b[n-1])
                 break;
        }
        int t = p - a;
        root->l = create(a, b, t);
        root->r = create(a+t+1, b+t, n-t-1);
        return root;
    }
}