一个算法的问题:输入二叉树的前序遍历和中序遍历序列,怎样能生成此二叉树?
我想了一个算法都非常复杂.
希望您最好用pascal或者c语言给出一个简单经济的算法.
多谢赐教,承蒙关照!
我想了一个算法都非常复杂.
希望您最好用pascal或者c语言给出一个简单经济的算法.
多谢赐教,承蒙关照!
解决方案 »
- 完成端口关于资源同步的问题
- 想学习MFC的web控件编程,有什么好的书或资料推荐吗?
- 请问如何生成动画(视频)?
- 如何判断当前的线程或进程,对某个目录下面是否有读,写,创建文件的权限?
- 怎样移动2张图片 一个水平移动 一个垂直移动
- 我正在做一个多线程下载工具,想做多个进度条以显示每个线程的下载进度,大家能给些提示吗?谢谢^-^
- 为什么#include <iostream.h>在vc6.0 Console项目中可以找到,在VC.NET2003 Console中找不到
- 请问怎么设全局变量?
- 我像学习VC,大家说要学习C++,下面的书哪本适合初学啊?
- 不明白。。。
- 有关串口的问题
- 请问宏 AC_SRC_ALPHA 的值是多少?
依次从前序遍历序列中取结点,每取出一个结点就与中序遍历序列中的各结点进行比较,当相等时,中序遍历序列便被分成以该结点为根结点的两棵子树,左部分为左子树,右部分为右子树。直至取完前序遍历序列中所有所有的结点,则该树构造完毕。
设树组A存放前序序列,B为中序序列。
算法描述如下:
TYPE node=RECORD
lchild,rchild:integer;
ch:char
END;
PROCEDURE ds(A:ARRAY[1..N] OF char;
B:ARRAY[1..N] OF node);
VAR s:stack;
top:integer;
i,j,t:integer;
BEGIN
top:=0;
FOR i:+1 TO n DO
BEGIN
j:=1;
WHILE B[i].ch<>A[i] DO
j:=j+1;
IF top=0
THEN BEGIN
top:=top+1;
s[top]:=j
END
ELSE IF j<s[top]
THEN BEGIN
B[s[top]].lchild:=j;
top:=top+1;
s[top]:=j
END
ELSE BEGIN
WHILE (j>s[top]) AND (top<>0) DO
BEGIN t:=s[top];
top:=top-1
END;
B[t].rchild:=j;
top:=top+1;
s[top]:=j
END
END
END;可直接运行ANSI C
#include "stdio.h" struct node
{
char ch;
int lchild,rchild;
};
void tree(char a[10],struct node b[11])
{
int s[10],top,i,j,t;
top=-1;//stack empty
for (i=0;i<10;i++)
{
j=0;
while (b[j].ch!=a[i])
j=j+1;
if (top==-1)
{
top=top+1;
s[top]=j;
}
else if (j<s[top])
{
b[s[top]].lchild=j;
top=top+1;
s[top]=j;
}
else
{
while (j>s[top]&&top!=-1)
{
t=s[top];
top=top-1;
}
b[t].rchild=j;
top=top+1;
s[top]=j;
}
}
for (i=0;i<10;i++)
{
printf("%c leftchild-> %c rightchild-> %c\n",b[i].ch,b[b[i].lchild].ch,b[b[i].rchild].ch);
//if (b[e].lchild!=-1)
//printf("%d ",b[b[e].rchild],ch);
//if (
//printf("/n"); }
getchar();
}
void main()
{
struct node b[11]={{'c',10,10},{'b',10,10},{'e',10,10},{'d',10,10},{'a',10,10},{'h',10,10},{'g',10,10},{'i',10,10},{'j',10,10},{'f',10,10},{'^',0,0}};
char a[10]="abcdefghij";//测试用例子
tree(a,b);
}