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

D

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
 
H

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
 
J

Jason Whitehurst

David said:
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.
 
D

Dave Vandervies

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

Per Vognsen

David Méndez said:
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
 
D

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

David Méndez

Thank you!!

C is ok.

David.

Dave Vandervies said:
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 (e-mail address removed)
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
 
D

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 said:
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 (e-mail address removed)
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
 
K

Karl Heinz Buchegger

David Méndez said:
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.
 
D

Dave Vandervies

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
 
D

Dave Vandervies

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 (e-mail address removed)
No, I did not look that up.
You should get out more, then.
--Garrett Wollman and Richard P. Grant in the scary devil monastery
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,905
Latest member
Kristy_Poole

Latest Threads

Top