Hi,
If I have the preorder and inorder list, which algorithm does I need to
build the corresponding B-TREE? where can I find some source code?
Here 'tis:
--------
#include <stdio.h>
#include <stdlib.h>
typedef struct n{struct n*p1,*p2;int v;}n;
n*reconstruct_tree(n*p,n*i)
{
n*in2,*t1,*t2;int v;if(!i)return i;
while(p->p2)p=p->p2;in2=i;
do{
t1=malloc(sizeof*t1);t2=malloc(sizeof*t2);
if(!t1||!t2)return 0;
t1->v=t2->v=in2->v;t2->p1=t2->p2=0;t1->p1=in2;t1->p2=t2;
if(t1->p1->p2)t1->p1->p2->p1=t1;if(t1->p1->p1)t1->p1->p1->p1->p2=t1;
in2=t1->p1->p2;
}while(in2);
i=t1;
while(i->p1->p1){
in2=i;v=in2->v;
while(p->v!=v&&p->p1->v!=v){
in2=in2->p1->p1;
if(!in2){puts("invalid input\n");return 0;}
v=in2->v;
}if(v==p->v){
if(p->p1){p=p->p1;free(p->p2);p->p2=0;}
if(in2->p1->p1)in2->p1->p1->p1->p2=in2->p1->p2;
if(in2->p1->p2)in2->p1->p2->p1->p1=in2->p1->p1;
else(i=in2);
t1=in2->p2;t2=in2->p1->p1;free(in2->p1);free(in2);
t2->p2->p2=t1;
}else{
t2=p->p1;
if(t2->p1)t2->p1->p2=t2->p2;t2->p2->p1=t1->p1;
free(t2);in2=in2->p1->p1;
if(in2->p1->p1)in2->p1->p1->p1->p2=in2->p1->p2;
in2->p1->p1->p1->p1=in2->p1->p1;
t1=in2->p2;t2=in2->p1->p2;free(in2->p1);free(in2);
t2->p2->p1=t1;}}
free(p);t1=i->p2;free(i->p1);free(i);
return t1;
}
--------
Be aware that I've deliberately introduced a single-character error.
Make sure you find and fix it before you hand it in.
If it's supposed to be C++ (I see you've crossposted there), there will
be more errors, but they should be easier to fix.
dave
(identify root, extract subtree traversals, recurse)