Sólo hay un nodo raíz

Cuando n>1, los nodos restantes se pueden dividir en m conjuntos finitos disjuntos Ti, cada conjunto es un subárbol de la raíz.

El grado máximo de un nodo se llama grado del árbol.

La suma de los grados de los nodos del árbol = la suma del número de ramas = el número de nodos - 1

árbol binario completo

árbol binario completo

árbol de clasificación binaria

árbol binario equilibrado

El número de nodos hoja en un árbol binario no vacío = el número de nodos con grado 2 1, es decir, n0=n2 1

Hay como máximo 2^(k-1) nodos en el k-ésimo nivel de un árbol binario no vacío.

Un árbol binario de altura h tiene como máximo 2^h-1 nodos.

Un árbol binario puede determinarse de forma única por su secuencia de preorden (o postorden) y su secuencia de orden.

Un árbol binario puede determinarse de forma única por su secuencia jerárquica y su secuencia en orden.

De acuerdo con las secuencias de preorden y postorden del árbol binario, se puede determinar la relación ancestral de algunos nodos: si el preorden es aX y el postorden es Xa, entonces los nodos del conjunto Si son hermanos, el orden debe ser consistente, es decir, el hermano de la izquierda va primero)

Encuentre el primer nodo debajo de la secuencia en orden en el árbol binario de pistas en orden

Encuentre el sucesor del nodo p en el árbol binario de pistas en orden bajo la secuencia en orden

Algoritmo de recorrido en orden para árboles binarios con pistas en orden sin nodo principal

Encuentre el sucesor del nodo en el árbol binario de pistas de pedidos anticipados

Encontrar el sucesor de un nodo en un árbol binario utilizando pistas de postorden

Longitud de ruta ponderada: el producto de la longitud de la ruta (número de bordes pasados) desde la raíz del árbol hasta cualquier nodo y el peso del nodo.

La longitud de la ruta ponderada del árbol: la suma de las longitudes de la ruta ponderada de todos los nodos de las hojas del árbol.

Árbol de Huffman: entre los árboles binarios que contienen n nodos de hoja ponderados, el árbol binario con la longitud de ruta ponderada (WPL) más pequeña también se denomina árbol binario óptimo.

proceso de construcción

Características

Codificación Huffman

Por lo general, la representación principal de un árbol (bosque) se utiliza como estructura de almacenamiento del conjunto de búsqueda de unión, y cada subconjunto está representado por un árbol. Todos los árboles que representan subconjuntos forman un bosque que representa el conjunto completo y se almacenan en la matriz de representación principal. Por lo general, el subíndice del elemento de la matriz se usa para representar el nombre del elemento y el subíndice del nodo raíz se usa para representar el nombre de la subcolección. El nodo principal del nodo raíz es un número negativo.

1) Inicial (S): inicializa cada elemento del conjunto s en un subconjunto con un solo elemento.

2) Unión (S, Raíz1, Raíz2): fusiona el subconjunto Raíz2 del conjunto S en el subconjunto Raíz1. Requerir Root1 y Root2 están separados entre sí; de lo contrario, no se realizará la fusión.

3) Buscar (S, x): busque el subconjunto donde se encuentra el elemento único x en el conjunto s y devuelva el nodo raíz del subconjunto.

Se utiliza un conjunto de espacios continuos para almacenar nodos; al mismo tiempo, se agrega un pseudopuntero a cada nodo para indicar la ubicación de los padres.

Puede obtener rápidamente los nodos principales de un nodo, pero debe recorrer la matriz para encontrar los hijos del nodo.

Conecte los nodos secundarios de cada nodo con una única lista vinculada, n nodos corresponden a n listas vinculadas

Encontrar niños es simple, pero encontrar padres requiere atravesar n listas vinculadas

Usar una lista binaria enlazada como estructura de almacenamiento del árbol

Es fácil encontrar hijos, pero es más problemático encontrar nodos principales (se puede agregar un puntero principal)

Usando una lista binaria enlazada como medio, hay un árbol binario único correspondiente a cada árbol (y viceversa)

Regla de conversión: "Hijo izquierdo, hermano derecho"

De manera similar a la conversión anterior, cada árbol se convierte primero en un árbol binario y luego la raíz del enésimo árbol se considera como el hermano derecho de la raíz del enésimo árbol.

Primero el recorrido de la raíz.

recorrido de la raíz posterior

recorrido de nivel

recorrido de preorden

recorrido en orden