Grado de árbol: la cantidad de hijos que tiene un árbol con la mayor cantidad de nodos secundarios

Altura del nodo: contando de abajo hacia arriba

Nivel de nodo, profundidad: contando de arriba a abajo

Grado de nodo: ¿Cuántos hijos tiene un nodo?

Un árbol de grado m: el grado de cada nodo es <= m, y al menos un nodo tiene grado m. Debe ser un árbol no vacío con al menos m 1 nodos.

Árbol m-ario: el grado de cualquier nodo <= m, el grado de todos los nodos está permitido <m, puede ser un árbol vacío

Características: cada nodo tiene como máximo dos subárboles y los subárboles izquierdo y derecho no se pueden revertir.

árbol binario completo

árbol binario completo

árbol de clasificación binaria

árbol binario equilibrado

n0=n2 1

El resto es igual que arriba.

La altura de un árbol binario completo con n nodos es log2(n 1) redondeado hacia arriba y (log2n) 1 redondeado hacia abajo.

Según que el número de nodos sea n, podemos deducir el número de nodos con grados 0, 1 y 2.

Cree una matriz estática para almacenar el árbol en orden de arriba a abajo, de izquierda a derecha. La estructura del árbol contiene dos variables, una es el valor de los datos y la otra es el valor bool para determinar si el nodo está vacío. Durante la inicialización, se requiere un bucle para configurar cada nodo para que esté vacío (el valor bool es verdadero)

funcionar

En el almacenamiento secuencial de árboles binarios, los números de nodo del árbol binario deben coincidir con el árbol binario completo, de modo que las relaciones lógicas entre los nodos puedan reflejarse en los números almacenados secuencialmente. Sólo tiene sentido que los árboles binarios completos se almacenen secuencialmente.

En el peor de los casos, un solo árbol con solo el hijo correcto requiere al menos 2^h-1 unidades de almacenamiento secuenciales.

La estructura tiene tres variables, una es el valor y las otras dos son las variables de puntero secundario izquierda y derecha.

Una lista enlazada de árbol binario con n nodos tiene un total de n 1 campos de enlace vacíos.

La ventaja es que es muy conveniente encontrar los hijos izquierdo y derecho de un nodo, pero la desventaja es que encontrar el nodo padre requiere atravesarlo desde el principio. El método consiste en establecer un puntero de nodo principal más en la estructura.

alrededor de la raíz

raíz izquierda derecha

raíces izquierda y derecha

Inicializar una cola auxiliar

Deje que el nodo raíz se una a la cola

Si la cola no está vacía, deje que el nodo raíz salga de la cola y permita que los hijos izquierdo y derecho del nodo raíz se unan a la cola (los hijos izquierdo y derecho existen)

Repita el paso 3 hasta que la cola esté vacía.

El principio es que el nodo raíz se puede determinar en función de los niveles delantero y trasero, y luego los subárboles izquierdo y derecho se dividen según el orden medio.

Idea: Hay n 1 dominios de enlace vacíos para n nodos. Usamos el dominio de enlace vacío de este nodo para almacenar el predecesor y el sucesor de este nodo en cada recorrido de secuencia. Establezca rtag, ltag indica si apunta al niño rag=1 o a la pista rag=0.

Pista precursora: servida por el puntero del niño izquierdo

Pista sucesora: servida por el puntero del hijo correcto

Predecesor en orden: apunta al predecesor del nodo en el recorrido en orden

Modificación de los tres algoritmos transversales Al visitar un nodo, la información de pista que conecta el nodo y el nodo predecesor es.

Utilice un puntero previo para registrar el nodo predecesor del nodo al que se accede actualmente.

Procesamiento de rchild y rtag del último nodo

Reserva pistas para prestar atención al problema del círculo mágico del amor. Cuando ltag = 0, el subárbol izquierdo se puede rastrear en preorden.

Buscando un sucesor

Encuentra un pionero

Encuentra un pionero

Buscando un sucesor

Encuentra un pionero

Buscando un sucesor

como definir

funcionar

Ventajas y desventajas: la ventaja es que es fácil encontrar el nodo principal, pero encontrar el nodo secundario requiere recorrerlo desde el principio.

como definir

Hay dos punteros en la estructura, uno que apunta al hijo izquierdo y el otro que apunta al hermano derecho del hijo izquierdo.

Ventajas: puede utilizar operaciones de árbol binario para procesar árboles directamente

Presentar la estructura de un árbol binario en lógica física.

recorrido de la raíz del árbol

Recorrido de la raíz posterior del árbol

Recorrido a nivel de árbol

Preordenar recorrido del bosque.

recorrido en orden

El peso del nodo: un valor con algún significado práctico (como la importancia del nodo)

La longitud total de la ruta de un nodo: el producto de la longitud de la ruta (número de aristas pasadas) desde la raíz del árbol hasta el nodo y el peso del nodo.

La longitud total del camino del árbol.

En un árbol binario que contiene n nodos de hoja ponderados, el árbol binario con la longitud de ruta total más pequeña se denomina árbol de Huffman, también conocido como árbol binario óptimo.

La estructura del árbol de Huffman.

naturaleza

Codificación de longitud fija: cada carácter está representado por bits binarios de igual longitud

Codificación de longitud variable: permite representar diferentes caracteres mediante longitudes desiguales de bits binarios

Codificación de prefijo: si ninguna codificación es el prefijo de otra codificación, dicha codificación se denomina codificación de prefijo.

La codificación de Huffman se obtiene utilizando un árbol de Huffman. Cada carácter del conjunto de caracteres se utiliza como un nodo hoja y la frecuencia de cada carácter se utiliza como el peso del nodo para construir un árbol de Huffman.

Aplicación: Telégrafo y datos comprimidos.

El conjunto de búsqueda de unión es una estructura lógica, una implementación específica de un conjunto. Solo realiza dos operaciones: unión y búsqueda. Se utiliza un bosque para representar un conjunto y cada árbol es un subconjunto disjunto.

funcionar

Estructura de almacenamiento: Representación parental de un árbol.

Código

Mayor optimización de la búsqueda de sindicatos