Un árbol binario es una estructura de datos jerárquica en la que cada nodo no tiene más de dos descendientes (hijos). Por lo general, el primer nodo se denomina nodo padre y los hijos se denominan hijos izquierdo y derecho. Un árbol binario es un árbol dirigido ordenado [1] .
A efectos prácticos, se suelen utilizar dos subtipos de árboles binarios: un árbol de búsqueda binario y un montón binario .
Existe la siguiente definición recursiva de un árbol binario (ver BNF ):
<árbol binario> ::= ( <datos> <árbol binario> <árbol binario> ) | nulo .Es decir, un árbol binario está vacío o consta de datos y dos subárboles (cada uno de los cuales puede estar vacío). Un hecho obvio pero importante de entender es que cada subárbol es a su vez también un árbol. Si un nodo tiene ambos subárboles vacíos, se denomina nodo de hoja (vértice de hoja) o nodo de hoja (terminal) [2] .
Por ejemplo, se muestra a la derecha en la Fig. 1 árbol según esta gramática podría escribirse así:
| (metro (mi (C (un nulo nulo) nulo ) (gramo nulo (k nulo nulo) ) ) (s (p (o nulo nulo) (s nulo nulo) ) (y nulo nulo) ) ) |
Cada nodo del árbol define un subárbol del cual es la raíz. El nodo m = (datos, izquierda, derecha) tiene dos hijos (izquierda y derecha) izquierda y derecha y, en consecuencia, dos subárboles (izquierda y derecha) con raíces izquierda y derecha [3] .
Muchas estructuras de datos útiles se basan en el árbol binario:
| Árbol (estructura de datos) | |
|---|---|
| Árboles binarios | |
| Árboles binarios autoequilibrados |
|
| árboles B |
|
| árboles de prefijo |
|
| Partición binaria del espacio | |
| Árboles no binarios |
|
| Rompiendo el espacio |
|
| Otros árboles |
|
| Algoritmos | |