Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Este artículo comenzará con los conceptos relacionados con los árboles y los árboles binarios para ayudarnos a aprender más sobre los árboles binarios.

🌈个人主页：es el camarero
🌈C语言笔记专栏：notas de lenguaje c
🌈C++笔记专栏： notas de c ++
🌈初阶数据结构笔记专栏： Notas elementales sobre la estructura de datos.

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

1. Concepto y estructura del árbol.

El árbol es una estructura de datos no lineal, que se compone den(n>=0)Los nodos limitados forman un conjunto con una relación jerárquica. Sin embargo, el árbol tiene poco valor en la práctica, pero el árbol binario tiene mayor valor práctico (la razón por la que este conjunto se llama árbol es que tiene la raíz hacia arriba y las hojas). boca abajo. Parece mucho un árbol).

• Hay un nodo especial llamado nodo raíz. El nodo raíz no tiene nodos predecesores.
• Excepto el nodo raíz, los nodos restantes se dividen enM(M>0)conjuntos disjuntosT1、T2、....、Tm, cada conjunto de los cualesTi(1<=i<=m) Es otro subárbol con una estructura similar a la de un árbol. El nodo raíz de cada subárbol tiene un solo predecesor y puede tener 0 o más sucesores.
• Los árboles se definen de forma recursiva y, al mismo tiempo, se debe tener cuidado.en estructura de árbolNo puede haber intersección entre subárboles, de lo contrario no será una estructura de árbol.

1.1 Conceptos relacionados de árboles

• Grado de nodo: El número de subárboles contenidos en un nodo se denomina grado del nodo, como se muestra en la figura anterior: A es 6;
• Nodo hoja o nodo terminal: Los nodos con grado 0 se denominan nodos hoja. Como se muestra en la figura anterior: Los nodos como B, C, H, I... son nodos hoja.
• Nodo no terminal o nodo ramal: Un nodo cuyo grado no es 0; como se muestra en la figura anterior: nodos como D, E, F, G... son nodos de rama.
• Nodo padre o nodo padre: Si un nodo contiene nodos secundarios, entonces este nodo se denomina nodo padre de su nodo hijo. Como se muestra en la figura anterior: A es el nodo padre de B;
• nodo hijo o nodo hijo: El nodo raíz del subárbol contenido por un nodo se denomina nodo hijo del nodo. Como se muestra en la figura anterior: B es el nodo hijo de A;
• Nodo hermano: Los nodos con el mismo nodo padre se denominan nodos hermanos, como se muestra arriba: B y C son nodos hermanos.
• grado de arbol: En un árbol, el grado del nodo más grande se llama grado del árbol como se muestra arriba: el grado del árbol es 6;
• Nivel de nodo: A partir de la definición de raíz, la raíz es el primer nivel, los nodos secundarios de la raíz son el segundo nivel, y así sucesivamente.
• altura o profundidad del árbol: El nivel máximo de nodos en el árbol como se muestra arriba: la altura del árbol es 4;
• nodo primo: Los nodos cuyos padres están en el mismo nivel son primos entre sí, como se muestra en la figura anterior: H e I son nodos hermanos entre sí.
• Ancestro del nodo: Todos los nodos en las ramas desde la raíz hasta el nodo como se muestra en la figura anterior: A es el antepasado de todos los nodos;
• descendientes : Cualquier nodo en el subárbol con raíz en un determinado nodo se denomina descendiente de ese nodo.Como se muestra arriba: todos los nodos son descendientes de A
• bosque: Un conjunto de m (m>0) árboles disjuntos se llama bosque.

2. Representación de almacenamiento del árbol.

Dado que la estructura de árbol es más compleja que la tabla lineal, el método de almacenamiento es más engorroso. Es necesario guardar tanto el rango de valores como la relación entre los nodos.

A continuación se muestran varios métodos basados ​​en conocimientos previos:

• Cada niño tiene una dirección y puede almacenar datos a través de una matriz de punteros (el espacio es fijo y existen costos y problemas de espacio al solicitar un nuevo espacio)
• Para la optimización del primer método, la matriz de punteros se utiliza como tabla de secuencia para almacenar elementos secundarios, lo que resuelve el problema del espacio fijo.
• Solución recomendada de uso común: método del hijo izquierdo y del hermano derecho (el hermano mayor toma al segundo hijo y el segundo hijo toma al tercer hijo, por lo que ambos padres no necesitan estar cansados)

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

Por supuesto, los métodos anteriores no están limitados, y también hay expresiones principales, expresiones secundarias, expresiones primarias secundarias y expresiones de hermanos secundarios, etc.Aquí entenderemos brevemente los más utilizados.representación del hermano menor

3. Concepto de árbol binario

Un árbol binario es un conjunto finito de nodos. Este conjunto puede tener dos situaciones:

1. arbol vacio
2. Consta de un nodo raíz más dos árboles binarios llamados subárbol izquierdo y subárbol derecho (el subárbol puede ser un árbol vacío)

De la figura se pueden sacar dos conclusiones.:

1. No hay ningún nodo con grado mayor que 2 en un árbol binario

2. Los subárboles de un árbol binario se pueden dividir en subárboles izquierdo y derecho y el orden no se puede invertir, por lo que el árbol binario es un árbol ordenado.

Aviso: Para cualquier árbol binario, se compone de las siguientes situaciones (La situación del árbol vacío es más fácil de olvidar)

3.1 Árbol binario en la realidad (tienes que inclinarte varias veces cuando lo ves)

4. Árbol binario especial

• árbol binario completo :Un árbol binario es un árbol binario completo si el número de nodos en cada capa alcanza el máximo. En otras palabras, el nivel de un árbol binario es K y el número total de nodos es 2.^K-1, entonces es un árbol binario completo
• árbol binario completo : Un árbol binario completo es una estructura de datos muy eficiente. Un árbol binario completo se deriva de un árbol binario completo. Para un árbol binario con altura K y n nodos, se llama árbol binario completo si y solo si cada nodo se corresponde uno a uno con los nodos numerados del 1 al n en el árbol binario completo con altura K.

Para resumir brevemente:

• Cada nivel de un árbol binario completo está lleno.

• Si la altura de un árbol binario completo es n, entonces los primeros n-1 niveles están llenos, pero el último nivel puede no estar lleno.Pero debe ser continuo de izquierda a derecha.

• Un árbol binario completo es una estructura de datos muy eficiente y un árbol binario completo es un tipo especial de árbol binario completo.

• Un árbol binario completo es una condición necesaria y suficiente para un árbol binario completo.

4.1 Situaciones que no pertenecen a un árbol binario completo

Este es un árbol binario ordinario, que no es continuo de izquierda a derecha.

5. Estructura de almacenamiento del árbol binario.

Los árboles binarios generalmente se pueden almacenar en dos estructuras, una es una estructura secuencial y la otra es una estructura en cadena.

5.1 Almacenamiento secuencial

El almacenamiento de estructura secuencial consiste en utilizar matrices para almacenar,Generalmente, las matrices sólo son adecuadas para representar árboles binarios completos. , porque si el árbol binario no está lleno, se desperdiciará espacio. En realidad, solo el montón utilizará matrices para el almacenamiento. El almacenamiento secuencial de árboles binarios es físicamente una matriz y lógicamente un árbol binario. Para resolver la siguiente pregunta, necesitamos usar la combinación de una matriz física y un árbol binario lógicamente para resolver una pregunta.

5.2 La relación regular de subíndices entre los nodos padre e hijo (importante)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(No diferencia entre niños de izquierda y derecha)

• En cuanto al tercer punto, basado en razonamientos personales,leftchildEl subíndice se divide enleftchild- 1y1,paraleftchild-1paraparentsubíndice dos veces, para(child - 1) / 2El operadorleftchildSácalo como1Parcialmente dividido por 2, el número entero es 0,leftchild -1Parte de esto puede verse comoleftchild,yrightchild与leftchild相差1,porquerightchild = leftchild - 1y por arribaleftchild - 1 ~= leftchild, se puede inferir querightchild = leftchild(在进行/2运算，取整数情况下)

5.3 Almacenamiento en cadena

La estructura de almacenamiento vinculada de un árbol binario significa que se utiliza una lista vinculada para representar un árbol binario, es decir, una cadena para indicar la relación lógica de los elementos. El método habitual es que cada nodo en la lista vinculada consta de tres campos, el campo de datos y los campos de puntero izquierdo y derecho. Los punteros izquierdo y derecho se utilizan para proporcionar las direcciones de almacenamiento de los puntos de enlace donde están el hijo izquierdo y el hijo derecho. del nodo se ubican respectivamente.Las estructuras de cadena se dividen en cadenas binarias y cadenas trifurcadas. En la actualidad, generalmente usamos cadenas binarias en nuestros estudios. Más adelante, cuando aprendamos estructuras de datos de alto orden, como los árboles rojo-negro, se utilizarán cadenas trifurcadas.

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
        struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 Resumen

El almacenamiento de estructura secuencial se almacena a través de matrices.Generalmente, las matrices solo son adecuadas para árboles binarios completos. Los árboles binarios incompletos no son adecuados para el almacenamiento de estructuras de matrices. Los árboles binarios ordinarios solo son adecuados para el almacenamiento de estructuras en cadena. . Pero en realidad, las matrices solo se usan para almacenamiento cuando se usan montones, y la mayoría de ellos se almacenan a través de estructuras en cadena.

la razón es:

1. En primer lugar, debemos saber que el árbol binario tiene su propia estructura lógica especial, que es diferente de otras estructuras de datos y es adecuado para agregar, eliminar, verificar y modificar datos del montón, porque el espacio abierto consume mucho espacio. la lógica es más compleja.Si se utiliza una estructura tan compleja para almacenar datos, no deja de tener mucho valor. , sería mejor utilizar una tabla secuencial para almacenar datos desde el principio. Al mismo tiempo, en términos generales, la estructura de un árbol binario es recursiva y es más problemático implementarla de forma no recursiva.
2. La densidad de elementos de almacenamiento en un árbol binario ordinario puede ser muy baja y la estructura de almacenamiento continuo provocará una gran pérdida de espacio.
3. El montón se ordena según el "atributo del montón", que determina la posición del nodo en el árbol (se explica en la introducción del montón a continuación).

---

Lo anterior es todo el contenido de este artículo. ¡Gracias a todos por leer! Aquí están las notas de Dian Xiaoer sobre estructuras de datos elementales. ¡Espero que le resulten útiles para aprender estructuras de datos elementales!