[SOLUCIONADO] C# Implementación en C# de un árbol binario ordenado

Noporfavor · Septiembre 13, 2016, 06:42:08 AM

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:

Código: php


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:

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

seth · Septiembre 13, 2016, 10:28:27 PM

El arbol seria asi?

Código: php



     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

[SOLUCIONADO] C# Implementación en C# de un árbol binario ordenado

Noporfavor

Septiembre 13, 2016, 06:42:08 AM Ultima modificación: Septiembre 19, 2016, 05:50:19 PM por rollth

seth

Septiembre 13, 2016, 10:28:27 PM #1