¿Qué es un árbol binario?
Binary_tree=(D, R)
Donde: D es un conjunto de elementos de datos con las mismas características, si D es igual a vacío, entonces; R es igual a vacío, se llama árbol binario vacío; si D es igual a vacío, entonces R es el conjunto de relaciones binarias H sobre D, es decir, R = {H}, y
( 1) Hay un elemento único r en D, llamado raíz, tiene una relación H elemento r, y no hay ningún antecedente bajo la relación H;
(2) Si D-{r} es no es igual a cero, entonces D-{r}={Dl, Dr } Y Dl cruza a Dr igual a cero;
(3) Si Dl no es igual a cero, entonces hay un elemento único xl , 〈 r, xl〉 que pertenece a H en Dl, y existe una relación Hl que pertenece a H en Dl ; Si Dr no es igual a vacío, entonces hay un elemento único xl, 〈 r, xl〉 en Dr que pertenece a H; ; si Dl no es igual a vacío, entonces hay un elemento único xl, 〈 r, xl〉 en Dr que pertenece a H ; Si Dr no está vacío, entonces hay un elemento único xr que pertenece a H, 〈 r, xr〉 gt;, y existe una relación Hr en Dr que pertenece a H={r, xl, 〈 r, xr〉, Hl, Hr };
(4) (Dl, Hl) es un árbol binario que cumple con la definición, llamado subárbol izquierdo de la raíz r, (Dr, Hr) es un árbol binario que cumple con la definición, llamada raíz El subárbol derecho de.
Entre ellos, la Figura 6.2 muestra varias formas de árboles binarios.
(1) Árbol binario vacío (2) Árbol binario con un solo nodo raíz (3) Árbol binario con subárbol derecho vacío (4) Árbol binario con subárbol izquierdo vacío (5) Árbol binario completo
Operaciones básicas de árboles binarios:
(1) Operación de inicialización INITIATE(BT). Configure BT en un árbol vacío.
(2)Función de búsqueda de raíces ROOT(BT)/ROOT(x). Encuentre el nodo raíz del árbol binario BT, o busque el nodo raíz del árbol binario donde se encuentra el nodo x.
Si BT es un árbol vacío o x no está en ningún árbol binario, el valor de la función está "vacío".
(3) PARENT(BT, x) encuentra la función principal. Encuentre los padres del nodo x en el árbol binario BT. Si el nodo x es el nodo raíz del árbol binario BT
, o no hay ningún nodo x en el árbol binario BT, el valor de la función es "nulo".
(4) LCHILD(BT, x) y RCHILD(BT, x) encuentran funciones de nodo secundario. Encuentre los nodos secundarios izquierdo y derecho del nodo x en el árbol binario BT.
Si el nodo x no es un nodo hoja en el árbol binario BT, el valor de la función es "nulo".
(5) LSIBLING(BT, x) y RSIBING(BT, x) encuentran funciones hermanas. Encuentre el nodo hermano izquierdo y el nodo hermano derecho del nodo x en el árbol binario BT, respectivamente.
Si el nodo x no es el nodo raíz en el árbol binario BT, ni el nodo raíz del subárbol izquierdo/derecho de sus dos nodos principales, el valor del árbol alfa es "nulo".
(6) Operación de creación de árbol CRT_BT(x, LBT, RBT). Genere un árbol binario con el nodo x como raíz y los árboles binarios LBT y RBT como subárboles izquierdo y derecho respectivamente.
(7) INS_LCHILD(BT, y, x) e INS_RCHILD(BT, x) insertan operaciones de subárbol.
Un árbol binario con el nodo x como raíz y un subárbol derecho vacío
Coloque los subárboles izquierdo y derecho del nodo y en el árbol binario BT. Si el nodo y tiene un subárbol izquierdo/subárbol derecho, se inserta el subárbol derecho del nodo x.
(8) DEL_LCHILD(BT, x) y DEL-RCHILD(BT, x) eliminan operaciones de subárbol. Elimine el subárbol izquierdo o el subárbol derecho del árbol binario BT con raíz en el nodo x respectivamente.
Si x no tiene subárbol izquierdo ni derecho, realice una operación no operativa.
(9) TRAVERSE(BT) operación transversal. Visite cada nodo del árbol binario en un orden determinado y haga que cada nodo se visite solo una vez.
(10)CLEAR(BT) Operación de limpieza de estructura. Establezca el árbol binario BT en un árbol vacío.
5.2.2 Estructura de almacenamiento del árbol binario
I. Estructura de almacenamiento secuencial
La unidad de memoria secuencial almacena los elementos de datos del árbol binario. Por ejemplo, el árbol binario completo de la Figura 6.4(b) puede utilizar el vector (matriz unidimensional) bt(1:6) como estructura de almacenamiento, y el nodo del árbol binario numerado i se almacenará en el componente del elemento de datos bt. [i], como se muestra en la figura Como se muestra en 6.6(a). Sin embargo, esta estructura de almacenamiento secuencial solo es aplicable a árboles binarios completos. Los árboles binarios generales también se almacenan de esta forma, lo que provocará una pérdida de espacio de almacenamiento. Como se muestra en la Figura 6.6 (b), la estructura de almacenamiento correspondiente del árbol binario en la Figura 6.4 (c) se muestra en la Figura 6.6 (b), donde "0" indica que el nodo no existe.
2. Estructura de almacenamiento vinculada
Según la definición de árbol binario, sabemos que el nodo del árbol binario consta de un elemento de datos y dos ramas que apuntan a la izquierda y a la derecha. subárboles respectivamente, lo que muestra que la lista vinculada del árbol binario Los nodos en se componen de al menos tres campos: campo de datos y campos de puntero izquierdo y derecho, como se muestra en la Figura (b). A veces, para facilitar la búsqueda del nodo principal de un nodo, la estructura del nodo también puede agregar un puntero al nodo principal afectado por el campo de puntero, como se muestra en la Figura 6.7 (c).
5.3 Atravesar un árbol binario
El problema de atravesar un árbol binario es cómo acceder a cada nodo del árbol a lo largo de una determinada ruta de búsqueda para que cada nodo se visite solo una vez. Hay tres situaciones comunes: recorrido de primer orden (raíz), recorrido de orden medio (raíz) y recorrido de último orden (raíz).
5.3.1 Recorrido de preorden
Recorrido de preorden: primero visite el nodo raíz, luego atraviese el subárbol izquierdo en preorden y finalmente atraviese el subárbol derecho en preorden. Se accede a la operación transversal de pedido previo para acceder a los nodos del árbol binario en el orden de raíz, izquierda y derecha. Por ejemplo:
El resultado de recorrer este árbol binario en preorden es ¡Hola! ¿Cómo estás?
proc preorder(bt: bitreprtr)
if (btlt; gt; null)[
print(bt^
preorden(bt^.lchild);
preorden(bt^.rchild);]