Jsgcykufgeuac

Árboles Binarios

Un árbol binario T se define como un conjunto finito de elementos, llamados nodos, de forma que:

a. T es vacío ( en cuyo caso se llamaárbol nulo o árbol vació) o
b. T contiene un nodo distinguido R, llamado raíz de T, y los restantes nodos de T forman un par ordenado de árboles binarios disjuntosT1 y T2.

Si T contiene una raíz R, los dos árboles T1 y T2 se llaman, respectivamente, subárboles izquierdo y derecho de la raíz R. Si T1 no es vació , entoncessu raíz se llama sucesor izquierdo de R; y análogamente, si T2 no es vació, su raíz se llama sucesor derecho de R.

Observe que :

a. B es un sucesorizquierdo y C un sucesor derecho del nodo A.
b. El subárbol izquierdo de la raíz A consiste en los nodos B, D, E y F, y el subárbol derecho de A consiste en los nodos C, G, H, J, K y L.

[pic]

Cualquier nodo N de un árbol binario T tiene 0, 1 ó 2 sucesores. Los nodos A,B,C y H tienen dos sucesores, los nodos R y J sólotienen un sucesor , y los nodos D,F, G,L y K no tienen sucesores. Los nodos sin sucesores se llaman nodos terminales.

La definición anterior del árbol binario T esrecursiva, ya que T se define en términos de los subárboles binarios T1 y T2. Esto significa, en particular, que cada nodo N de T contiene un subárbol izquierdo yuno derecho. Más aun, si N es un nodo terminal, ambos árboles están vacíos.

Dos árboles binarios T y T’ se dicen que son similares si tienen la misma estructurao, en otras palabras, si tienen la misma forma. Los árboles se dice que son copias si son similares y tienen los mismos contenidos en sus correspondientes nodos.