主题:跪求算法[已知后序和中序序列,如何恢复二叉树]
TonyShaw
[专家分:300] 发布于 2007-09-20 16:25:00
求,如题的算法。基本思想我明白,可就是一写算法就糊涂了。求一个详细的算法,网上很多都是已知先序和中序来恢复二叉树,我想要后序和中序恢复二叉树。谢谢了,给答案狂加分啊,有源代码加分加到你爽,很急
回复列表 (共3个回复)
沙发
goal00001111 [专家分:4030] 发布于 2007-09-21 10:30:00
我没有构造二叉树,而是用字符串的形式存储二叉树的各种序列.程序比较粗糙,仅供参考.
#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;
}
板凳
goal00001111 [专家分:4030] 发布于 2007-09-21 10:52:00
再给一个层序遍历的.
算法分析:主要是以根结点为中心点,使用递归方式求解左右子树。但是单纯的递归得到的解是先处理完左子树后,再处理右子树的,而我们现在要求层序遍历,所以要记录结点所在的层数.
#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;
}
我来回复