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

From: David Méndez (davigre_spam_at_hotmail.com)
Date: 11/12/04 

Date: 12 Nov 2004 01:03:57 GMT

Thank you!!

C is ok.

David.

"Dave Vandervies" <dj3vande@csclub.uwaterloo.ca> escribió en el mensaje
news:clcm-20041107-0001@plethora.net...
> 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 

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.782 / Virus Database: 528 - Release Date: 2004-10-22
-- 
comp.lang.c.moderated - moderation address: clcm@plethora.net

Relevant Pages