Arbol binario

Programación IV. Guía 6

1

Facultad:
Ingeniería
Escuela:
Computación
Asignatura: Programación IV

Tema: Arboles en C#.
Objetivos Específicos
•

Definir el concepto de la estructura de datos Árbol.

•

Implementar la estructura de datos Árbol en C #.

Materiales y Equipo
• Guía Número 6.
• Computadora con programa Microsoft Visual C#.

Introducción Teórica
Definición deÁrbol Binario.
Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del
árbol puede tener 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 laderecha, el segundo elemento de la relación es el
subárbol derecho.
15

7

5

18

12

10

25

14

23

2

Programación IV. Guía 6

La Figura anterior muestra un árbol binario sencillo de tamaño 9 y altura 4, con un nodo raíz
cuyo valor es 15.
La Figura siguiente muestra un Árbol binario esencialmente completo.

4

Existen cuatro tipos de árbol binario:
1. ArbolesBinarios Distintos.
2. Arboles Binarios Similares.
3. Arboles Binarios Equivalentes.
4. Arboles Binarios 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.

Arboles Binarios Distintos.
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.
Ejemplo:

Programación IV. Guía 63

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

Arboles Binarios Equivalentes.
Son aquellos árboles que son similares y que además los nodos contienen la misma
información.
Ejemplo:

Arboles Binarios Completos.
Son aquellos árboles en los que todos sus nodosexcepto 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 apuntar al subárbol izquierdo y derecho del subárbol en cuestión.
Cada nodo se representa gráficamente de lasiguiente manera:

Procedimiento
Ejemplo 1. Implementaremos un árbol binario de búsqueda en C#:

Programación IV. Guía 6

4

1. Crear un proyecto de tipo Windows Forms Application, se sugiere darle el nombre de “Arbol
Binario”.
2. Agregar una clase al proyecto, se sugiere darle el nombre de “Nodo Arbol”. Esta clase la
utilizaremos para definir el elemento “nodo” del árbol binario.
3. Enesta clase, agregar el siguiente código:
using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
// Librería para dibujar figuras geométricas
using System.Windows.Forms;
using System.Threading;
// Librería para manejo de hilos
namespace Arbol_Binario
{
class Nodo_Arbol
{
public int info;
public Nodo_Arbol Izquierdo;
public Nodo_Arbol Derecho;
publicNodo_Arbol Padre;
public int altura;
public int nivel;
public Rectangle nodo;

// Dato a almacenar en el nodo
// Nodo izquierdo del árbol
// Nodo derecho del árbol
// Nodo raíz del árbol
// Para dibujar el nodo del árbol

private Arbol_Binario arbol;

// declarando un objeto de tipo Árbol Binario

public Nodo_Arbol()
{
}

// Constructor por defecto

public Arbol_Binario Arbol{
get {return arbol;}
set { arbol = value; }
}

// Constructor por defecto para el objeto de tipo Arbol

// Constructor con parámetros
public Nodo_Arbol(int nueva_info, Nodo_Arbol izquierdo, Nodo_Arbol derecho,
Nodo_Arbol padre)
{
info = nueva_info;
Izquierdo = izquierdo;
Derecho = derecho;
Padre = padre;
altura = 0;
}
}
}

Programación IV. Guía 6

5

// Función para...