Reestructurar un árbol de búsquede binario
Publicado por pixie (1 intervención) el 17/01/2010 12:48:07
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.
<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.
Valora esta pregunta
0