Compartilhamento de tecnologia

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

1. Conceito e estrutura de árvore

1.1 O conceito de árvore

árvore é umanão linear Uma estrutura de dados, que é um conjunto de relacionamentos hierárquicos compostos por n (n>=0) nós limitados.PacoteÉ chamada de árvore porque se parece com uma árvore de cabeça para baixo, o que significa que tem as raízes apontando para cima e as folhas apontando para baixo.

• Nó raiz: O nó raiz não possui nó predecessor.
• Com exceção do nó raiz, os demais nós são divididos em subárvores com estrutura semelhante à de uma árvore. O nó raiz de cada subárvore possui um e apenas um predecessor e pode ter 0 ou mais sucessores.
• Portanto, a árvore édefinição recursivade.

1.2 Conceitos relacionados de árvores

• Grau do nó: O número de subárvores contidas em um nó é chamado de grau do nó conforme mostrado na figura acima: A's é 4;
• Nó folha ou nó terminal: Nós com grau 0 são chamados de nós folha Conforme mostrado na figura acima: Os nós B, F, G, D e H são nós folha;
• Nó não terminal ou nó de ramificação: Um nó cujo grau não é 0 Conforme mostrado na figura acima: os nós A, C e E são nós ramificados;
• Nó pai ou nó pai: Se um nó contém nós filhos, então esse nó é chamado de nó pai de seu nó filho. Conforme mostrado na figura acima: A é o nó pai de B;
• nó filho ou nó filho: O nó raiz da subárvore contida por um nó é chamado de nó filho do nó. Conforme mostrado na figura acima: B é o nó filho de A;
• Nó irmão: Nós com o mesmo nó pai são chamados de nós irmãos, conforme mostrado acima: B e C são nós irmãos;
• grau de árvore: Em uma árvore, o grau do maior nó é chamado de grau da árvore conforme mostrado acima: o grau da árvore é 4;
• Nível do nó: A partir da definição da raiz, a raiz é o 1º nível, os nós filhos da raiz são o 2º nível e assim por diante;
• altura ou profundidade da árvore: O nível máximo de nós na árvore conforme mostrado acima: a altura da árvore é 3;
• nó primo: Nós cujos pais estão no mesmo nível são primos um do outro conforme mostrado na figura acima: F e G são nós irmãos um do outro;
• Ancestral do nó: Todos os nós nas ramificações da raiz ao nó conforme mostrado na figura acima: A é o ancestral de todos os nós;
• descendentes : Qualquer nó na subárvore com raiz em um determinado nó é chamado de descendente desse nó.Como mostrado acima: todos os nós são descendentes de A
• floresta: Uma coleção de m árvores disjuntas é chamada de floresta;

1.3 Representação em árvore

A estrutura em árvore é mais complicada do que a tabela linear e é mais difícil armazená-la e representá-la.É necessário salvar tanto a faixa de valores quanto o relacionamento entre nós e nós., na verdade, existem muitas maneiras de representar árvores, como:Notação pai, notação filho, notação pai filho e notação irmão filhoespere.

No processo de introdução da seguinte estrutura de armazenamento, tomamos a árvore a seguir como exemplo.

1.3.1 Representação dos pais

Assumimos que os nós da árvore são armazenados em um conjunto de espaços contínuos e, ao mesmo tempo,Em cada nó, um indicador é anexado para indicar a posição do seu nó pai na lista vinculada. . Ou seja, além de saber quem é, cada nó também sabe onde estão seus pais.

Entre eles, data é o campo de dados, que armazena as informações de dados do nó. E parent é um campo de ponteiro que armazena os subscritos dos pais do nó na matriz.
A seguir está o código de definição da estrutura do nó para nossa representação pai.

/*树的双亲表示法结点结构定义*/
#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

Com essa estrutura de armazenamento, podemos encontrar facilmente seus nós pais de acordo com o ponteiro pai do nó usado.A complexidade do tempo é 0 (1) , até que parent seja -1, indicando que a raiz do nó da árvore foi encontrada. Mas se quisermos saber quais são os filhos do nó, desculpe, percorra toda a estrutura.

1.3.2 Representação do irmão menor

Há pouco estudamos a estrutura de armazenamento da árvore da perspectiva dos pais e da perspectiva da criança. E se olharmos para os nós irmãos da árvore. É claro que, para uma estrutura hierárquica como uma árvore, estudamos apenas os nós da árvore. irmãos dos nós Não é possível Após observação, descobrimos que para qualquer árvore, o primeiro filho de seu nó é único se existir, e seu irmão direito também é único se existir. Portanto, definimos dois ponteiros, apontando para o primeiro filho do nó e para o irmão direito do nó.

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

1.4 Aplicações práticas de árvores

2. Conceito e estrutura de árvore binária

2.1 Conceito

Uma árvore binária é um conjunto finito de nós, que é:

• ou vazio
• Consiste em um nó raiz mais duas árvores binárias, também conhecidas como subárvore esquerda e subárvore direita.

Como pode ser visto na imagem acima:

1. Não existe nenhum nó com grau maior que 2 em uma árvore binária
2. As subárvores de uma árvore binária podem ser divididas em subárvores esquerda e direita, e a ordem não pode ser invertida, então a árvore binária éárvore ordenada

Nota: Qualquer árvore binária é composta pelas seguintes situações:

2.2 Árvores binárias especiais

1. árvore binária completa: uma árvore binária,Se o número de nós em cada camada atingir o máximo, a árvore binária será uma árvore binária completa. . Ou seja, se o número de níveis de uma árvore binária for K e o número total de nós for 2^k-1, então é uma árvore binária completa.
2. árvore binária completa: Uma árvore binária completa é uma estrutura de dados muito eficiente.Árvores binárias completas são derivadas de árvores binárias completas . Para uma árvore binária com profundidade K e n nós, ela é chamada de árvore binária completa se e somente se cada nó corresponder um a um aos nós numerados de 1 a n na árvore binária completa com profundidade K. Para ter cuidadoUma árvore binária completa é um tipo especial de árvore binária completa.
   

2.3 Propriedades de árvores binárias

1. Se o número de níveis do nó raiz for especificado como 1, então oExistem no máximo 2 ^ (i-1) na i-ésima camada nós
2. Se o número de níveis do nó raiz for especificado como 1, entãoO número máximo de nós de uma árvore binária com profundidade h é 2 ^ h-1
3. Para qualquer árvore binária, seO número de nós folha com grau 0 é n0, e o número de nós ramificados com grau 2 é n2, então n0=n2 +1
4. Se o número de níveis do nó raiz for especificado como 1,A profundidade de uma árvore binária completa com n nós, h=log (n+1) (ps: log é base 2, n+1 é logaritmo)
5. Para uma árvore binária completa com n nós, se todos os nós forem numerados começando em 0 na ordem do array de cima para baixo, da esquerda para a direita, então para o nó com número de série i:
   • Se i>0, o número pai do nó na posição i: (i-1)/2;, i é o número do nó raiz, não há nó pai
   • Se 2i+1, 2i+1>=n caso contrário não há filho esquerdo
   • Se 2i+2, 2i+2>=n caso contrário não existe filho certo

2.4 Estrutura de armazenamento da árvore binária

As árvores binárias geralmente podem ser armazenadas usando duas estruturas:Uma estrutura sequencial, uma estrutura em cadeia.

1. armazenamento sequencial
   O armazenamento de estrutura sequencial deve usarvariedadePara armazenar, geralmente use um arrayAdequado apenas para representar árvores binárias completas , porque não é uma árvore binária completa e haverá desperdício de espaço. Na realidade, apenas o heap usa arrays para armazenamento.O armazenamento sequencial de árvores binárias é fisicamente um array e logicamente uma árvore binária.
   2. Armazenamento em cadeia
   A estrutura de armazenamento vinculada de uma árvore binária refere-se a,Use uma lista vinculada para representar uma árvore binária , isto é, usando cadeias para indicar o relacionamento lógico dos elementos. **O método usual é que cada nó na lista vinculada consiste em três campos, o campo de dados e os campos de ponteiro esquerdo e direito. Os ponteiros esquerdo e direito são usados ​​para fornecer os endereços de armazenamento dos pontos de link onde o filho esquerdo e. filho direito do nó estão localizados respectivamente. **As estruturas de cadeia são divididas em cadeias binárias e cadeias trifurcadas. Atualmente, geralmente estudamos cadeias binárias.
   

3. Estrutura sequencial e implementação de árvore binária

Árvores binárias comuns não são adequadas para armazenamento em arrays porque pode haver muito espaço desperdiçado.eÁrvores binárias completas são mais adequadas para armazenamento de estrutura sequencial .Na realidade, normalmenteUm heap (uma árvore binária) usa um array de estruturas sequenciais para armazenar, deve-se notar que o heap aqui e o heap no espaço de endereço do processo virtual do sistema operacional são duas coisas diferentes. Uma é uma estrutura de dados e a outra é uma segmentação de área que gerencia a memória no sistema operacional.
Para implementação e aplicação específicas, consulte:[Estrutura de dados] 08. Aplicativos heap e heap

4. Estrutura da cadeia da árvore binária e sua implementação

4.1 Travessia de árvore binária

A maneira mais simples de aprender uma estrutura de árvore binária é atravessá-la.assim chamadoA travessia da árvore binária (Traversal) consiste em realizar operações correspondentes nos nós da árvore binária em sequência de acordo com certas regras, e cada nó é operado apenas uma vez . As operações realizadas ao acessar os nós dependem do problema específico da aplicação. Traversal é uma das operações mais importantes em uma árvore binária e também é a base para outras operações em uma árvore binária.

4.1.1 Travessia de pré-encomenda

//根 左子树 右子树
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

A figura abaixo mostra o processo recursivo:

4.1.2 Percurso em ordem

//左子树 根 右子树
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

O seguinte é o processo recursivo:

4.1.3 Travessia pós-ordem

//左子树 右子树 根
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

O seguinte é o processo recursivo:

4.2.4 Percurso de ordem de nível

Travessia de ordem de nível: além da travessia de pré-ordem, travessia em ordem e travessia de pós-ordem, a travessia de ordem de nível também pode ser executada em árvores binárias. Suponha que o número do nível do nó raiz da árvore binária seja 1. A travessia de ordem de nível começa no nó raiz da árvore binária. Primeiro, ele visita o nó raiz do primeiro nível e, em seguida, visita os nós do segundo. nível da esquerda para a direita e, em seguida, o terceiro nível Os nós da camada e assim por diante,O processo de visitar os nós da árvore, camada por camada, de cima para baixo e da esquerda para a direita, é uma travessia em ordem de camada.。
Ilustração:

Aqui intervimos na fila para realizar a travessia de pré-ordem da árvore binária.

// 层序遍历
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 Criação e destruição de árvores binárias

Para criar e destruir uma árvore binária, usamosTravessia de árvore bináriaPor exemplo.

//二叉树的创建
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 Outras operações em árvores binárias

As operações a seguir são todas realizadas de acordo com a ideia de travessia.

// 二叉树节点个数
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