Arboles

MiEmpresa

Ventas Producción

Portátiles Pc’sVe Internacional

Europa Asia América

A

B C

D E F G

IH

Nodo RAIZ

A

B C

D E F G

H

C: es padre de

F y G

F y G son Hijos de CF y G son hermanos

A

B C

D E F G

H

D: Es un nodo

interno

H: es un nodo hoja

A

B C

D E F G

H

Subárbol Izquierdo de B

Subárbol derecho de B

A

B C

D E F G

H

Nivel 0

Nivel 1

Nivel 2

Nivel 3

A

B C

D E F G H

I J K

A

B C

D E F G H

I J K

Nodo Altura Nivel Grado

A 3 0 2

B 2 1 2

C 2 1 3

D 1 2 2

E 0 2 0

F 1 2 1

G 0 2 0

H 0 2 0

I 0 3 0

J 0 3 0

K 0 3 0

A

B C

D E F G

H I

A

B C

D E F G

H I

A

B C

D E F G

H I J K

A

B C

D E F G

H I

A

C B

E D F G

H I

A

C B

D E F G

H I

A

C B

D E F G

H I

A

B C

D E F G

H IJ

0 1 1 2 2 5 5 5 3 3

1 2 3 4 5 6 7 8 9 10

A(i) es el nodo padre del nodo i

A(4)=B es el nodo padre del nodo D

EnlaceIzquierdo

Información EnlaceDerecho

- A -

+

* ^

A B / 35

C D

+

^*

- B - B 35

A

BC

D E F

G H

A

BC

D E F

G H

RECORRIDO: D,B

A

BC

D E F

G H

RECORRIDO: D,B,A

A

BC

D E F

G H

RECORRIDO: D,B,A,G

A

BC

D E F

G H

RECORRIDO: D,B,A,G,E

A

BC

D E F

G H

RECORRIDO: D,B,A,G,E,H

A

BC

D E F

G H

RECORRIDO: D,B,A,G,E,H,C

A

BC

D E F

G H

RECORRIDO: D,B,A,G,E,H,C,F.

A

BC

D E F

G H

A

BC

D E F

G H

RECORRIDO: A,B

A

BC

D E F

G H

RECORRIDO: A,B,D

A

BC

D E F

G H

RECORRIDO: A,B,D,C

A

BC

D E F

G H

RECORRIDO: A,B,D,C,E

A

BC

D E F

G H

RECORRIDO: A,B,D,C,E,G

A

BC

D E F

G H

RECORRIDO: A,B,D,C,E,G,H

RECORRIDO: A,B,D,C,E,G,H,F

A

BC

D E F

G H

A

BC

D E F

G H

A

BC

D E F

G H

RECORRIDO: D,B

A

BC

D E F

G H

RECORRIDO: D,B,G

A

BC

D E F

G H

RECORRIDO: D,B,G,H

A

BC

D E F

G H

RECORRIDO: D,B,G,H,E

A

BC

D E F

G H

RECORRIDO: D,B,G,H,E,F

A

BC

D E F

G H

RECORRIDO: D,B,G,H,E,F,C

RECORRIDO: D,B,G,H,E,F,C,A.

A

BC

D E F

G H

Crear el arbolInsertar un nodoEliminar un nodo

TYPETipoPuntero = TipoNodoABB;TipoNodoABB = RECORDinfo : TipoInfo;izquierdo : TipoPuntero;derecho: TipoPuntero;End;

Crear un ABB vacío.

Procedure InicializaArbol(var RaizArbol: TipoPuntero);BeginRaizArbol := NulL;

End;

Procedure Insertar_arbol_binario( var Raizarbol: TipoPuntero;InfoNodo: TipoInfo);

VarNuevoNodo: TipoPuntero; (*puntero para nodo nuevo*)Ptr, Anterior:TipoPuntero; (* usado para buscar en el ABB*)ClaveNueva: TipoClave;(* clave del nuevo nodo a insertar*)BEGIN(* Crear un nuevo nodo*)New(NuevoNodo); NuevoNodo^.izquierdo:= NIL; NuevoNodo^.derecho:= NIL;NuevoNodo^.info:= InfoNodo;(* Buscar el lugar de inserción*)ptr: = RaizArbol; Anterior: = NIL;

While ptr <> NIL Dobeginanterior : = ptr;if ptr^.info.clave > ClaveNueva thenptr := ptr^.izquierdoelseptr := ptr^.derechoend;

if anterior = NIL thenraizarbol = NuevoNodoelseif anterior^.info.clave > ClaveNueva thenanterior^.izquierdo: = Nuevonodoelseanterior^.derecho: = NuevonodoEND;

Eliminar elementos ya existentes.

(a)Eliminación de un nodo hoja sólo consiste en anular el puntero de su nodo padre

(b)Eliminación de un nodo con un hijo, es necesario reasignar el puntero del padre hacia el hijo.

(c)Eliminación de un nodo con dos hijos : Reemplazar el nodo que deseamos suprimir con el nodo de valor más próximo al valor del nodo suprimido. Así será posible hacer el reemplazo por "El mayor más cercano" o "El menor más cercano", dependiendo de qué subárbol sea escogido el nodo.

Procedure SuprimirNodo (Var RaízArbol : Tipo_Puntero; ptr, anterior: Tipo_ Puntero);

(* Suprime el nodo apuntado por Ptr sobre el árbol binario con puntero RaizArbol, Anterior es un puntero al nodo padre ( NIL si el nodo a suprimir es el nodo Raiz*)Vartemp: Tipo_Puntero;BEGIN(*Caso b.1 Supresión de una hoja*)if(ptr^.derecho = NIL) AND (ptr^.izquierdo = NIL) thenIF Anterior = NIL then (*Nodo(ptr) es el último en el árbol)RaizArbol:= NILelseif anterior^.derecho = Ptr thenanterior^.derecho : = NILelse anterior^.izquierdo: = NIL

Else (* Caso b.3 supresión de nodo con dos hijos*)if(ptr^.derecho <> NIL) AND (ptr^.izquierdo <> NIL) thenbegin (* Encontrar el valor para reemplazar, valor más próximo al eliminado*)anterior: = ptr;temp := ptr^.izquierdo;

While temp^.derecho<> NIL Dobeginanterior:= temp;temp : = temp^.derechoend;

(* Copiar la información a reemplazar en el nodo*)

ptr^.info:= temp^.info;if anterior = Ptr thenanterior^.izquierdo:= temp^.izquierdoelseanterior^.derecho:= temp^.izquierdo;ptr:= temp;end

else (* Caso b.2 Nodo con un hijo*)

(* Inicializa uno de los campos punteros de nodo (anterior) dependiendo si tiene un hijo a la derecha o izquierda*)

if ptr^.derecho <>NIL then (* Hay un hijo derecho*)if anterior = NIL thenRaizArbol:= Ptr^.derechoelseif anterior^.derecho=ptr thenanterior^.derecho := ptr^.derechoelseanterior^.izquierdo := ptr^.derechoelse(* hay un hijo izquierdo*)if anterior = NIL thenRaizArbol:= Ptr^.izquierdoelseif anterior^.derecho=ptr thenanterior^.derecho := ptr^.izquierdoelseanterior^.izquierdo := ptr^.izquierdo;dispose (ptr);END;