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

[David Méndez]

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?

thanks
--
comp.lang.c.moderated - moderation address: cl**@plethora.net

[hari4063]

Is any chance that this list are _named_ in some another names. If not, can
you explain what is inorder/preorder list are? (I know that you expect
answer, but i post question !:)

Thanks,
Zaharije Pasalic

[Jason Whitehurst]

David Méndez wrote:

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?

do your own homework.

--
Jason Whitehurst
--
comp.lang.c.moderated - moderation address: cl**@plethora.net

[Dave Vandervies]

In article <cl****************@plethora.net>,
David Méndez <da**********@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 dj******@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: cl**@plethora.net

[Per Vognsen]

"David Méndez" <da**********@hotmail.com> wrote in message news:<cl****************@plethora.net>...

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?

thanks

Hint: The first element of the pre-order traversal list will be the root of
the tree. This same element will also be present somewhere in the
in-order traversal list. What can you say about the part of the
in-order list to the left of this element? What about the part to the
right?

Per
--
comp.lang.c.moderated - moderation address: cl**@plethora.net

[David Méndez]

inorder/preorder list's: 2 List Data Structures where the nodes are
connected with a Binary Tree values in inorder and preorder respectively.

thank you.

"hari4063" <za**************@pmf.unsa.ba> escribió en el mensaje
news:76******************************@localhost.ta lkaboutprogramming.com...

Is any chance that this list are _named_ in some another names. If not, can you explain what is inorder/preorder list are? (I know that you expect
answer, but i post question !:)

Thanks,
Zaharije Pasalic

---
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

[David Méndez]

Thank you!!

C is ok.

David.

"Dave Vandervies" <dj******@csclub.uwaterloo.ca> escribió en el mensaje
news:cl****************@plethora.net...

In article <cl****************@plethora.net>,
David Méndez <da**********@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 dj******@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: cl**@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: cl**@plethora.net

[David Méndez]

well, I was expecting something like:

typedef struct tree{
int v;
struct tree *left, *right;
}BTREE, *BTREEPTR;

typedef struct list{
int v;
struct list *next
}TLIST, *TLISTPTR;

BTREE *reconstruct_tree(TLIST *p, TLIST *i)
{
...
}

I TAKE THE TIME TO IDENT THE CODE THAT YOU SEND ME, What you mean when you
use as parameters another 2 BTREE's ?:

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 NULL;

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 NULL;
}
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;
}

"Dave Vandervies" <dj******@csclub.uwaterloo.ca> escribió en el mensaje
news:cl****************@plethora.net...

In article <cl****************@plethora.net>,
David Méndez <da**********@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 dj******@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: cl**@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: cl**@plethora.net

[Karl Heinz Buchegger]

"David Méndez" wrote:

I TAKE THE TIME TO IDENT THE CODE THAT YOU SEND ME, What you mean when you
use as parameters another 2 BTREE's ?:

Did you recognize that the code posted was a joke?
It was something that worked (actually I assume this, I
never tried the code), but was intentionally obfuscated
such that you cannot hand it in directly. It is a way
of saying: Do your own homework.
--
Karl Heinz Buchegger
kb******@gascad.at

[Dave Vandervies]

In article <41***************@gascad.at>,
Karl Heinz Buchegger <kb******@gascad.at> wrote:

"David Méndez" wrote:

I TAKE THE TIME TO IDENT THE CODE THAT YOU SEND ME, What you mean when you
use as parameters another 2 BTREE's ?:
Did you recognize that the code posted was a joke?
It was something that worked (actually I assume this, I
never tried the code),

Well, there's two problems with it, actually.

The first problem is the deliberately-introduced single-character error I
mentioned; I figured that untangling the code enough to identify and fix
that should provide more enlightenment than coming up with the expected
solution to the exercise.

The second problem is actually an error in the algorithm that I missed
in my desk-check. (I didn't actually run the code, but did spend quite
a bit of time desk-checking it to make sure it correctly implemented the
algorithm; unfortunately I didn't notice the flaw in the algorithm until
after I had posted it.) The code that should remove the rightmost leaf
node from the preorder list in the case where that node is on the left
of its parent actually removes the parent, not the leaf. (I expect
that this will cause the code to break in obvious ways at runtime and
not just silently give the wrong answer.)

Your assignment, should you choose to accept it:
1. Identify the code with the logic error and replace it with correct
code.
2. Explain why the correct code is simpler than the incorrect code
it replaced.
3. Explain the algorithm used, and compare it with the "obvious"
top-down algorithm.

but was intentionally obfuscated
such that you cannot hand it in directly. It is a way
of saying: Do your own homework.

Yep, pretty much.
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
I grant, of course, that our tasks would be much simpler if we could
order up a stock of ideal components.
--William Meyer in comp.lang.c

[Dave Vandervies]

In article <cl****************@plethora.net>,
David Méndez <da**********@hotmail.com> wrote:

well, I was expecting something like:

typedef struct tree{
int v;
struct tree *left, *right;
}BTREE, *BTREEPTR;

typedef struct list{
int v;
struct list *next
}TLIST, *TLISTPTR;

BTREE *reconstruct_tree(TLIST *p, TLIST *i)
{
...
}

I TAKE THE TIME TO IDENT THE CODE THAT YOU SEND ME, What you mean when you
use as parameters another 2 BTREE's ?:
Read the code more carefully.
Note that where the pointers are pointing is more important than what
they're called in determining what data structure they represent.
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca No, I did not look that up.

You should get out more, then.
--Garrett Wollman and Richard P. Grant in the scary devil monastery
--
comp.lang.c.moderated - moderation address: cl**@plethora.net