Suponha que uma árvore binária tenha n nós folha ponderados, então a soma do comprimento do caminho do nó raiz para cada nó folha e o produto do peso do nó correspondente é chamada de comprimento do caminho ponderado WPL (comprimento do caminho ponderado) da árvore binária .

Os mesmos nós folha constroem diferentes árvores binárias

A árvore binária com o comprimento de caminho mínimo ponderado é chamada de árvore de Huffman (também chamada de árvore ótima).

em princípio

processo

Codificação Huffman (codificação de prefixo)

esquerda<raiz<direita

Uma versão melhorada da árvore de classificação binária (uma árvore de classificação binária especial), tente manter a árvore o mais curta possível!

Como saber se uma árvore está crescendo normalmente?

Árvore de classificação binária com fator de equilíbrio <= 1

Equilibre a profundidade máxima e o número mínimo de nós de uma árvore binária

inserir

prólogo

ordem intermediária

Posfácio

Percorrer linha por linha

Exigir

Para perguntas com poucos nós

As etapas principais do algoritmo Prime são: em um grafo conectado ponderado, V é um conjunto contendo todos os vértices U já é um nó na árvore geradora mínima, começando em qualquer vértice v no grafo. ={v}, Repita as seguintes operações: encontre uma aresta com o menor peso entre todas as arestas (u,w)∈E de todas u∈U,w∈V-U, e adicione a aresta (u,w) ao conjunto de arestas encontradas. E adicione o ponto w ao conjunto U. Quando U = V, a árvore geradora mínima é encontrada.

Primeiro determine os nós e selecione aqueles com os caminhos mais curtos em ordem.

Para perguntas com um pequeno número de lados

Ideia básica: edge-led. Em um grafo conectado ponderado, U é o conjunto de todas as arestas, N é o número de vértices e seja SU o conjunto de arestas que já estão na árvore geradora mínima. Repita as seguintes operações: a cada vez selecione uma aresta e∈U-SU com o menor peso e uma aresta que não forme um ciclo com as arestas em SU, e adicione-a a SU. Quando o número de arestas em SU é igual a N-1, a árvore geradora mínima é encontrada.

O número de nós sem um ponteiro direito é: número do nó raiz de nós não-folha

Exclua os simétricos, conte o número e certifique-se de que esteja sempre menos à esquerda e mais à direita ou mais à esquerda e menos à direita.

O nó raiz é único

Não há limite para o número de subárvores, mas elas não se cruzam.

natureza

árvore binária completa

árvore binária completa

Deve ser uma árvore binária completa

dagendui

pequena pilha de raízes

Armazenamento de pilha

Filtro superior

Filtrar

Como converter um array não ordenado em um heap?

duas operações

Pode ser implementado usando um pequeno heap raiz

Complexidade: O(NlogN)