Compartir tecnología

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

1. Concepto y estructura de árbol.

1.1 El concepto de árbol

el árbol es unno lineal Una estructura de datos, que es un conjunto de relaciones jerárquicas compuestas por n (n>=0) nodos limitados.ManojoSe llama árbol porque parece un árbol al revés, lo que significa que tiene las raíces hacia arriba y las hojas hacia abajo.

• Nodo raíz: el nodo raíz no tiene un nodo predecesor.
• A excepción del nodo raíz, los nodos restantes se dividen en subárboles 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.
• Por lo tanto, el árbol esdefinición recursivade.

1.2 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 4;
• Nodo hoja o nodo terminal: Los nodos con grado 0 se denominan nodos hoja. Como se muestra en la figura anterior: los nodos B, F, G, D y H son nodos hoja.
• Nodo no terminal o nodo ramal: Un nodo cuyo grado no es 0; como se muestra en la figura anterior: los nodos A, C y E 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 4;
• 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 3;
• nodo primo: Los nodos cuyos padres están en el mismo nivel son primos entre sí, como se muestra en la figura anterior: F y G 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: Una colección de m árboles separados se llama bosque;

1.3 Representación de árbol

La estructura de árbol es más complicada que la tabla lineal y es más problemático almacenarla y representarla.Es necesario guardar tanto el rango de valores como la relación entre nodos y nodos.De hecho, existen muchas formas de representar árboles, como por ejemplo:Notación padre, notación hijo, notación padre hijo y notación hermano hijoesperar.

En el proceso de introducción de la siguiente estructura de almacenamiento, tomamos el siguiente árbol como ejemplo.

1.3.1 Representación de los padres

Suponemos que los nodos del árbol están almacenados en un conjunto de espacios continuos y al mismo tiempoEn cada nodo, se adjunta un indicador para indicar la posición de su nodo principal en la lista vinculada. . En otras palabras, además de saber quién es, cada nodo también sabe dónde están sus padres.

Entre ellos, los datos son el campo de datos, que almacena la información de datos del nodo. Y padre es un campo de puntero que almacena los subíndices de los padres del nodo en la matriz.
El siguiente es el código de definición de estructura de nodos para nuestra representación principal.

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;	//树结点的数据类型，目前暂定为整型
/*结点结构*/
typedef struct TreeNode
{
	TElemType data;	//结点数据
	int parent;	//双亲位置
}TreeNode;
/*树结构*/
typedef struct
{
	TreeNode nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Con dicha estructura de almacenamiento, podemos encontrar fácilmente sus nodos principales según el puntero principal del nodo utilizado.La complejidad del tiempo es 0(1) , hasta que el padre sea -1, lo que indica que se ha encontrado la raíz del nodo del árbol. Pero si queremos saber cuáles son los hijos del nodo, lo siento, recorra toda la estructura.

1.3.2 Representación del hermano menor

Hace un momento estudiamos la estructura de almacenamiento del árbol desde la perspectiva de los padres y la perspectiva del niño. ¿Qué pasa si miramos a los hermanos de los nodos del árbol? Por supuesto, para una estructura jerárquica como un árbol, solo estudiamos el. hermanos de los nodos No es posible Después de la observación, encontramos que para cualquier árbol, el primer hijo de su nodo es único si existe, y su hermano derecho también es único si existe. Por lo tanto, configuramos dos punteros, que apuntan al primer hijo del nodo y al hermano derecho del nodo.

/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
	TElemtype data;
	struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;
1
2
3
4
5
6

1.4 Aplicaciones prácticas de los árboles

2. Concepto y estructura del árbol binario.

2.1 Concepto

Un árbol binario es un conjunto finito de nodos, que es:

• o vacío
• Consta de un nodo raíz más dos árboles binarios, también conocidos como subárbol izquierdo y subárbol derecho.

Como se puede ver en la imagen de arriba:

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árbol ordenado

Nota: Cualquier árbol binario se compone de las siguientes situaciones:

2.2 árboles binarios especiales

1. árbol binario completo: un árbol binario,Si el número de nodos en cada capa alcanza el máximo, el árbol binario es un árbol binario completo. . Es decir, si el número de niveles de un árbol binario es K y el número total de nodos es 2^k-1, entonces es un árbol binario completo.
2. árbol binario completo: Un árbol binario completo es una estructura de datos muy eficiente.Los árboles binarios completos se derivan de árboles binarios completos. . Para un árbol binario con n nodos de profundidad K, se llama árbol binario completo si y sólo si cada nodo se corresponde uno a uno con los nodos numerados del 1 al n en el árbol binario completo de profundidad K. tener cuidado deUn árbol binario completo es un tipo especial de árbol binario completo.
   

2.3 Propiedades de los árboles binarios

1. Si se especifica que el número de niveles del nodo raíz es 1, entonces elHay como máximo 2^(i-1) en la i-ésima capa nodos
2. Si se especifica que el número de niveles del nodo raíz es 1, entoncesEl número máximo de nodos de un árbol binario con profundidad h es 2^h-1
3. Para cualquier árbol binario, siEl número de nodos de hoja con grado 0 es n0 y el número de nodos de rama con grado 2 es n2, entonces n0 = n2 +1
4. Si se especifica que el número de niveles del nodo raíz es 1,La profundidad de un árbol binario completo con n nodos, h=log (n+1) (ps: log es base 2, n+1 es logaritmo)
5. Para un árbol binario completo con n nodos, si todos los nodos están numerados comenzando desde 0 en orden de matriz de arriba a abajo, de izquierda a derecha, entonces para el nodo con número de serie i:
   • Si i>0, el número principal del nodo en la posición i: (i-1)/2;, i es el número del nodo raíz, no hay ningún nodo padre
   • Si 2i+1, 2i+1>=n de lo contrario no queda ningún hijo
   • Si 2i+2, 2i+2>=n de lo contrario no existe el hijo adecuado

2.4 Estructura de almacenamiento del árbol binario

Los árboles binarios generalmente se pueden almacenar mediante dos estructuras:Una estructura secuencial, una estructura en cadena.

1. almacenamiento secuencial
   Se utiliza el almacenamiento de estructura secuencial.formaciónPara almacenar, generalmente use una matrizSólo apto para representar árboles binarios completos. , porque no es un árbol binario completo y habrá una pérdida de espacio. En realidad, sólo el montón utiliza matrices para el almacenamiento.El almacenamiento secuencial de árboles binarios es físicamente una matriz y lógicamente un árbol binario.
   2. Almacenamiento en cadena
   La estructura de almacenamiento vinculada de un árbol binario se refiere a,Utilice una lista vinculada para representar un árbol binario , es decir, utilizar cadenas para indicar la relación lógica de 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 ubica respectivamente. ** Las estructuras de cadena se dividen en cadenas binarias y cadenas trifurcadas. Actualmente, generalmente estudiamos cadenas binarias.
   

3. Estructura secuencial e implementación del árbol binario.

Los árboles binarios ordinarios no son adecuados para el almacenamiento en matrices porque puede haber mucho espacio desperdiciado.yLos árboles binarios completos son más adecuados para el almacenamiento de estructuras secuenciales. .En realidad, normalmenteUn montón (un árbol binario) utiliza una serie de estructuras secuenciales para almacenarCabe señalar que el montón aquí y el montón en el espacio de direcciones del proceso virtual del sistema operativo son dos cosas diferentes. Una es una estructura de datos y la otra es una segmentación de área que administra la memoria en el sistema operativo.
Para una implementación y aplicación específicas, consulte:[Estructura de datos] 08. Montón y aplicaciones de montón

4. Estructura de cadena del árbol binario y su implementación.

4.1 recorrido del árbol binario

La forma más sencilla de aprender la estructura de un árbol binario es recorrerla.así llamadoEl recorrido del árbol binario (Traversal) consiste en realizar las operaciones correspondientes en los nodos del árbol binario en secuencia de acuerdo con ciertas reglas, y cada nodo solo se opera una vez. . Las operaciones realizadas al acceder a los nodos dependen del problema específico de la aplicación. El recorrido es una de las operaciones más importantes en un árbol binario y también es la base para otras operaciones en un árbol binario.

4.1.1 Recorrido de reserva

//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

La siguiente figura muestra el proceso recursivo:

4.1.2 Recorrido en orden

//左子树 根 右子树
void InOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

El siguiente es el proceso recursivo:

4.1.3 Recorrido posterior al pedido

//左子树 右子树 根
void PostOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

El siguiente es el proceso recursivo:

4.2.4 Recorrido de orden de nivel

Recorrido de orden de nivel: además del recorrido de orden previo, recorrido de orden y recorrido de orden posterior, el recorrido de orden de nivel también se puede realizar en árboles binarios. Supongamos que el número de nivel del nodo raíz del árbol binario es 1. El recorrido de orden de nivel comienza desde el nodo raíz del árbol binario. Primero, visita el nodo raíz del primer nivel y luego visita los nodos del segundo. nivel de izquierda a derecha, y luego el tercer nivel Los nodos de la capa, y así sucesivamente.El proceso de visitar los nodos del árbol capa por capa de arriba a abajo y de izquierda a derecha es un recorrido por orden de capas.。
Ilustración:

Aquí intervenimos en la cola para realizar un recorrido de preorden del árbol binario.

// 层序遍历
void LevelOrder(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			printf("NULL ");
		}
		else
		{
			printf("%d ", front->val);
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.1 Creación y destrucción de árboles binarios.

Para crear y destruir un árbol binario, usamosRecorrido de árbol binarioPor ejemplo.

//二叉树的创建
struct TreeNode* Creat(char* arr,int n,int* i)
{ 
    if(*i<n&&arr[*i]=='#')
    {
        (*i)++;
        return NULL;
    }
    
    TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));
    newnode->left=NULL;
    newnode->right=NULL;

    newnode->val=arr[(*i)++];
    newnode->left=Creat(arr,n,i);
    newnode->right=Creat(arr,n,i);
    
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    TreeDestroy(root->left);
    TreeDestroy(root->right);
    free(root);
}
1
2
3
4
5
6
7
8
9
10
11

4.3 Otras operaciones en árboles binarios

Todas las siguientes operaciones se llevan a cabo según la idea de recorrido.

// 二叉树节点个数
int TreeSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}
1
2
3
4
5
6
7
8
9

// 二叉树叶子节点个数
int TreeLeafSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树第k层节点个数
int TreeLevelKSize(pTreeNode root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树查找值为x的节点
pTreeNode TreeFind(pTreeNode root, TreeDataType x)
{

	if (root == NULL)
	{
		return NULL;
	}
	//相等就返回
	if (root->val == x)
		return root;
	//找左子树
	pTreeNode left=TreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	//找右子树
	pTreeNode right = TreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	//都没找到
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//二叉树的高度
int TreeHeight(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	int max_left = TreeHeight(root->left) ;
	int max_right = TreeHeight(root->right);
	return max_left > max_right ? max_left + 1 : max_right + 1;
}
1
2
3
4
5
6
7
8
9
10
11

//判断是否是完全二叉树
bool TreeComplete(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36