CON 2 LISTAS QUE CONTIENEN EL PREORDEN Y EL INORDEN DE UN ARBOL BINARIO COMO OBTENGO EL ARBOL?

[David Méndez]

Teniendo 2 listas con el Preorden y el Inorden de un arbol Binario como
puedo armar el arbol binario?

ArbBin *ArbolPreIn(Lista *p, Lista *i)
{
...
}

Muchas gracias por cualquier ayuda.

David.



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

[Ernesto Perez]

David Méndez wrote:
| Teniendo 2 listas con el Preorden y el Inorden de un arbol Binario como
| puedo armar el arbol binario?
|
| ArbBin *ArbolPreIn(Lista *p, Lista *i)
| {
|
| }
|
| Muchas gracias por cualquier ayuda.
|
| David.
|
|
|
| ---
| 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
|
|
//indica si son está a la derecha(>0) o a la izquierda(<0) del parent
int leftOrRight(Lista *i,int parent,int son){
int pp=0,ps=0,j=0;
Lista::Iterador itor;
for(itor=i->inicio,j=0;itor!=i->fin;itor.next(),j++){
if(itor->dato==parent)
pp=j;
else
if(itor->dato==son)
ps=j;
}
return ps-pp;
}
//la lista preorden nos da la secuencia de insercion
//la lista inorden indica si el nodo que se va a insertar está a la
//derecha o a la izquierda de su padre
Nodo *preIn(Lista *p,Lista *i){
int lr,pv;
Lista::Iterador itor=p->inicio;
//root ya sabes donde apunta,parent apunta al padre del nodo
Nodo *root=new Nodo(itor->dato),*parent;
Nodo *nodo=null; //funciona como un indicador, para seguir
//el camino hasta donde debe ir el nodo
itor.next;
for(;itor!=p->fin;itor.next()){
parent=root;
pv=root->dato;
nodo=root;
while(nodo!=null){

if(leftOrRight(i,parent->dato,itor.dato)<0){
parent=nodo;
nodo=nodo->izq;
}else{ parent=nodo;
nodo=nodo->der;
}

}
//ya me canse de escribir, aqui tu te encargas de hacer
//que el padre apunte al hijo, ya tu sabes como ¿no? ;)
}
}

[Tito]

Bueno, aquí tienes una solución en Haskell, un lenguaje funcional.
Se puede convertir a C++ fácilmente, Haskell no es difícil de entender.
Quizás lo haga yo mismo un día de éstos.
Si tienes más problemas de éstos, sigue escribiendo al grupo, son un bonito
pasatiempo.

<code>
partition :: Eq a => a -> [a] -> ([a], [a])
partition x [] = ([], [])
partition x (y:ys) =
if x == y
then ([], ys)
else (y:fst p, snd p)
where p = partition x ys

data Tree a = Nil | Node (Tree a) a (Tree a)

makeTreeRec :: Eq a => [a] -> [a] -> (Tree a, [a])
makeTreeRec [] inorder = (Nil, [])
makeTreeRec preorder [] = (Nil, preorder)
makeTreeRec (root:preorder) inorder =
(Node (fst makeTree1) root (fst makeTree2), snd makeTree2)
where
makeTree1 = makeTreeRec preorder (fst inorderPartition)
makeTree2 = makeTreeRec (snd makeTree1) (snd inorderPartition)
inorderPartition = partition root inorder

makeTree preorder inorder = fst (makeTreeRec preorder inorder)
</code>

Saludos,
Tito

Post by David Méndez
Teniendo 2 listas con el Preorden y el Inorden de un arbol Binario como
puedo armar el arbol binario?
ArbBin *ArbolPreIn(Lista *p, Lista *i)
{
...
}
Muchas gracias por cualquier ayuda.
David.
---
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]

muchas gracias voy a estudiarlo...

Post by Tito
Bueno, aquí tienes una solución en Haskell, un lenguaje funcional.
Se puede convertir a C++ fácilmente, Haskell no es difícil de entender.
Quizás lo haga yo mismo un día de éstos.
Si tienes más problemas de éstos, sigue escribiendo al grupo, son un bonito
pasatiempo.
<code>
partition :: Eq a => a -> [a] -> ([a], [a])
partition x [] = ([], [])
partition x (y:ys) =
if x == y
then ([], ys)
else (y:fst p, snd p)
where p = partition x ys
data Tree a = Nil | Node (Tree a) a (Tree a)
makeTreeRec :: Eq a => [a] -> [a] -> (Tree a, [a])
makeTreeRec [] inorder = (Nil, [])
makeTreeRec preorder [] = (Nil, preorder)
makeTreeRec (root:preorder) inorder =
(Node (fst makeTree1) root (fst makeTree2), snd makeTree2)
where
makeTree1 = makeTreeRec preorder (fst inorderPartition)
makeTree2 = makeTreeRec (snd makeTree1) (snd inorderPartition)
inorderPartition = partition root inorder
makeTree preorder inorder = fst (makeTreeRec preorder inorder)
</code>
Saludos,
Tito

Post by David Méndez
Teniendo 2 listas con el Preorden y el Inorden de un arbol Binario como
puedo armar el arbol binario?
ArbBin *ArbolPreIn(Lista *p, Lista *i)
{
...
}
Muchas gracias por cualquier ayuda.
David.
---
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

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.799 / Virus Database: 543 - Release Date: 2004/11/19