Arbol

Solo disponible en BuenasTareas
  • Páginas : 7 (1618 palabras )
  • Descarga(s) : 0
  • Publicado : 7 de diciembre de 2011
Leer documento completo
Vista previa del texto
Declaración de tipos
Como estamos trabajando con un árbol binario, sólo necesitamos una estructura para referirnos tanto a cualquiera de los nodos como al árbol completo. Recuerda que cualquier nodo puede ser considerado como la raíz de un árbol.
-------------------------------------------------
typedef struct _nodo \{
-------------------------------------------------int dato;
-------------------------------------------------
struct _nodo *derecho;
-------------------------------------------------
struct _nodo *izquierdo;
-------------------------------------------------
} tipoNodo;
--------------------------------------------------------------------------------------------------
typedef tipoNodo *pNodo;
-------------------------------------------------
typedef tipoNodo *Arbol;
Insertar un elemento en un árbol ABB
Diseñaremos una función que se ajuste al algoritmo que describimos en el punto 7.4:
1. Padre = NULL
2. nodo = Raiz
3. Bucle: mientras actual no sea un árbol vacío o hasta que se encuentre elelemento.
a. Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo: Padre=nodo, nodo=nodo->izquierdo.
b. Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho: Padre=nodo, nodo=nodo->derecho.
4. Si nodo no es NULL, el elemento está en el árbol, por lo tanto salimos.5. Si Padre es NULL, el árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el nuevo elemento, que será la raíz del árbol.
6. Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol izquierdo de Padre.
7. Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol derecho de Padre.-------------------------------------------------
void Insertar(Arbol *a, int dat) \{
-------------------------------------------------
pNodo padre = NULL; /* (1) */
-------------------------------------------------
pNodo actual = *a; /* (2) */
--------------------------------------------------------------------------------------------------
while(!Vacio(actual) && dat != actual->dato) \{ /* (3) */
-------------------------------------------------
padre = actual;
-------------------------------------------------
if(dat < actual->dato) actual = actual->izquierdo; /* (3-a) */
-------------------------------------------------
elseif(dat > actual->dato) actual = actual->derecho; /* (3-b) */
-------------------------------------------------
}
-------------------------------------------------

-------------------------------------------------
if(!Vacio(actual)) return; /* (4) */
-------------------------------------------------if(Vacio(padre)) \{ /* (5) */
-------------------------------------------------
*a = (Arbol)malloc(sizeof(tipoNodo));
-------------------------------------------------
(*a)->dato = dat;
-------------------------------------------------
(*a)->izquierdo = (*a)->derecho = NULL;
-------------------------------------------------}
-------------------------------------------------
else if(dat < padre->dato) \{ /* (6) */
-------------------------------------------------
actual = (Arbol)malloc(sizeof(tipoNodo));
-------------------------------------------------
padre->izquierdo = actual;
-------------------------------------------------...
tracking img