¿Qué es un árbol binario?
El árbol binario es otra estructura de árbol. Su característica es que cada nodo tiene como máximo dos subárboles (es decir, no hay nodos con un grado mayor que 2 en el árbol binario), y el árbol binario sí. subárboles izquierdo y derecho, y su orden no se puede invertir arbitrariamente. El árbol binario es una estructura de datos:
Binary_tree=(D,R)
Donde: D tiene las mismas características Una colección. de elementos de datos; si D es igual a vacío, entonces R es igual a vacío, lo que se denomina árbol binario vacío. Si D es igual a vacío, entonces R es un conjunto de una determinada relación binaria H en D, es decir, R={H}, y
(1) Hay un elemento único r llamado raíz en D, y su relación H no tiene predecesor
(2) Si D-; {r} no es igual a vacío, entonces D-{ r}={Dl,Dr}, y Dl cruza Dr igual a vacío
(3) Si Dl no es igual a vacío, entonces hay; es el único elemento xl en Dl, y 〈 r, xl〉 pertenece a H, y existe una relación Hl sobre Dl que pertenece a H si Dr no es igual a vacío, entonces hay un elemento único xr en Dr, 〈 r, xr〉 > pertenece a H, y existe una relación Hr sobre Dr que pertenece a H={r, xl,＜ r,xr＞ ,Hl, Hr}; (Dl, Hl) es un árbol binario definido por esta definición, llamado subárbol izquierdo de la raíz r, (Dr, Hr) es un árbol binario que cumple con la definición y se llama subárbol derecho de la raíz.
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) El subárbol derecho está vacío. Árbol binario (4) Árbol binario con subárbol izquierdo vacío (5) Árbol binario completo
Operaciones básicas de los árboles binarios:
(1) INITIATE(BT) Operación de inicialización. Configure BT para que sea un árbol vacío.
(2)ROOT(BT)\ROOT(x) Encuentra la función raíz. Encuentre el nodo raíz del árbol binario BT o encuentre 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 nodos principales 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 está "vacío".
(4)LCHILD(BT,x) y RCHILD(BT,x) encuentran la función del nodo secundario. Encuentre los nodos hijo izquierdo y derecho del nodo x en el árbol binario BT respectivamente.
Si el nodo x es un nodo hoja o no en el árbol binario BT, el valor de la función está "vacío".
(5)LSIBLING(BT,x) y RSIBING(BT,x) encuentran funciones hermanas. Encuentre los nodos hermano izquierdo y hermano derecho del nodo x en el árbol binario BT respectivamente.
Si el nodo x es el nodo raíz o no está en BT o es la raíz del subárbol izquierdo/derecho de sus padres, el valor del árbol de funciones está "vacío".
(6)Operación de creación CRT_BT(x,LBT,RBT). Genere un árbol binario con el nodo x como raíz y 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. Establezca el árbol binario con el nodo x como raíz y el subárbol derecho vacío como el subárbol izquierdo y el subárbol derecho del nodo y en el árbol binario BT, respectivamente. Si el nodo y tiene un subárbol izquierdo/subárbol derecho, entonces la inserción es 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 con raíz en el nodo x en el árbol binario BT, respectivamente.
Si x no tiene subárbol izquierdo ni derecho, no hay operación.
(9)TRAVERSE(BT) operación transversal.
Visite cada nodo del árbol binario en un orden determinado, de modo 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
1. Estructura de almacenamiento secuencial
Las unidades de almacenamiento continuo almacenan los elementos de datos del árbol binario. Por ejemplo, para el árbol binario completo de la Figura 6.4(b), el vector (matriz unidimensional) bt(1:6) puede usarse como estructura de almacenamiento, y el elemento de datos del nodo numerado i en el árbol binario se almacena en el componente bt[i], como se muestra en la Figura 6.6(a). Sin embargo, esta estructura de almacenamiento secuencial solo es adecuada para árboles binarios completos y, en general, los árboles binarios también se almacenan de esta forma, lo que provocará desperdicio de almacenamiento. Como se muestra en la Figura 6.6 (b), la estructura de almacenamiento correspondiente al árbol binario en la Figura 6.4 (c), "0" en la figura indica que este nodo no existe
2.
De la definición de un árbol binario, sabemos que el nodo de un árbol binario consta de un elemento de datos y dos ramas que apuntan a los subárboles izquierdo y derecho respectivamente. Esto significa que el nodo en la lista vinculada. del árbol binario contiene al menos tres campos: el campo de datos y los dominios de punteros izquierdo y derecho, como se muestra en la Figura (b). A veces, para facilitar la búsqueda de los padres de un nodo, se puede agregar a la estructura del nodo un campo de puntero que apunte a sus padres, 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 visitar cada nodo del árbol de acuerdo con una determinada ruta de búsqueda para que cada nodo se visite una sola vez. una vez. Hay tres situaciones comunes: se denominan 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
Operación de 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. La operación transversal de preorden accede a cada nodo del árbol binario en el orden de raíz, izquierda y derecha. Por ejemplo:
El resultado de recorrer este árbol binario en preorder es: ¡Hola! ¿Cómo estás?
proc preorder(bt:bitreprtr)
if ( bt> null)[
print(bt^);
preorden(bt^.lchild);
preorden(bt^.rchild);]
end;
5.3.2 Recorrido en orden
Operación de recorrido en orden: es decir, primero atraviesa el subárbol izquierdo en preorden y luego visita el nodo raíz y, finalmente, atraviesa en orden el subárbol derecho. La operación transversal en orden accede a cada nodo del árbol binario en el orden de izquierda, raíz y derecha. Por ejemplo:
El resultado de recorrer este árbol binario en orden es: a*b-c
proc inorder(bt:bitreprtr)
if (bt>null )[
inorder(bt^.lchild);
print(bt^);
niorder(bt^.rchild);]
end;
5.3.3 Recorrido posterior al pedido
Operación transversal posterior al pedido: atraviesa el subárbol izquierdo en orden, luego atraviesa el subárbol derecho en orden y finalmente visita el nodo raíz. La operación transversal posterior al orden accede a cada nodo del árbol binario en el orden de izquierda, derecha y raíz.
Por ejemplo:
El resultado de recorrer este árbol binario en orden de publicación es: ¡Bienvenido a usarlo!
proc postorder(bt:bitreprtr)
if ( bt>null )[
postorder(bt^.lchild);
postorder(bt^.rchild);]
print(bt^); /p>
end;
5. Ejemplo:
1. Utilice el almacenamiento secuencial para crear un árbol binario completo con 31 nodos y realice un recorrido de pedido previo en él.
2. Utilice el almacenamiento de listas vinculadas para construir un árbol binario como se muestra en las Figuras 3 y 4, y realice un recorrido de pedido previo en él.
3. Dado un conjunto de datos: R={10.18,3,8,12,2,7,3}, intente programar primero construya un árbol binario y luego acceda a todos los datos en orden. recorrido. Obtenga el árbol binario y genere los resultados del recorrido.
4. Dadas ocho monedas de oro a, b, c, d, e, f, g, h, programe para pesarlas el número mínimo de veces para determinar si hay monedas falsas. Descubra esta moneda falsa y determine si la moneda falsa es pesada o liviana.
Preparado por el equipo de competencia de informática de la escuela bilingüe Sanxin de la escuela secundaria Sun Yat-sen Memorial 2004.7.15