Compartilhamento de tecnologia

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

Este artigo começará com os conceitos relacionados a árvores e árvores binárias para nos ajudar a aprender mais sobre árvores binárias.

🌈个人主页：É o garçom
🌈C语言笔记专栏：Notas da linguagem C
🌈C++笔记专栏： Notas C++
🌈初阶数据结构笔记专栏： Notas elementares sobre estrutura de dados

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

1. Conceito e estrutura da árvore

Árvore é uma estrutura de dados não linear, composta porn(n>=0)Nós limitados formam um conjunto com relacionamento hierárquico Porém, a árvore tem pouco valor na prática, mas a árvore binária tem maior valor prático (o motivo pelo qual esse conjunto é chamado de árvore é que ele tem a raiz voltada para cima e as folhas. voltado para baixo. Parece muito com uma árvore)

• Existe um nó especial chamado nó raiz. O nó raiz não possui nós predecessores.
• Com exceção do nó raiz, os nós restantes são divididos emM(M>0)conjuntos disjuntosT1、T2、....、Tm, cada conjunto dos quaisTi(1<=i<=m) É outra subárvore 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.
• As árvores são definidas recursivamente e, ao mesmo tempo, é preciso tomar cuidado.na estrutura da árvoreNão pode haver interseção entre subárvores, caso contrário não será uma estrutura em árvore

1.1 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 é 6;
• Nó folha ou nó terminal: Nós com grau 0 são chamados de nós folha. Conforme mostrado na figura acima: Nós como B, C, H, I... são nós folha.
• Nó não terminal ou nó de ramificação: Um nó cujo grau não é 0 Como mostrado na figura acima: nós como D, E, F, G... 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 é 6;
• Nível do nó: A partir da definição da raiz, a raiz é o primeiro nível, os nós filhos da raiz são o segundo 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 é 4;
• nó primo: Nós cujos pais estão no mesmo nível são primos um do outro conforme mostrado na figura acima: H e I 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: Um conjunto de m (m>0) árvores disjuntas é chamado de floresta.

2. Representação de armazenamento da árvore

Como a estrutura em árvore é mais complexa que a tabela linear, o método de armazenamento é mais complicado. É necessário salvar tanto o intervalo de valores quanto o relacionamento entre os nós.

Aqui estão vários métodos baseados em conhecimentos prévios:

• Cada criança tem um endereço e pode armazenar dados por meio de uma matriz de ponteiros (o espaço é fixo e há custos e problemas de espaço ao solicitar um novo espaço)
• Para a otimização do primeiro método, o array de ponteiros é utilizado como tabela de sequência para armazenar filhos, o que resolve o problema de espaço fixo.
• Solução comumente usada recomendada: método do filho esquerdo e do irmão direito (o irmão mais velho fica com o segundo filho e o segundo filho fica com o terceiro filho, para que ambos os pais não precisem se cansar)

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

Claro, os métodos acima não são limitados, e também existem expressões pai, expressões filho, expressões pai filho e expressões irmão filho, etc.Aqui entenderemos brevemente os mais comumente usadosrepresentação do irmão menor

3. Conceito de árvore binária

Uma árvore binária é um conjunto finito de nós. Este conjunto pode ter duas situações:

1. árvore vazia
2. Consiste em um nó raiz mais duas árvores binárias chamadas subárvore esquerda e subárvore direita (a subárvore pode ser uma árvore vazia)

Duas conclusões podem ser tiradas da figura:

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, portanto a árvore binária é uma árvore ordenada.

Perceber: Para qualquer árvore binária, ela é composta pelas seguintes situações (A situação da árvore vazia é mais fácil de esquecer)

3.1 Árvore binária na realidade (você tem que se curvar várias vezes ao vê-la)

4. Árvore binária especial

• árvore binária completa :Uma árvore binária é uma árvore binária completa se o número de nós em cada camada atingir o máximo. Em outras palavras, o nível de uma árvore binária é K e o número total de nós é 2^E-1, então é uma árvore binária completa
• árvore binária completa : Uma árvore binária completa é uma estrutura de dados muito eficiente. Uma árvore binária completa é derivada de uma árvore binária completa. Para uma árvore binária com altura K e n nós, ela é chamada de árvore binária completa se e somente se cada nó corresponde um a um com os nós numerados de 1 a n na árvore binária completa com altura K.

Para resumir brevemente:

• Cada nível de uma árvore binária completa está cheio

• Se a altura de uma árvore binária completa for n, então os primeiros n-1 níveis estão cheios, mas o último nível pode não estar cheio.Mas deve ser contínuo da esquerda para a direita

• Uma árvore binária completa é uma estrutura de dados muito eficiente, e uma árvore binária completa é um tipo especial de árvore binária completa.

• Uma árvore binária completa é uma condição necessária e suficiente para uma árvore binária completa

4.1 Situações que não pertencem a uma árvore binária completa

Esta é uma árvore binária comum, que não é contínua da esquerda para a direita.

5. Estrutura de armazenamento da árvore binária

As árvores binárias geralmente podem ser armazenadas em duas estruturas, uma é uma estrutura sequencial e a outra é uma estrutura em cadeia.

5.1 Armazenamento sequencial

O armazenamento de estrutura sequencial consiste em usar arrays para armazenar,Geralmente, os arrays são adequados apenas para representar árvores binárias completas. , porque se a árvore binária não estiver cheia, haverá desperdício de espaço. Na realidade, apenas o heap usará arrays para armazenamento. O armazenamento sequencial de árvores binárias é fisicamente um array e logicamente uma árvore binária. Para resolver a próxima questão, precisamos usar a combinação de fisicamente um array e logicamente uma árvore binária para resolver uma questão.

5.2 O relacionamento regular de subscritos entre nós pai e filho (importante)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(Não diferencia entre filhos da esquerda e da direita)

• Em relação ao terceiro ponto, com base no raciocínio pessoal,leftchildO subscrito é dividido emleftchild- 1e1,paraleftchild-1paraparentsubscrito duas vezes, para(child - 1) / 2O operador iráleftchildRetire como1Parcialmente dividido por 2, o número inteiro é 0,leftchild -1Parte disso pode ser vista comoleftchild,erightchild与leftchild相差1,porquerightchild = leftchild - 1e através de cimaleftchild - 1 ~= leftchild, pode-se inferir querightchild = leftchild(在进行/2运算，取整数情况下)

5.3 Armazenamento em cadeia

A estrutura de armazenamento vinculada de uma árvore binária significa que uma lista vinculada é usada para representar uma árvore binária, ou seja, uma cadeia é usada 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 do link aponta onde o filho esquerdo e o filho direito. do nó estão localizados respectivamente.As estruturas de cadeia são divididas em cadeias binárias e cadeias trifurcadas. Atualmente, geralmente usamos cadeias binárias em nossos estudos. Mais tarde, quando aprendermos estruturas de dados de alta ordem, como árvores vermelhas e pretas, serão usadas cadeias 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 Resumo

O armazenamento de estrutura sequencial é armazenado por meio de arrays.Geralmente, os arrays são adequados apenas para árvores binárias completas. Árvores binárias não completas não são adequadas para armazenamento de estruturas de array. . Mas, na realidade, os arrays são usados ​​para armazenamento apenas quando heaps são usados, e a maioria deles é armazenada por meio de estruturas em cadeia.

a razão é:

1. Em primeiro lugar, precisamos saber que a árvore binária possui sua própria estrutura lógica especial. É diferente de outras estruturas de dados e é adequada para adicionar, excluir, verificar e modificar dados heap, pois o espaço aberto consome muito espaço e. a lógica é mais complexa.Se uma estrutura tão complexa for usada para armazenar dados, ela terá muito valor. , seria melhor usar uma tabela sequencial para armazenar dados desde o início. Ao mesmo tempo, de modo geral, a estrutura de uma árvore binária é recursiva e é mais difícil implementá-la de forma não recursiva.
2. A densidade dos elementos de armazenamento em uma árvore binária comum pode ser muito baixa e a estrutura de armazenamento contínua causará muito desperdício de espaço.
3. O heap é classificado de acordo com o "atributo heap", que determina a posição do nó na árvore (explicado na introdução do heap abaixo)

---

O texto acima é todo o conteúdo deste artigo. Obrigado a todos pela leitura! Aqui estão as notas de Dian Xiaoer sobre estruturas de dados elementares. Espero que sejam úteis para você no aprendizado de estruturas de dados elementares!