Hola a todos,
bueno como siempre antes de la pregunta les mostrare la tarea y el codigo:
Tarea:
Desarrollar una clase para la administración de un árbol binario ordenado.
Codigo:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ArbolBinarioOrdenado1
{
public class ArbolBinarioOrdenado {
class Nodo
{
public int info;
public Nodo izq, der;
}
Nodo raiz;
public ArbolBinarioOrdenado()
{
raiz=null;
}
public void Insertar (int info)
{
Nodo nuevo;
nuevo = new Nodo ();
nuevo.info = info;
nuevo.izq = null;
nuevo.der = null;
if (raiz == null)
raiz = nuevo;
else
{
Nodo anterior = null, reco;
reco = raiz;
while (reco != null)
{
anterior = reco;
if (info < reco.info)
reco = reco.izq;
else
reco = reco.der;
}
if (info < anterior.info)
anterior.izq = nuevo;
else
anterior.der = nuevo;
}
}
private void ImprimirPre (Nodo reco)
{
if (reco != null)
{
Console.Write(reco.info + " ");
ImprimirPre (reco.izq);
ImprimirPre (reco.der);
}
}
public void ImprimirPre ()
{
ImprimirPre (raiz);
Console.WriteLine();
}
private void ImprimirEntre (Nodo reco)
{
if (reco != null)
{
ImprimirEntre (reco.izq);
Console.Write(reco.info + " ");
ImprimirEntre (reco.der);
}
}
public void ImprimirEntre ()
{
ImprimirEntre (raiz);
Console.WriteLine();
}
private void ImprimirPost (Nodo reco)
{
if (reco != null)
{
ImprimirPost (reco.izq);
ImprimirPost (reco.der);
Console.Write(reco.info + " ");
}
}
public void ImprimirPost ()
{
ImprimirPost (raiz);
Console.WriteLine();
}
static void Main(string[] args)
{
ArbolBinarioOrdenado abo = new ArbolBinarioOrdenado ();
abo.Insertar (100);
abo.Insertar (50);
abo.Insertar (25);
abo.Insertar (75);
abo.Insertar (150);
Console.WriteLine ("Impresion preorden: ");
abo.ImprimirPre ();
Console.WriteLine ("Impresion entreorden: ");
abo.ImprimirEntre ();
Console.WriteLine ("Impresion postorden: ");
abo.ImprimirPost ();
Console.ReadKey();
}
}
}
La pregunta es esta:
Si la consola me devuelve esto:
(http://i.imgur.com/CwU9iF1.png)
Entonces no coincide con esta regla:
Árbol binario
Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
Visite la raíz
Atraviese el sub-árbol izquierdo
Atraviese el sub-árbol derecho
Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
Atraviese el sub-árbol izquierdo
Visite la raíz
Atraviese el sub-árbol derecho
Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
Atraviese el sub-árbol izquierdo
Atraviese el sub-árbol derecho
Visite la raíz
En el postorden me devuelve esto:
25 75 50 150 100
Pero primero tengo que atravesar el sub-árbol izquierdo como en el primer paso del entreorden, a saber, 25 50 (los primeros dos nodos)
Gracias y saludos
El arbol seria asi?
100
/ \
50 150
/ \
25 75
Si no me equivoco, los resultados son correctos
Hagamos el post orden:
Entra por el 100
-hay izquierda? entra por la izquierda, 50
- -hay izquierda? entra por la izquierda, 25
- -no hay izquierda, no hay derecha, imprime 25
-vuelve al 50
- -hay derecha? entra por la derecha, 75
- -no hay izquierda, no hay derecha, imprime 75
-vuelve al 50, como ya entro por los dos lados, imprime 50
vuelve al 100
-hay derecha? entra por la derecha, 150
-no hay izquierda, no hay derecha, imprime 150
vuelve al 100, como ya entro por los dos lados, imprime 100
Tene en cuenta que al ser un algoritmo recursivo, cada subarbol es un arbol en si mismo. Si vos agarras el arbol arrancando del 50 y te olvidas de todo lo que tiene arriba, el 50 pasa a ser la raiz. Cuando el algoritmo dice imprimir la raiz, no es imprimir 100, si no el nodo del que salen los hijos, que en el scope en el que estas se ve como si fuera la raiz