Balance de un arbol binario ordenado

[nico56]

Hola que tal, este es mi primer mensaje en este foro, ya vengo de varios foros donde se creen que saben algo de computacion y no saben nada pero de este me preguntaron si lo habia visitado y heme aqui vamos a ver que tal  , el asunto es el siguiente, tengo el siguiente algoritmo pero no se como pasarlo a un pseudocodigo, queria ver si me podian dar una mano, el algotimo consiste en:

1.- Leer el arbol "inorder" y almacenar sus elmentos en una estructura secuencial (array o lista).

2.- Destruir el arbol mediante una poda "posorder".

3.- Reconstruir el arbol tomando el conjunto almacenado en el paso (1) utilizando el procedimiento "insertarOrdenado", haciendolo mediante particiones medias recursivas.

Tengo basicamente problemas con el paso (1) y (3). Para la poda del arbol ya he hecho una funcion que se le pasa como argumento un puntero al nodo raiz de ese arbol.

Desde ya gracias y saludos.

[AlbertoBSD]

Puedes guadar el arbol con alguna funcion recursiva bastara, todo esto en un ArrayList, no se en que lenguaje estes trabajando, sinceramente recomiendo java ya que tiene muchas funciones ya diseñanas como el ArrayList.


Saludos

[nico56]

No estoy trabajando en ningún lenguaje especifico, justamente como dice el primer mensaje debo hacer un "psedocodigo". Tampoco se como volcar el árbol en un "array list" con una función recursiva, si no no hubiera creado este tema .

[nico56]

 

[nico56]

y al final que tanta fama le hacen a este foro...

[-Ramc-]

y al final que tanta fama le hacen a este foro...

vaya, mira que nadie te va a hacer la tarea y menos si vienes de ofensivo, si no sabes como recorrer un arbol en inorder y tampoco estás aprendiendo modales te están robando la plata así que mira a ver que haces.

Código (java) [Seleccionar] Expandir


ArrayList tour;
private void inOrder(TreeNode node) {
if(node == root) {
tour = new ArrayList();
}
if(node != null) {
inOrder(node.getLeft());
tour.add(node.getValue());
inOrder(node.getRight());
}
}

Con eso  lo recorres en inorder, el algoritmo está en java, pero, debo suponer que ya tienes toda la lista enlazada hecha lo que equivale a ArrayList e igualmente el arbol con lo que le envias al método la raíz del árbol.

Para el punto 3, se supone que según lo que dice ahí ya tienes la función insertar ordenado, con lo que sería tomar cada valor de la lista enlazada e insertarlo, no importa el orden ya que según el nombre de la función sugiere que ordena.

No indicas que tipo de arbol es así que puse el algoritmo sobre un árbol binario que fue el que encontré ahora en mi PC.

No especificas mucho en tu post, ni siquiera colocas qué códigos tienes, como para que andes de arrogante.

[nico56]

Gracias, pero mira vamos a la primera parte del algoritmo, no es que no se hacer la lectura inorder, basicamente lo que no entiendo de tu codigo es esto.

Código [Seleccionar] Expandir

if(node == root) {
tour = new ArrayList();
}

[-Ramc-]

Gracias, pero mira vamos a la primera parte del algoritmo, no es que no se hacer la lectura inorder, basicamente lo que no entiendo de tu codigo es esto.

Código [Seleccionar] Expandir

if(node == root) {
tour = new ArrayList();
}

Si el nodo que recibe la función es igual a la raiz del árbol, entonces quiere decir que el recorrido es nuevo, porque la raíz es el primer nodo así que la lista enlazada se inicializa, sino se verifica que no sea nulo y se hacen las llamadas recursivas ya que en inorder se lee, primero el nodo hijo izquierdo, después el padre y después el hijo derecho.