Almacenamiento del árbol de claves

Los árboles de claves generalmente se almacenan de dos maneras:

(1) Representación de árbol con doble enlace

Si están representados por los hermanos secundarios del árbol, entonces cada uno nodo Contiene 3 dominios.

A: campo de símbolo: almacena un carácter de la palabra clave; B: campo hijo: almacena un puntero a la raíz del primer subárbol. El campo hijo del nodo hoja apunta al puntero del registro de palabras clave; C: campo hermano: almacena el puntero al hermano derecho. El árbol clave en este momento también se llama árbol de doble cadena. El código clave es el siguiente:

//Representación de almacenamiento del árbol de doble enlace

typedef struct DULNode{

char símbolo //Campo de carácter de nodo<; /p>

struct DULNode *son, *brother; //son apunta al nodo raíz del subárbol, brother apunta al nodo hermano derecho.

}DULNode, *DLTree;

(2) Representación de lista multienlazada

Si el árbol clave está representado por una lista multienlazada de un árbol, cada nodo del árbol debe contener d (d es la base del carácter clave Por ejemplo: el conjunto de caracteres se compone de letras mayúsculas en inglés. Cuando, entonces d = 26 1 = 27) dominio de puntero, el árbol de claves en este momento también se llama árbol Trie. Hay dos tipos de nodos en el árbol Trie:

(1) Nodo de rama: contiene d campos de puntero y el número entero n registra el número de campos de puntero no nulos (opcional).

(2) Nodo hoja: contiene dominio de palabras clave (palabra clave completa, opcional), nombre de dominio de datos adicionales (opcional).

En la implementación real, generalmente solo contiene los campos del puntero d. Según el árbol Trie estándar, se puede comprimir: si cada nodo en la ruta desde un nodo en el árbol clave hasta un nodo hoja tiene solo un hijo, entonces todos los nodos en la ruta se pueden comprimir en un nodo hoja.