Grau da árvore: o número de filhos que uma árvore possui o maior número de nós filhos

Altura do nó: contando de baixo para cima

Nível do nó, profundidade: contando de cima para baixo

Grau do nó: Quantos filhos um nó tem?

Uma árvore com grau m: o grau de cada nó é <=m, e pelo menos um nó tem grau m. Deve ser uma árvore não vazia com pelo menos m 1 nós.

árvore m-ária: o grau de qualquer nó <= m, o grau de todos os nós é permitido <m, pode ser uma árvore vazia

Características: Cada nó possui no máximo duas subárvores, e as subárvores esquerda e direita não podem ser invertidas.

árvore binária completa

árvore binária completa

Árvore de classificação binária

árvore binária balanceada

n0=n2 1

O resto é igual ao anterior

A altura de uma árvore binária completa com n nós é log2(n 1) arredondado para cima e (log2n) 1 arredondado para baixo.

De acordo com o número de nós sendo n, podemos deduzir o número de nós com graus 0, 1 e 2.

Crie uma matriz estática para armazenar a árvore em ordem de cima para baixo, da esquerda para a direita. A estrutura da árvore contém duas variáveis, uma é o valor dos dados e a outra é o valor bool para determinar se o nó está vazio. Durante a inicialização, um loop é necessário para definir cada nó como vazio (o valor bool é verdadeiro)

operar

No armazenamento sequencial de árvores binárias, os números dos nós da árvore binária devem ser combinados com a árvore binária completa, para que as relações lógicas entre os nós possam ser refletidas pelos números armazenados sequencialmente. Só faz sentido que árvores binárias completas sejam armazenadas sequencialmente.

Na pior das hipóteses, uma única árvore com apenas o filho certo requer pelo menos 2 ^ h-1 unidades de armazenamento sequenciais

A estrutura possui três variáveis, uma é o valor e as outras duas são as variáveis ​​de ponteiro filho esquerdo e direito.

Uma lista vinculada de árvore binária com n nós possui um total de n 1 campos de link vazios.

A vantagem é que é muito conveniente encontrar os filhos esquerdo e direito de um nó, mas a desvantagem é que encontrar o nó pai requer percorrer desde o início. O método consiste em definir mais um ponteiro de nó pai na estrutura.

Ao redor da raiz

esquerda raiz direita

raízes esquerda e direita

Inicializar uma fila auxiliar

Deixe o nó raiz entrar na fila

Se a fila não estiver vazia, deixe o nó raiz sair da fila e deixe os filhos esquerdo e direito do nó raiz entrarem na fila (os filhos esquerdo e direito existem)

Repita a etapa 3 até que a fila esteja vazia

O princípio é que o nó raiz pode ser determinado com base nos níveis frontal e traseiro e, em seguida, as subárvores esquerda e direita são divididas de acordo com a ordem intermediária.

Idéia: Existem n 1 domínios de link vazios para n nós. Usamos o domínio de link vazio deste nó para armazenar o predecessor e o sucessor deste nó em cada travessia de sequência. Definir rtag, ltag indica se aponta para filho rag = 1 ou pista rag = 0.

Pista precursora: servida pelo ponteiro do filho esquerdo

Pista do sucessor: servida pelo ponteiro do filho certo

Predecessor em ordem: aponta para o antecessor do nó na travessia em ordem

Modificação dos três algoritmos de travessia Ao visitar um nó, a informação da pista que conecta o nó e o nó predecessor é.

Use um ponteiro pré para registrar o nó predecessor do nó atualmente acessado.

Processamento de rchild e rtag do último nó

Encomende pistas para prestar atenção ao problema do círculo mágico do amor. Quando ltag=0, a subárvore esquerda pode ser informada em pré-ordem.

Procurando um sucessor

Encontre um pioneiro

Encontre um pioneiro

Procurando um sucessor

Encontre um pioneiro

Procurando um sucessor

Como definir

operar

Vantagens e desvantagens: A vantagem é que é fácil encontrar o nó pai, mas encontrar o nó filho requer percorrê-lo desde o início.

Como definir

Existem dois ponteiros na estrutura, um apontando para o filho esquerdo e outro apontando para o irmão direito do filho esquerdo.

Vantagens: você pode usar operações de árvore binária para processar árvores diretamente

Apresente a estrutura de uma árvore binária em lógica física

passagem pela raiz da árvore

Travessia da raiz traseira da árvore

Percurso em nível de árvore

Pré-encomenda de travessia da floresta

travessia em ordem

O peso do nó: um valor com algum significado prático (como a importância do nó)

O comprimento total do caminho de um nó: o produto do comprimento do caminho (número de arestas passadas) da raiz da árvore até o nó e o peso do nó

O comprimento total do caminho da árvore

Em uma árvore binária contendo n nós folha ponderados, a árvore binária com o menor comprimento total de caminho é chamada de árvore de Huffman, também conhecida como árvore binária ótima.

A estrutura da árvore de Huffman

natureza

Codificação de comprimento fixo: cada caractere é representado por comprimento igual de bits binários

Codificação de comprimento variável: permite que diferentes caracteres sejam representados por comprimentos desiguais de bits binários

Codificação de prefixo: se nenhuma codificação for o prefixo de outra codificação, essa codificação será chamada de codificação de prefixo.

A codificação de Huffman é obtida usando uma árvore de Huffman. Cada caractere do conjunto de caracteres é usado como um nó folha, e a frequência de cada caractere é usada como o peso do nó para construir uma árvore de Huffman.

Aplicação: Telégrafo e dados compactados

O conjunto de pesquisa de união é uma estrutura lógica, uma implementação específica de um conjunto. Ele executa apenas duas operações: união e pesquisa. Uma floresta é usada para representar um conjunto, e cada árvore é um subconjunto disjunto.

operar

Estrutura de armazenamento: Representação parental de uma árvore.

Código

Otimização adicional da pesquisa de união