Supongamos que un árbol binario tiene n nodos de hoja ponderados, entonces la suma de la longitud de la ruta desde el nodo raíz a cada nodo de hoja y el producto del peso del nodo correspondiente se denomina longitud de ruta ponderada WPL (longitud de ruta ponderada) del árbol binario. .

Los mismos nodos hoja construyen diferentes árboles binarios

El árbol binario con la longitud de ruta ponderada mínima se llama árbol de Huffman (también llamado árbol óptimo).

en principio

proceso

Codificación Huffman (codificación de prefijo)

izquierda<raíz<derecha

Una versión mejorada del árbol de clasificación binaria (un árbol de clasificación binaria especial). ¡Intente mantener el árbol lo más corto posible!

¿Cómo saber si un árbol crece normalmente?

Árbol de clasificación binaria con factor de equilibrio <= 1

Equilibrar la profundidad máxima y el número mínimo de nodos de un árbol binario

insertar

prólogo

orden medio

Epílogo

Recorrer línea por línea

Requerir

Para preguntas con pocos nodos

Los pasos principales del algoritmo Prime son: en un gráfico conectado ponderado, V es un conjunto que contiene todos los vértices. U ya es un nodo en el árbol de expansión mínima, comenzando desde cualquier vértice v en el gráfico. ={v}, repita las siguientes operaciones: encuentre una arista con el peso más pequeño entre todas las aristas (u,w)∈E de todas u∈U,w∈V-U, y agregue la arista (u,w) al conjunto de bordes encontrados y agregue el punto w al conjunto U. Cuando U = V, se encuentra el árbol de expansión mínimo.

Primero determine los nodos y seleccione aquellos con los caminos más cortos en orden.

Para preguntas con un número reducido de lados.

Idea básica: liderada por el borde. En un gráfico conectado ponderado, U es el conjunto de todas las aristas, N es el número de vértices y sea SU el conjunto de aristas que ya están en el árbol de expansión mínima. Repita las siguientes operaciones: cada vez seleccione una arista e∈U-SU con el peso más pequeño y una arista que no forme un ciclo con las aristas en SU, y súmela a SU. Cuando el número de aristas en SU ​​es igual a N-1, se encuentra el árbol de expansión mínimo.

El número de nodos sin un puntero derecho es: nodo raíz número de nodos que no son hoja

Excluya los simétricos, cuente el número y asegúrese de que siempre sea menos a la izquierda y más a la derecha o más a la izquierda y menos a la derecha.

El nodo raíz es único.

No hay límite para el número de subárboles, pero no se cruzan entre sí.

naturaleza

árbol binario completo

árbol binario completo

Debe ser un árbol binario completo.

dagendui

pequeño montón de raíces

almacenamiento en montón

Filtro superior

Filtrar hacia abajo

¿Cómo convertir una matriz desordenada en un montón?

dos operaciones

Se puede implementar usando un pequeño montón raíz.

Complejidad: O (NlogN)