pixie
21 de Enero del 2010

Tengo que crear un método que reestructure un árbol de búsqueda binario para que cada nodo cumpla la propiedad "el número de nodos en su sub-árbol izquierdo, menos el número de nodo en su sub-árbol derecho es cero o uno". Tengo un pseudocódigo que lo implementa pero es que no lo entiendo muy bien... Os lo dejo de todas formas.

<N1,..., Nk> es la lista de nodos en el orden inorder.

reestructurar(<N, ..., Nk>)

1. if k<1 return NULL
2. i = (k div 2) + 1
3. T = new Tree
4. T->info = Ni
5. T->izq = reestructurar(<N1, ..., Ni-1>)
6. T->der = reestructurar(<Ni+1, ..., Nk>)
7. return T

¿Alguien puede ayudarme? Porque me estoy volviendo loco intentando hacerlo y no hay forma.

yomismo
21 de Enero del 2010

jajajaja, lp2?? estoy igual, yo creo que ese algoritmo esta mal, porq la k nunca va a ser menor que 1 cuando se reestructure el derecho, debe de haber otra condicion de parada. Si consigo hacerlo lo pongo aqui, haz lo mismo tu, jeje