¿Conoces los árboles en Python?
Árboles y árboles binarios
Antes de comprender los árboles binarios, primero debemos comprender algunos conceptos de árboles para que podamos comprender los árboles binarios más fácilmente.
¿Qué es un árbol?
Árbol (inglés: árbol) es un tipo de datos abstracto (ADT) o una estructura de datos de este tipo de datos abstracto, que se utiliza para modelar colecciones de datos con una estructura de árbol.
Consta de n (n>=1) número limitado de nodos formando un conjunto con relaciones jerárquicas. Se llama "árbol" porque parece un árbol invertido, con las raíces hacia arriba y las hojas hacia abajo. Tiene las siguientes características:
Cada nodo tiene cero o más nodos secundarios;
Un nodo sin un nodo padre se llama nodo raíz;
Cada nodo Los nodos no raíz tienen un solo nodo padre;
Excepto el nodo raíz, cada nodo hijo se puede dividir en subárboles separados;
Terminología de árbol:
Terminología de árbol:
El grado de un nodo: el número de subárboles que contiene un nodo se llama grado del nodo;
El grado del árbol: el grado del mayor El nodo en el árbol se llama grado del árbol;
Nodo raíz: el nodo en la parte superior del árbol, que continúa hacia abajo hasta los nodos secundarios
Nodo principal: el nodo principal del nodo un nivel por encima del nodo hijo
Nodos hermanos: los nodos con el mismo nodo padre se denominan nodos hermanos
Nodos hoja/terminal: los nodos que ya no tienen nodos hijos son nodos hoja
Árbol binario:
p>El árbol binario es un tipo especial de árbol con las siguientes características:
Cada nodo tiene como máximo dos nodos secundarios y el máximo el orden del nodo es 2
Los subárboles izquierdo y derecho tienen un orden y el orden no se puede invertir
En otras palabras, si un nodo tiene solo un subárbol, el orden izquierdo y se deben distinguir los subárboles derechos
Características de los árboles binarios:
En el i-ésimo nivel de un árbol binario no vacío, hay como máximo 2i-1 nodos (i> =1)
En un árbol binario con profundidad K, hay como máximo 2i-1 nodos (i>=1) )
En un árbol binario con profundidad K, hay como máximo 2i-2 nodos (i>=2).
En un árbol binario de profundidad K, hay como máximo 2k-1 nodos (k>=2). 1)
Para cualquier árbol binario no vacío, si el número de nodos hoja es n0 y el número de nodos con orden 2 es n2, entonces tenemos n0=n2+1
Proceso de inferencia inversa: en el árbol binario, además de los nodos hoja (orden 0), todavía hay nodos con órdenes 2 (n2) y 1 (n1), y nodos con órdenes 2 (n2) y 1 (n1) . Por lo tanto, el número total de nodos del árbol es T = n0 + n1 + n2, en un árbol binario, el número total de nodos es T y el número total de enlaces es T-1 = 2*n2 + n1, entonces n0; + n1 + n2 - 1 = 2 *n2 + n1, es decir, n0 = n2 + 1.
Árbol binario especial
Árbol binario completo
En un árbol binario, excepto los nodos hoja, el grado de todos los nodos es 2 y todos los nodos hoja son en el mismo En el mismo nivel, este árbol se convierte en un árbol binario completo.
Características de un árbol binario completo:
Los nodos hoja solo pueden aparecer en el nivel inferior
El orden de los nodos que no son hoja debe ser 2
Entre los árboles binarios con la misma profundidad, el árbol binario completo tiene el mayor número de nodos y nodos hoja
Árbol binario completo
Si el árbol binario es un binario completo árbol después de eliminar el último nodo hoja, y el último Los nodos hoja de la capa se distribuyen de izquierda a derecha, entonces dicho árbol binario se llama árbol binario completo
Características de un árbol binario completo:
Los nodos de hoja generalmente aparecen en el nivel más bajo. Si aparece un nodo de hoja en el penúltimo nivel, debe ubicarse en una posición continua a la derecha.
Los nodos de hoja en el nivel más bajo. debe concentrarse en una posición continua a la izquierda
Para árboles binarios con el mismo número de nodos, la profundidad del árbol binario completo Mínima (el árbol binario completo también es correcto)
Pequeña pregunta de ejemplo:
¿Un árbol binario completo**** tiene 200 nodos y el árbol binario**** tiene ( ) nodos hoja?
Solución: n0 + n1 + n2 = 200, donde n0 = n2 + 1, n1 = 0 o 1 (n1 = 1, el número de nodos que aparecen en la capa más baja es un número impar y el El número de nodos en la capa más baja es un número par, entonces n1 = 0), dado que n0 es un número entero, el resultado final del cálculo es n0 = 100.
Características de un árbol binario completo:
La profundidad de un árbol binario completo con n nodos es log2n+1, y el resultado de log2n es la parte entera.
Si hay un árbol binario completo con n nodos y los nodos están numerados en orden jerárquico, para el nodo i en cualquier nivel (1 <= i <= n)
1 Si i = 1, entonces el nodo es el nodo raíz del árbol binario y no tiene un nodo padre; si i>1, entonces su nodo padre es i/2, redondeado hacia abajo
2. *1>n, entonces el nodo i no tiene un nodo hijo izquierdo; de lo contrario, su nodo hijo izquierdo es 2i
3. Si 2i+1>n, entonces el nodo no tiene un nodo hijo derecho; de lo contrario, su nodo hijo derecho es 2i+1
Verificación:
Primero:
Cuando i = 1, es el nodo raíz. Por ejemplo, cuando i>1, si el nodo es 7, su padre es 7/2=3; el padre del nodo 9 es 4.
Segundo tipo:
Nodo 6,62 = 12>10, por lo que al nodo 6 no le queda ningún hijo y es un nodo hoja.
El tercer tipo:
El nodo 5,2*5+1>10 no tiene un nodo hijo derecho y el nodo 4 tiene un nodo hijo derecho.
Para obtener más conocimientos relacionados con Python, consulta el vídeo tutorial de Python para seguir aprendiendo.