lunes, 12 de noviembre de 2012

Ejemplo de Arbol Binario de Busqueda en C#

Descargar Solución de la galería de códigos de msdn aquí

Este es un ejemplo de una arbol binario de busqueda en C#.

Un árbol binario de búsqueda también llamados BST (acrónimo del inglés Binary Search Tree) es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.


using System; 
using System.Collections.Generic; 
using System.Text; 
using System.Collections; 
 
namespace Arboles 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            MyArbol<int> a = new MyArbol<int>(4, new MyArbol<int> 
                      (10, new MyArbol<int>(15, 
                       new MyArbol<int>(35)), 
                       new MyArbol<int>(5), 
                       new MyArbol<int>(25)), 
                       new MyArbol<int>(20), 
                       new MyArbol<int>(30, 
                       new MyArbol<int>(40), 
                       new MyArbol<int>(50))); 
            Console.WriteLine("Altura del arbol {0}\n", a.Altura()); 
            Console.WriteLine("Total de Hijos {0}\n", a.TotalHijos); 
            a.ListarArbol(); 
            Console.WriteLine("\nPreOrder usando List"); 
            foreach (int k in a.PreOrderUsandoList()) 
                Console.Write("{0}  ", k); 
            Console.WriteLine(); 
            Console.WriteLine("\nPreOrder"); 
            foreach (int k in a.PreOrder()) 
                Console.Write("{0}  ", k); 
            Console.WriteLine(); 
            Console.WriteLine("\nPostOrder usando List"); 
            foreach (int k in a.PostOrderUsandoList()) 
                Console.Write("{0}  ", k); 
            Console.WriteLine(); 
            Console.WriteLine("\nPostOrder"); 
            foreach (int k in a.PostOrder()) 
                Console.Write("{0}  ", k); 
            Console.WriteLine(); 
            Console.WriteLine("\nAloAncho"); 
            foreach (int k in a.AloAncho()) 
                Console.Write("{0}  ", k); 
            Console.WriteLine(); 
        } 
    } 
 
    class MyArbol<R> 
    { 
        List<MyArbol<R>> hijos; 
        R padre; 
        public MyArbol(R padre, params MyArbol<R>[] hijos) 
        { 
            this.padre = padre; 
            this.hijos = new List<MyArbol<R>>(); 
            if (hijos != null) 
                foreach (MyArbol<R> arbol in hijos) 
                    this.hijos.Add(arbol); 
        } 
        public int TotalHijos 
        { 
            get 
            { 
                if (hijos == null) return 0; 
                else return hijos.Count; 
            } 
        } 
        public MyArbol<R> this[int k] 
        { 
            get 
            { 
                if (k >= 0 && k < TotalHijos) return hijos[k]; 
                else throw new IndexOutOfRangeException("Hijo inexistente"); 
            } 
            set 
            { 
                if (k >= 0 && k < TotalHijos) hijos[k] = value; 
                else throw new IndexOutOfRangeException("Hijo inexistente"); 
            } 
        } 
        public int Altura() 
        { 
            if (TotalHijos == 0) return 0; 
            else 
            { 
                int max = 0; 
                foreach (MyArbol<R> arbol in hijos) 
                { 
                    int altura = arbol.Altura(); 
                    if (altura > max) max = altura; 
                } 
                return max + 1; 
            } 
        } 
        public R Padre 
        { 
            get { return padre; } 
        } 
        public void ListarArbol() 
        { 
            ListarArbol(this, 0); 
        } 
        public void ListarArbol(MyArbol<R> arbol, int nivel) 
        { 
            for (int i = 0; i < nivel; i++) 
                Console.Write(" "); 
            Console.WriteLine(arbol.padre); 
            foreach (MyArbol<R> a in arbol.hijos) 
                ListarArbol(a, nivel + 4); 
        } 
        public IEnumerable<R> PreOrderUsandoList() 
        { 
            List<R> preorder = new List<R>(); 
            preorder.Add(padre); 
            foreach (MyArbol<R> a in hijos) 
                foreach (R x in a.PreOrderUsandoList()) 
                    preorder.Add(x); 
            return preorder; 
        } 
        public IEnumerable<R> PreOrder() 
        { 
            yield return padre; 
            foreach (MyArbol<R> a in hijos) 
                foreach (R x in a.PreOrderUsandoList()) 
                    yield return x; 
        } 
        public IEnumerable<R> PostOrderUsandoList() 
        { 
            List<R> postorder = new List<R>();             
            foreach (MyArbol<R> a in hijos) 
                foreach (R x in a.PostOrderUsandoList()) 
                    postorder.Add(x); 
            postorder.Add(padre); 
            return postorder; 
        } 
        public IEnumerable<R> PostOrder() 
        { 
            foreach (MyArbol<R> a in hijos) 
                foreach (R x in a.PostOrderUsandoList()) 
                    yield return x; 
            yield return padre; 
        } 
        public IEnumerable<R> AloAncho() 
        { 
            Queue<MyArbol<R>> cola = new Queue<MyArbol<R>>(); 
            cola.Enqueue(this); 
            while (cola != null) 
            { 
                MyArbol<R> arbol = cola.Dequeue(); 
                foreach (MyArbol<R> a in arbol.hijos) 
                    cola.Enqueue(a); 
                yield return arbol.padre; 
            } 
        } 
    } 
}

Descargar Solución de la galería de códigos de msdn aquí