swust oj 983和984 利用二叉树中序及后序遍历确定该二叉树的先序序列

2021年9月20日 7点热度 0条评论 来源: saradudu

思路:
1.983:当前树的后续遍历的最后一个元素肯定是根节点。中序遍历中根节点左边是左子树,右边是右子树,递归处理。
2.984:当前树的先续遍历的第一个元素肯定是根节点。中序遍历中根节点左边是左子树,右边是右子树,递归处理。
3.两种方法进行顺序相反

983: 利用二叉树中序及后序遍历确定该二叉树的先序序列
题目描述
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果,要求输出其先序遍历结果。
输入
第一行为中序序列
第二行为后续序列
输出
输出为遍历二叉树得到的先序序列
样例输入
BFDAEGC
FDBGECA
样例输出
ABDFCEG

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define Max 100
int x;
typedef char datatype;
typedef struct node
{ 
    datatype data;
    struct node *lchild;
    struct node *rchild;

}tree;
void Creat(tree *&T,char *in,char *hou,int x)//*in,*hou指针数组,x表示当前子树的元素个数
{ 
    int k;//长度
    char *p;//来判断中序进行位置的间接指针
    if(x<=0)//无子树元素即子树为空
    { 
        T=NULL;
        return ;
    }
    T=(tree *)malloc(sizeof(tree));//申请空间
    T->data=*hou;//后序的最后一个元素为根节点
    for(p=in;p>in-x;p--)//从先序的最后一个位置开始向前找当前根节点
    { 
        if(*p==*hou)
            break;
    }
    k=in-p;//k代表子树长度
    Creat(T->rchild,in,hou-1,k);//循环进行,注意指针所指的位置
    Creat(T->lchild,p-1,hou-k-1,x-k-1);//第二个变量是:中序的该子树元素中的最后一个元素的位置,第三个变量是:后序的该子树元素中的最后一个元素的位置,
}
void displaypre(tree *&T)
{ 
    if(T!=NULL)
    { 
        printf("%c",T->data);
        displaypre(T->lchild);
        displaypre(T->rchild);
    }
}
int main()
{ 
    tree *T=NULL;
    char in[Max],hou[Max];
    scanf("%s %s",in,hou);
    x=strlen(in);//x是长度
    Creat(T,in+x-1,hou+x-1,x);//后序判断要从最后一个元素开始向前进行
    displaypre(T);
    return 0;
}

984: 利用二叉树中序及先序遍历确定该二叉树的后序序列
题目描述
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果。
输入
输入数据占2行,其中第一行表示中序遍历结果,第二行为先序遍历结果。
输出
对测试数据,输出后序遍历结果。
样例输入
BFDAEGC
ABDFCEG
样例输出
FDBGECA

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define Max 100
typedef char datatype;
typedef struct node
{ 
    datatype data;
    struct node *lchild;
    struct node *rchild;
}tree;
void Creat(tree *&T,char *in,char *pre,int x)
{ 
    int k=0;
    char *p;
    if(x<=0)
    { 
        T=NULL;
        return ;
    }
    T=(tree *)malloc(sizeof(tree));
    T->data=*pre;
    for(p=in;p<in+x;p++)
    { 
        if(*p==*pre)
            break;
    }
    k=p-in;
    Creat(T->lchild,in,pre+1,k);//第二个变量是:中序的该子树元素中的第一个元素的位置,第三个变量是:先序的该子树元素中的第一个元素的位置,
    Creat(T->rchild,p+1,pre+k+1,x-k-1);
}
int displayhou(tree *&T)
{ 
    if(T!=NULL)
    { 

        displayhou(T->lchild);
        displayhou(T->rchild);
        printf("%c",T->data);

    }
}
int main()
{ 
    tree *T=NULL;
    char in[Max],pre[Max];
    scanf("%s %s",in,pre);
    int x=strlen(in);
    Creat(T,in,pre,x);//先序判断要从第一个元素开始向前进行
    displayhou(T);
    return 0;
}

    原文作者:saradudu
    原文地址: https://blog.csdn.net/weixin_45733897/article/details/106421751
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。