回 帖 发 新 帖 刷新版面

主题:跪求算法[已知后序和中序序列,如何恢复二叉树]

求,如题的算法。基本思想我明白,可就是一写算法就糊涂了。求一个详细的算法,网上很多都是已知先序和中序来恢复二叉树,我想要后序和中序恢复二叉树。谢谢了,给答案狂加分啊,有源代码加分加到你爽,很急

回复列表 (共3个回复)

沙发

我没有构造二叉树,而是用字符串的形式存储二叉树的各种序列.程序比较粗糙,仅供参考.
#include<stdio.h>
#include<string.h>
#define MAX 1000

void Drive(const char a[], const char b[], char c[]);
int TheLast(const char a[], const char b[], int lenA, int left, int right);
int Print(const char a[], const char b[], char c[], int lenA, int lenC, int left, int right);

int main()
{
    char a[] = "debfgca"; //后序序列 
    char b[] = "dbeafcg"; //中序序列 
    char c[MAX];  //前序序列  
    
    Drive(a, b, c);//主要操作过程 
    
    puts(a);
    puts(b);
    puts(c);
    
    getchar();
    return 0;
}

/*
函数功能:递归求前序序列的驱动程序,同时给出第一个元素(即根结点) 
输入变量: const char a[], 后序序列字符串 
           const char b[], 中序序列字符串    
           char c[], 待求的前序序列字符串      
输出变量:char c[], 前序序列字符串
返回值: 无
*/
void Drive(const char a[], const char b[], char c[])
{
    int lenA = strlen(a);
    int lenB = strlen(b);
    int lenC = 0;
    int pos = TheLast(a, b, lenA, 0, lenB-1);//寻找当前子树的根结点在字符串b中的位置 
    int top = 0;
    
    if (pos != -1)
    {
        c[lenC++] = b[pos]; //结点的数据,即字符串的内容  
        if (pos > 0)//递归处理左子树 
            lenC = Print(a, b, c, lenA, lenC, 0, pos-1);
        if (pos < lenB-1)//递归处理子右树 
            lenC = Print(a, b, c, lenA, lenC, pos+1, lenB-1);
    }
    
    c[lenC] = '\0';//设置结尾符 
}
/*
函数功能:寻找当前子树的根结点在字符串b中的位置  
输入变量: const char a[], 后序序列字符串 
           const char b[], 中序序列字符串    
           int lenA, 字符串a的长度  
           int left,  当前子树在字符串b中所对应的子串的左边界
           int right, 当前子树在字符串b中所对应的子串的右边界
输出变量: 无
返回值:int, 当前子树的根结点在字符串b中的位置(下标) 
*/
int TheLast(const char a[], const char b[], int lenA, int left, int right)
{
    int i, j;
    
    for (i=lenA-1; i>=0; i--)//逆序遍历后序序列字符串以寻找根结点 
    {
        for (j=left; j<=right; j++)//判断结点a[i]是否是当前子树的根结点 
        {
            if (b[j] == a[i]) 
                return j;
        }
    }
    return -1;//未找到根结点,返回-1 
}

/*
函数功能:递归求前序序列,存储每个结点的数据
输入变量: const char a[], 后序序列字符串 
           const char b[], 中序序列字符串
           char c[], 待求的前序序列字符串    
           int lenA, 字符串a的长度  
           int lenC, 二维数组c的长度  
           int left,  当前子树在字符串b中所对应的子串的左边界
           int right, 当前子树在字符串b中所对应的子串的右边界
输出变量:无
返回值: int, 二维数组c的长度
*/
int Print(const char a[], const char b[], char c[], int lenA, int lenC, int left, int right)
{
    int pos = TheLast(a, b, lenA, left, right);//寻找当前子树的根结点在字符串b中的位置 
    
    if (pos != -1)
    {
        c[lenC++] = b[pos];
        if (pos > left)//递归处理左子树 
            lenC = Print(a, b, c, lenA, lenC, left, pos-1);
        if (pos < right)//递归处理子右树 
            lenC = Print(a, b, c, lenA, lenC, pos+1, right);
    }
    return lenC;
}

板凳

再给一个层序遍历的.
算法分析:主要是以根结点为中心点,使用递归方式求解左右子树。但是单纯的递归得到的解是先处理完左子树后,再处理右子树的,而我们现在要求层序遍历,所以要记录结点所在的层数.

#include<stdio.h>
#define MAX 1000

void Drive(const char a[], const char b[], char c[]);
int TheLast(const char a[], const char b[], int lenA, int left, int right);
int Print(const char a[], const char b[], int c[][2], int lenA, int lenC, int top, int left, int right);
void Transform(int a[][2], char b[], int len);

int main()
{
    char a[] = "hidjkeblfmngca"; //后序序列 
    char b[] = "hdibjekalfcmgn"; //中序序列 
    char c[MAX];  //前序序列  
    
    Drive(a, b, c);//主要操作过程 
    
    puts(a);
    puts(b);
    puts(c);
    
    getchar();
    return 0;
}

/*
函数功能:递归求前序序列的驱动程序,同时给出第一个元素(即根结点) 
输入变量: const char a[], 后序序列字符串 
           const char b[], 中序序列字符串    
           char c[], 待求的前序序列字符串      
输出变量:char c[], 前序序列字符串
返回值: 无
*/
void Drive(const char a[], const char b[], char c[])
{
    int cc[MAX][2];//使用一个二维数组来存储结点的数据和所在层数 
    int lenA = strlen(a);
    int lenB = strlen(b);
    int lenC = 0;
    int pos = TheLast(a, b, lenA, 0, lenB-1);//寻找当前子树的根结点在字符串b中的位置 
    int top = 0;
    
    if (pos != -1)
    {
        cc[lenC][0] = top;   //结点所在层数,根结点在第0层 
        cc[lenC++][1] = b[pos]; //结点的数据,即字符串的内容  
        if (pos > 0)//递归处理左子树 
            lenC = Print(a, b, cc, lenA, lenC, top+1, 0, pos-1);
        if (pos < lenB-1)//递归处理子右树 
            lenC = Print(a, b, cc, lenA, lenC, top+1, pos+1, lenB-1);
    }
    
    Transform(cc, c, lenC);//把二维数组中存储的信息转换到字符串c 
}

/*
函数功能:把二维数组中存储的信息转换成字符串的形式,要求以层为顺序进行存储 
输入变量: int a[][2], 用来存储结点的数据和所在层数的二维数组
           char c[], 待求的前序序列字符串      
输出变量:char c[], 前序序列字符串
返回值: 无
*/
void Transform(int a[][2], char c[], int len)
{
    int i, j;
    int top = 0;
    
    c[top++] = a[0][1];
    for (i=1; i<len; i++)//以层为顺序遍历二维数组,i表示结点所在层数 
    {
        for (j=1; j<len; j++)//如果是在同一层,则按顺序存储 
        {
            if (a[j][0] == i)
            {
                c[top++] = a[j][1];
            }
        }
    }
    
    c[top] = '\0';//设置结尾符 
}

/*
函数功能:寻找当前子树的根结点在字符串b中的位置  
输入变量: const char a[], 后序序列字符串 
           const char b[], 中序序列字符串    
           int lenA, 字符串a的长度  
           int left,  当前子树在字符串b中所对应的子串的左边界
           int right, 当前子树在字符串b中所对应的子串的右边界
输出变量: 无
返回值:int, 当前子树的根结点在字符串b中的位置(下标) 
*/
int TheLast(const char a[], const char b[], int lenA, int left, int right)
{
    int i, j;
    
    for (i=lenA-1; i>=0; i--)//逆序遍历后序序列字符串以寻找根结点 
    {
        for (j=left; j<=right; j++)//判断结点a[i]是否是当前子树的根结点 
        {
            if (b[j] == a[i]) 
                return j;
        }
    }
    return -1;//未找到根结点,返回-1 
}

/*
函数功能:递归求前序序列,存储每个结点的数据和所在层数  
输入变量: const char a[], 后序序列字符串 
           const char b[], 中序序列字符串    
           int c[][2], 用来存储结点的数据和所在层数的二维数组
           int lenA, 字符串a的长度  
           int lenC, 二维数组c的长度  
           int top, 结点所在层数
           int left,  当前子树在字符串b中所对应的子串的左边界
           int right, 当前子树在字符串b中所对应的子串的右边界
输出变量:无
返回值: int, 二维数组c的长度
*/
int Print(const char a[], const char b[], int c[][2], int lenA, int lenC, int top, int left, int right)
{
    int pos = TheLast(a, b, lenA, left, right);//寻找当前子树的根结点在字符串b中的位置 
    
    if (pos != -1)
    {
        c[lenC][0] = top;   //存储当前子树根结点的信息 
        c[lenC++][1] = b[pos];
        if (pos > left)//递归处理左子树 
            lenC = Print(a, b, c, lenA, lenC, top+1, left, pos-1);
        if (pos < right)//递归处理子右树 
            lenC = Print(a, b, c, lenA, lenC, top+1, pos+1, right);
    }
    return lenC;
}

3 楼


楼上的不错

我来回复

您尚未登录,请登录后再回复。点此登录或注册