O conceito de árvore binária
Uma árvore binária é um conjunto finito de nós n (n> = 0). Este conjunto é um conjunto vazio (árvore binária vazia) ou consiste em um nó raiz e duas árvores binárias que não se cruzam, chamadas de nó raiz e a subárvore direita, respectivamente.
Características de árvores binárias
Cada nó possui no máximo duas subárvores, portanto, não há nós com um grau maior que 2 na árvore binária. Cada nó na árvore binária é um objeto, e cada nó de dados tem três ponteiros, a saber, ponteiros para os pais, filho esquerdo e filho direito. Cada nó é conectado um ao outro através de um ponteiro. A relação entre os ponteiros conectados é todo o relacionamento pai-filho.
Definição de nós de árvore binária
O nó da árvore binária é definido da seguinte forma:
A cópia do código é a seguinte:
Struct binarytreenode
{
int m_nvalue;
Binarytreenode* m_pleft;
Binarytreenode* M_PRIGHT;
};
Cinco formas básicas de árvores binárias
Árvore binária vazia
Existe apenas um nó raiz
O nó raiz tem apenas a subárvore esquerda
O nó raiz tem apenas a subárvore certa
O nó raiz tem uma subárvore esquerda e uma direita
Existem apenas dois casos para árvores comuns com três nós: dois ou três. No entanto, como a árvore binária precisa distinguir a esquerda e a direita, ela evoluirá para as cinco formas a seguir:
Árvore binária especial
Árvore inclinada
Como mostrado na segunda e terceira pequenas imagens pequenas na penúltima sub-pictura acima.
Árvore binária completa
Em uma árvore binária, se todos os nós do ramo tiverem subárvores esquerdo e direito, e todas as folhas estiverem na mesma camada, uma árvore binária é chamada de árvore binária completa. Como mostrado na figura abaixo:
Árvore binária completa
Uma árvore completamente binária significa que a última camada está cheia à esquerda, o lado direito pode estar cheio ou não e o restante das camadas está cheio. Uma árvore binária com uma profundidade de K e vários nós de 2^K - 1 é uma árvore binária completa (árvore binária completa). É uma árvore com uma profundidade de K e sem espaço.
As características de uma árvore completamente binária são:
Os nós foliares só podem aparecer nas duas camadas mais baixas.
A folha mais baixa deve estar concentrada em uma posição contínua à esquerda.
Na penúltima camada, se houver nós foliares, eles devem estar em posições contínuas à direita.
Se o grau de nós for 1, o nó terá apenas o filho esquerdo.
Para árvores binárias com a mesma árvore de nós, a árvore binária completa tem a menor profundidade.
Nota: Uma árvore binária completa deve ser uma árvore completamente binária, mas uma árvore completamente binária pode não ser uma árvore binária completa.
O algoritmo é o seguinte:
A cópia do código é a seguinte:
bool is_complete (árvore *raiz)
{
fila q;
árvore *ptr;
// Faz a amplitude de travessia de prioridade (travessia hierárquica) e coloque nós nulos também na fila
q.push (root);
while ((ptr = q.pop ())! = nulo)
{
q.push (ptr-> esquerda);
q.push (ptr-> à direita);
}
// determinar se ainda existem nós que não foram acessados
While (! Q.is_empty ())
{
ptr = q.pop ();
// Se houver nós não nulos que não são acessados, a árvore tem um vazio e é uma árvore binária não completa.
if (null! = ptr)
{
retornar falso;
}
}
retornar true;
}
Propriedades de árvores binárias
Propriedade 1 da árvore binária: existem no máximo 2^(i-1) nós na i -th camada da árvore binária (i> = 1)
Propriedade 2 da árvore binária: Árvore binária com profundidade k tem no máximo 2^k-1 nós (k> = 1)
Estrutura de armazenamento seqüencial de árvores binárias
A estrutura de armazenamento seqüencial de uma árvore binária é usar uma matriz unidimensional para armazenar cada nó na árvore binária, e o local de armazenamento dos nós pode refletir a relação lógica entre nós.
Lista de links binários
Como o método de armazenamento seqüencial não é muito aplicável, devemos considerar a estrutura de armazenamento da cadeia. De acordo com a prática internacional, o armazenamento de árvores binárias geralmente adota uma estrutura de armazenamento em cadeia.
Cada nó de uma árvore binária tem no máximo dois filhos, por isso é uma idéia natural projetar um campo de dados e dois campos de ponteiro para ele. Chamamos uma lista tão vinculada de uma lista binária vinculada.
Travessia de árvores binárias
A árvore binária travessia refere -se a acessar todos os nós na árvore binária em uma certa ordem do nó raiz, para que cada nó seja acessado uma vez e apenas uma vez.
Existem três maneiras de atravessar árvores binárias, como segue:
(1) Travessal de pré-encomenda (DLR), acessando primeiro o nó raiz, depois atravessando a subárvore esquerda e finalmente atravessando a subárvore direita. Raiz abreviada - esquerda - direita.
(2) Traversal na ordem (LDR), primeiro travessia a subárvore esquerda, depois acesse o nó raiz e finalmente travesal a subárvore direita. NOTA ABREVIATIVA: Right-Right à esquerda.
(3) Traversal pós-ordem (LRD), primeiro atravessando a subárvore esquerda, depois atravessando a subárvore direita e finalmente acessando o nó raiz. Raízes esquerda-direita abreviada.
Travessal preâmbulo:
Se a árvore binária estiver vazia, a operação vazia retornará. Caso contrário, primeiro acesse o nó raiz, depois atravesse a subárvore esquerda na ordem anterior e depois atravesse a subárvore direita no pedido anterior.
A ordem de Traversal é: abdhiejcfkg
A cópia do código é a seguinte:
// Traversal preciso
Função pré -encomenda (nó) {
if (! node == null) {
putstr (node.show ()+ "");
pré -encomenda (node.left);
pré -encomenda (node.right);
}
}
Travessal em ordem:
Se a árvore estiver vazia, a operação vazia retornará; caso contrário, ela inicia no nó raiz (observe que o nó raiz não é acessado primeiro) e a subárvore esquerda do nó raiz é percorrida na ordem média, o nó raiz será acessado e, finalmente, o subtraco direito será atravessado na ordem do meio.
A ordem de Traversal é: hdibejafkcg
A cópia do código é a seguinte:
// Use o método recursivo para implementar a travessia de ordem média
função inOrder (nó) {
if (! (node == null)) {
inOrder (node.left); // Adicione à subárvore esquerda primeiro
putstr (node.show ()+ ""); // Adicione ao nó raiz novamente
inOrder (Node.right); // Último acesso à subárvore direita
}
}
Traversal de pós-ordem:
Se a árvore estiver vazia, a operação vazia retornará. Caso contrário, as subáridas esquerda e direita são atravessadas da esquerda para a direita para acessar as subárvores esquerda e direita e, finalmente, acessar o nó raiz.
A ordem de Traversal é: Hidjebkfgca
A cópia do código é a seguinte:
// Traversal pós-ordem
Função Postrome (nó) {
if (! node == null) {
PROTORMA (NODE.LEFT);
PROTORMA (NODE.right);
putstr (node.show ()+ "");
}
}
Implementar árvore de pesquisa binária
A árvore de pesquisa binária (BST) é composta de nós, então definimos um objeto de nó do nó da seguinte forma:
A cópia do código é a seguinte:
Nó da função (dados, esquerda, direita) {
this.data = dados;
this.left = esquerda; // salvar o link do nó esquerdo
this.right = certo;
this.show = show;
}
function show () {
Retorne this.data; // mostra dados salvos no nó
}
Encontre valores máximos e mínimos
Encontrar os valores mínimo e máximo no BST é muito simples, porque os valores menores estão sempre no nó da criança esquerda e, procurando o valor mínimo no BST, apenas atravesse a infância esquerda até que o último nó seja encontrado
Encontre o valor mínimo
A cópia do código é a seguinte:
function getmin () {
Var Current = this.root;
while (! (current.left == null)) {
atual = current.left;
}
return Current.data;
}
Este método atravessa um a um ao longo da subárvore esquerda do BST até atravessar o nó mais à esquerda do BST, que é definido como:
A cópia do código é a seguinte:
current.left = null;
Neste momento, o valor salvo no nó atual é o valor mínimo
Encontre o valor máximo
Encontrar o valor máximo no BST requer apenas atravessar a subárvore correta até que o último nó seja encontrado, e o valor salvo nesse nó é o valor máximo.
A cópia do código é a seguinte:
função getMax () {
Var Current = this.root;
while (! (Current.right == null)) {
atual = current.right;
}
return Current.data;
}