Algoritmos INSERTAR y HEAPIFY

INSERCIÓN

Cuando se llega a un árbol vacío se crea el nodo en el puntero que se pasa como parámetro por referencia, de esta manera los nuevos enlaces mantienen la coherencia. Si el elemento a insertar ya existe entonces no se hace nada.

void insertar(tarbol **a, int elem)
{
  if (*a == NULL) {
    *a = (arbol *) malloc(sizeof(arbol));
    (*a)->clave = elem;
    (*a)->izq = (*a)->der = NULL;
  }
  else if ((*a)->clave < elem) insertar(&(*a)->der, elem);
  else if ((*a)->clave > elem) insertar(&(*a)->izq, elem);
}

Teoremas I y II para árboles Binarios.

TEOREMA I

Un grafo no dirigido es un árbol si, y solo si, hay un único camino entre cada pareja de vértices.

Supongamos que existe un árbol T, ademas de eso T es conexo y acíclico. Siendo a y b dos vertices de de T es conexo por el Teorema I, hay un camino entre a y b. Añadiendo que este camino debe de ser unico, ya que si existiese otro , entonces el recorrido construido de combinar  el primer camino de a y b con el camino de b hacia a, daria un circuito.

Tipos de Arboles (Binarios y HEAP).

ÁRBOL BINARIO 

Árbol de grado 2. De cada nodo parten como máximo dos subárboles disjuntos (izquierdo y derecho). También puede estar vacío. 

Conceptos Básicos de Árbol, Altura, Nivel, Grado.

Árbol: Estructura no lineal que organiza sus elementos formando jerarquías.

• Nodo: Elemento del árbol. 

• Árbol: Se define formalmente como una estructura finita formada por un nodo al cual están conectados ninguno, uno o más árboles disjuntos (no comparten elementos). 

Definición recursiva: lo definido se encuentra dentro de la definición.