El concepto de árbol binario
Un árbol binario es un conjunto finito de nodos N (n> = 0). Este conjunto es un conjunto vacío (árbol binario vacío) o consiste en un nodo raíz y dos árboles binarios que no se cruzan entre sí, llamados nodo raíz y el subárbol derecho respectivamente.
Características de los árboles binarios
Cada nodo tiene como máximo dos subárboles, por lo que no hay nodos con un grado mayor que 2 en el árbol binario. Cada nodo en el árbol binario es un objeto, y cada nodo de datos tiene tres punteros, a saber, punteros para el padre, el niño izquierdo y el niño derecho. Cada nodo está conectado entre sí a través de un puntero. La relación entre los punteros conectados es toda la relación padre-hijo.
Definición de nodos de árbol binarios
El nodo del árbol binario se define de la siguiente manera:
La copia del código es la siguiente:
struct binaryTeNode
{
int m_nValue;
BinaryTreenode* m_pleft;
BinaryTreenode* M_Pright;
};
Cinco formas básicas de árboles binarios
Árbol binario vacío
Solo hay un nodo raíz
El nodo raíz solo tiene el subárbol izquierdo
El nodo raíz solo tiene el subárbol correcto
El nodo raíz tiene un subárbol izquierdo y derecho
Solo hay dos casos para árboles ordinarios con tres nodos: dos o tres. Sin embargo, dado que el árbol binario tiene que distinguir a la izquierda y a la derecha, evolucionará hacia las siguientes cinco formas:
Árbol binario especial
Árbol inclinado
Como se muestra en la segunda y tercera pequeñas imágenes en la penúltima subplicción de arriba.
Árbol binario completo
En un árbol binario, si todos los nodos de ramificación tienen subárboles izquierdo y derecho, y todas las hojas están en la misma capa, dicho árbol binario se llama árbol binario completo. Como se muestra en la figura a continuación:
Árbol binario completo
Un árbol completamente binario significa que la última capa está llena a la izquierda, el lado derecho puede estar lleno o no, y el resto de las capas están llenas. Un árbol binario con una profundidad de k y varios nodos de 2^k - 1 es un árbol binario completo (árbol binario completo). Es un árbol con una profundidad de k y sin espacio.
Las características de un árbol completamente binario son:
Los nodos de la hoja solo pueden aparecer en las dos capas más bajas.
La hoja más baja debe concentrarse en una posición continua a la izquierda.
En la penúltima capa, si hay nodos de hoja, deben estar en posiciones continuas a la derecha.
Si el grado de nodo es 1, entonces el nodo solo tiene el hijo izquierdo.
Para los árboles binarios con el mismo árbol de nodo, el árbol binario completo tiene la profundidad más pequeña.
Nota: Un árbol binario completo debe ser un árbol completamente binario, pero un árbol completamente binario puede no ser un árbol binario completo.
El algoritmo es el siguiente:
La copia del código es la siguiente:
bool is_complete (árbol *raíz)
{
cola q;
Árbol *ptr;
// Realizar el recorrido de la prioridad (transversal jerárquico) y coloque los nodos nulos en la cola también
q.push (raíz);
while ((ptr = q.pop ())! = nulo)
{
q.push (ptr-> izquierda);
q.push (ptr-> derecha);
}
// Determinar si todavía hay nodos a los que no se ha accedido
While (! Q.is_empty ())
{
ptr = q.pop ();
// Si hay nodos no nulos a los que no se accede, el árbol tiene un vacío y es un árbol binario no complicado.
if (null! = ptr)
{
devolver falso;
}
}
devolver verdadero;
}
Propiedades de los árboles binarios
Propiedad 1 del árbol binario: hay como máximo 2^(i-1) nodos en la capa i-th del árbol binario (i> = 1)
Propiedad 2 del árbol binario: el árbol binario con profundidad K tiene como máximo los nodos 2^K-1 (k> = 1)
Estructura de almacenamiento secuencial de árboles binarios
La estructura de almacenamiento secuencial de un árbol binario es usar una matriz unidimensional para almacenar cada nodo en el árbol binario, y la ubicación de almacenamiento de los nodos puede reflejar la relación lógica entre los nodos.
Lista de enlaces binarios
Dado que el método de almacenamiento secuencial no es muy aplicable, debemos considerar la estructura de almacenamiento de la cadena. Según la práctica internacional, el almacenamiento de árboles binarios generalmente adopta una estructura de almacenamiento en cadena.
Cada nodo de un árbol binario tiene como máximo dos niños, por lo que es una idea natural diseñar un campo de datos y dos campos de puntero para él. Llamamos a una lista de este tipo una lista binaria vinculada.
Recorrido de árboles binarios
El recorrido binario que atraviesa se refiere a acceder a todos los nodos en el árbol binario en un determinado orden desde el nodo raíz, de modo que se accede a cada nodo una vez y solo una vez.
Hay tres formas de atravesar árboles binarios, como sigue:
(1) Re-orden de transferencia (DLR), primero accediendo al nodo raíz, luego atravesando el subárbol izquierdo y finalmente atravesando el subárbol derecho. Raíz abreviada - izquierda - derecha.
(2) Traversal en orden (LDR), primero atraviesa el subárbol izquierdo, luego acceda al nodo raíz y finalmente atraviesa el subárbol derecho. Nota abreviada: raíz izquierda-derecha.
(3) Traversal posterior al orden (LRD), primero atravesando el subárbol izquierdo, luego atravesando el subárbol derecho y finalmente accediendo al nodo raíz. Raíz izquierda-derecha abreviada.
PREAMBLO Traversal:
Si el árbol binario está vacío, la operación vacía regresa. De lo contrario, primero acceda al nodo raíz, luego atraviese el subárbol izquierdo en el orden anterior y luego atraviese el subárbol derecho en el orden anterior.
El orden de transversal es: abdhiejcfkg
La copia del código es la siguiente:
// Traversal preciso
preorden de función (nodo) {
if (! node == null) {
PUTSTR (node.show ()+ "");
preorden (node.left);
preorden (nodo.right);
}
}
Traversal en orden:
Si el árbol está vacío, la operación vacía regresa, de lo contrario se inicia desde el nodo raíz (tenga en cuenta que no se accede al nodo raíz primero), y el subárbol izquierdo del nodo raíz se atraviesa en el orden medio, entonces se accede al nodo raíz y finalmente el subárbol derecho se atraviesa en el orden medio.
El orden de transversal es: hdibejafkcg
La copia del código es la siguiente:
// Use el método recursivo para implementar el recorrido de orden medio
function inorder (node) {
if (! (node == null)) {
Inorder (node.left); // Agregar primero al subárbol izquierdo
PUTSTR (node.show ()+ ""); // Agregar al nodo raíz nuevamente
Inorder (node.right); // Último acceso al subárbol correcto
}
}
Traversal posterior al orden:
Si el árbol está vacío, la operación vacía regresa. De lo contrario, los subárboles izquierdo y derecho se atraviesan de izquierda a derecha para acceder a los subárboles izquierdo y derecho, y finalmente acceden al nodo raíz.
El orden de transversal es: Hidjebkfgca
La copia del código es la siguiente:
// transversal posterior al orden
función PostOrder (nodo) {
if (! node == null) {
PostOrder (node.left);
PostOrder (node.right);
PUTSTR (node.show ()+ "");
}
}
Implementar un árbol de búsqueda binario
El árbol de búsqueda binario (BST) está compuesto de nodos, por lo que definimos un objeto de nodo de nodo de la siguiente manera:
La copia del código es la siguiente:
Function Node (datos, izquierda, derecha) {
this.data = data;
this.left = izquierda; // Guardar el enlace del nodo izquierdo
this.right = Right;
this.show = show;
}
función show () {
devolver esto.data; // Mostrar datos guardados en el nodo
}
Encontrar valores máximos y mínimos
Encontrar los valores mínimos y máximos en el BST es muy simple, porque los valores más pequeños siempre están en el nodo infantil izquierdo y buscan el valor mínimo en el BST, simplemente atraviese el árbol infantil izquierdo hasta que se encuentre el último nodo
Encuentra el valor mínimo
La copia del código es la siguiente:
función getmin () {
var corriente = this.root;
while (! (current.left == null)) {
corriente = corriente.left;
}
return current.data;
}
Este método atraviesa uno por uno a lo largo del subárbol izquierdo de BST hasta que atraviesa el nodo más a la izquierda de BST, que se define como:
La copia del código es la siguiente:
actual.left = nulo;
En este momento, el valor guardado en el nodo actual es el valor mínimo
Encuentra el valor máximo
Encontrar el valor máximo en BST solo requiere atravesar el subárbol correcto hasta que se encuentre el último nodo, y el valor guardado en ese nodo es el valor máximo.
La copia del código es la siguiente:
función getMax () {
var corriente = this.root;
while (! (current.right == null)) {
actual = corriente.right;
}
return current.data;
}