Vicente Gerbasi

Arbol: Un árbol (tree) es un T.D.A. que consta de un conjunto finito T de nodos y una relación R (paternidad) entre los nodos tal que:
Si n es un nodo y A1, A2, A3, A4, A5, …, Ak son árboles conraíces n1, n2, n3, n4,…, nk . Se puede construir un nuevo árbol haciendo que n se constituya en padre de los nodos n1, n2, n3, n4,…, nk.

• Aclaraciones: Si el conjunto finito T de nodos del árboles vacío, entonces se trata de un árbol vacío.

• En esta estructura existe sólo un nodo sin padre, que es la raíz del árbol.

• Todo nodo, a excepción del nodo raíz, tiene uno y sólo unpadre.

• Los subárboles de un nodo son llamados hijos.

Otras definiciones:

• Grado de un nodo: cantidad de hijos de un nodo.
•
• Grado de un árbol al mayor de los grados detodos sus nodos.
•
• Nodo hoja a un nodo sin hijos o con grado = 0.
•
• Nodo rama a un nodo que tiene hijos, o sea, a la raíz de un subárbol.

Nivel de un nodo al nivel de su padremás uno. Por definición, la raíz del árbol tiene nivel 0. Esta definición es recursiva.

Árbol completo de nivel n a un árbol en el que cada nodo de nivel n es una hoja y cada nodo de nivel menorque n tiene, al menos, un subárbol no vacío.

Árbol completo de nivel 2:Cada nodo del nivel n es una hoja
Árbol no completo de nivel 2: Un nodo del nivel n-1 es una hoja

Padre de un nodo al nodoraíz del subárbol más pequeño que contiene a dicho nodo y en el cual él no es raíz.

Hijo de un nodo al (los) nodo(s) raíz(ces) de uno de sus subárboles.

Predecesor de un nodo al nodo que leantecede en un recorrido del árbol.

Hermano de un nodo a otro nodo hijo de su padre.

Árbol ordenado a todo árbol para el que se considera el orden relativo de los sucesores o subárboles de cualquiernodo. Es decir, en un árbol ordenado se habla de primero, segundo o último hijo de un nodo en particular. El primer hijo de un nodo de un árbol ordenado es denominado el hijo mayor de ese nodo y...