Re: Giving the preorder & inorder lists, How can be constructed the corresponding B-TREE ?

From: Dave Vandervies (dj3vande_at_csclub.uwaterloo.ca)
Date: 11/08/04 

Date: 08 Nov 2004 01:59:36 GMT

In article <clcm-20041104-0008@plethora.net>,
David Méndez <davigre_spam@hotmail.com> wrote:
>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) 

-- 
Dave Vandervies                               dj3vande@csclub.uwaterloo.ca
There once was a troller named Cass,   Who lived in a house made of glass.
  Every stone that he threw     Showed how little he knew.
(Now what rhymes with "glass" and with "Cass?")    --Keith Thompson in CLC
-- 
comp.lang.c.moderated - moderation address: clcm@plethora.net

Relevant Pages