Programacion

1

Programación 4, Guía 8 Facultad: Ingeniería Escuela: Computación Asignatura: Programación 4

Tema: ARBOLES CON C#
Objetivo Especifico
• •

Conocer la definición de Arboles A partir de una clase agregar sintaxis necesaria para construir un árbol

Introduccion Teorica
A. Definición Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del árbol puedetener 0, 1, ó 2 sub árboles llamados de acuerdo a su caso como: 1. Si el nodo raíz tiene 0 relaciones se llama hoja. 2. Si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbol izquierdo. 3. Si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho.

Figura 1: Un árbol binario sencillo de tamaño 9 y altura3,con un nodo raíz cuyo valor es 2

Programación 4, Guía 8

2

Figura 2: Árbol binario esencialmente completo
B. Existen cuatro tipos de árbol binario: 1. A. B. Distinto. 2. A. B. Similares. 3. A. B. Equivalentes. 4. A. B. Completos. A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos. A. B. DISTINTO Se dice que dosárboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:
A A

B

B

A. B. SIMILARES Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Ejemplo:
A A

B

D

A. B. EQUIVALENTES Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:
A AB

B

3

Programación 4, Guía 8

A. B. COMPLETOS Son aquellos arboles en los que todos sus nodos excepto los del último nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho. Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntaral subárbol izquierdo y derecho del subárbol en cuestión. Cada nodo se representa gráficamente de la siguiente manera: Izquierdo Centro Derecho

Programación 4, Guía 8

4

Material y Equipo
• •

Guía de laboratorio No. 8 Visual Studio 2005

Procedimiento
Ejemplo: Árbol binario de búsqueda
using System; using System.Collections.Generic; using System.Text; namespace arboles{ publicclass NodoT{ public NodoT NodoIzquierdo; public int Informacion; public NodoT NodoDerecho; //Constructor public NodoT(){ this.NodoIzquierdo = null; this.Informacion = 0; this.NodoDerecho = null; } } class Program{ static void Main(string[] args){ int Opcion = 0; NodoT Raiz = null; int Dato; do{ Opcion = Menu(); switch (Opcion){ case 1: Console.Write("Valor del Nuevo Nodo: "); Dato =int.Parse(Console.ReadLine()); if (Raiz == null){ NodoT NuevoNodo = new NodoT(); NuevoNodo.Informacion = Dato; Raiz = NuevoNodo; } else{ Insertar(Raiz, Dato); } Console.Clear(); break; case 2: Recorrer(Raiz); Console.WriteLine("Fin del Recorrido,..."); Console.ReadLine(); Console.Clear(); break; case 3: Console.Write("Teclee el Dato a Buscar: "); Dato = int.Parse(Console.ReadLine()); if (Raiz != null){BuscarNodo(Raiz, Dato); } else{ Console.WriteLine("ERROR, Arbol Vacio...."); } Console.Clear(); break; case 4: Console.Write("Teclee el Dato a Eliminar: ");

5

Programación 4, Guía 8
Dato = int.Parse(Console.ReadLine()); if (Raiz != null){ EliminarNodo(ref Raiz, Dato); } else{ Console.WriteLine("ERROR, Arbol Vacio...."); } Console.Clear(); break; case 5: Finalizar(); break; default:Console.WriteLine("ERROR, Opcion Invalida...."); Console.ReadLine(); Console.WriteLine(""); break; } } while (Opcion != 5); } static int Menu(){ int Resultado = 0; Console.WriteLine("MENU DE ARBOLES"); Console.WriteLine(""); Console.WriteLine("1.- Registrar un Nuevo Nodo"); Console.WriteLine("2.- Mostrar/Recorrer el Arbol"); Console.WriteLine("3.- Buscar un Nodo"); Console.WriteLine("4.- Eliminar un Nodo");...