5.2.1 Creacion Arboles Binarios

Creación.

Una de las operaciones básicas de un árbol binario es la creación del mismo en memoria. Un algoritmo muy simple para formar un árbol, por medio de la creación dinámica de nodos y la asignación a estos de información, es el que se muestra a continuación.

Crea_arbol (APNODO)
El algoritmo crea un árbol binario en memoria. APNODO es una variable de tipo ENLACE puntero a un nodo. La primera vez APNODO se crea en el programa principal INFO, IZQ y DER son campos del registro NODO. INFO es de tipo carácter. IZQ y DER son de tipo puntero. Las variables RESP y OTRO son de tipo carácter y de tipo ENLACE, respectivamente

1. Leer APNODO.INFO Lee la información y se guarda en el nodo}
2. Escribir “¿Existe nodo por izquierda: 1(Sí) – 0(No)?”
3. Leer RESP
4. Si (RESP = "Sí')
      entonces
            Crear(OTRO) Se crea un nuevo nodo
            Hacer APNODO.IZQ <- OTRO
            Regresar a  Crea_arbol con APNODO^.IZQ Llamada recursiva
      si no
            Hacer APNODO.IZQ <- NULO
5. Fin del condicional del paso 4
6. Escribir “¿Existe nodo por derecha: 1(Sí) – 0(No)?
7. Leer RESP
8. Si (RESP = “Sí”)
      entonces
            Crear(OTRO) Se crea un nuevo nodo
            Hacer APNODO^.DER  <-  OTRO
            Regresar a Crea_arbol con APNODO^.DER Llamada recursiva 
      si no
            Hacer APNODOA.DER  <- NULO
9. Fin del condicional del paso 8

Una vez que se crea el árbol binario, se pueden realizar otras operaciones sobre sus elementos: recorrer todos los nodos, insertar un nuevo nodo, eliminar alguno de los existentes o buscar un valor determinado.

Una de las operaciones más importantes que se realiza en un árbol binario es el recorrido de los mismos. Recorrer significa visitar los nodos del árbol en forma ordenada, de tal manera que todos los nodos del mismo sean visitados una sola vez. Existen tres formas diferentes de efectuar el recorrido y todas ellas de naturaleza recursiva; estas son:

a) Recorrido en preorden 
      Visitar la raíz
      Recorrer el subárbol izquierdo
      Recorrer el subárbol derecho

b) Recorrido en inorden
      Recorrer el subárbol izquierdo
      Visitar la raíz
      Recorrer el subárbol derecho

c) Recorrido en posorden
      Recorrer el subárbol izquierdo
      Recorrer el subárbol derecho
      Visitar la raíz

De tal modo que la estructura Nodo quedaría de la siguiente forma:

Implementación en C sharp.

Class Arbol

{

Int info; //tipo dato aceptado por C#

Árbol  izq, der;

Public Arbol()//constructor de nodos

{

Info=”0”;

Izq=null;

Der=null;

}

Public Arbol raíz=null;//estado inicial = vacío

}