Existe apenas um nó raiz

Quando n>1, os nós restantes podem ser divididos em m conjuntos finitos disjuntos Ti, cada conjunto é uma subárvore da raiz.

O grau máximo de um nó é chamado de grau da árvore

A soma dos graus dos nós da árvore = a soma do número de ramos = o número de nós - 1

árvore binária completa

árvore binária completa

Árvore de classificação binária

árvore binária balanceada

O número de nós folha em uma árvore binária não vazia = o número de nós com grau 2 1, ou seja, n0=n2 1

Existem no máximo 2 ^ (k-1) nós no k-ésimo nível de uma árvore binária não vazia.

Uma árvore binária de altura h possui no máximo 2 ^ h-1 nós.

Uma árvore binária pode ser determinada exclusivamente por sua sequência de pré-ordem (ou pós-ordem) e sequência de inordem.

Uma árvore binária pode ser determinada exclusivamente por sua sequência hierárquica e sequência ordenada.

De acordo com as sequências de pré-ordem e pós-ordem da árvore binária, o relacionamento ancestral de alguns nós pode ser determinado: se a pré-ordem for aX e a pós-ordem for Xa, então os nós do conjunto Se eles são irmãos, a ordem deve ser consistente, ou seja, o irmão da esquerda vem primeiro)

Encontre o primeiro nó na sequência inorder na árvore binária de dicas inorder

Encontre o sucessor do nó p na árvore binária de dicas em ordem na sequência em ordem

Algoritmo de travessia em ordem para árvores binárias com dicas em ordem sem nó principal

Encontre o sucessor do nó na árvore binária de dicas de pré-encomenda

Encontrando o sucessor de um nó em uma árvore binária usando pistas de pós-ordem

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

O comprimento do caminho ponderado da árvore: a soma dos comprimentos do caminho ponderado de todos os nós folhas da árvore

Árvore Huffman: Entre as árvores binárias contendo n nós folha ponderados, a árvore binária com o menor comprimento de caminho ponderado (WPL) também é chamada de árvore binária ideal.

Processo de construção

Características

Codificação de Huffman

Normalmente, a representação pai de uma árvore (floresta) é usada como estrutura de armazenamento do conjunto union-find, e cada subconjunto é representado por uma árvore. Todas as árvores que representam subconjuntos formam uma floresta que representa todo o conjunto e são armazenadas na matriz de representação pai. Normalmente, o subscrito do elemento da matriz é usado para representar o nome do elemento, e o subscrito do nó raiz é usado para representar o nome da subcoleção. O nó pai do nó raiz é um número negativo.

1) Inicial (S): inicializa cada elemento do conjunto s em um subconjunto com apenas um único elemento.

2) Union(S, Root1, Root2): Mescla o subconjunto Root2 no conjunto S no subconjunto Root1. Exigir Root1 e Root2 são disjuntos, caso contrário a mesclagem não será realizada.

3) Find(S,x): Encontre o subconjunto onde o único elemento x está localizado no conjunto s e retorne o nó raiz do subconjunto.

Um conjunto de espaços contínuos é usado para armazenar nós ao mesmo tempo, um pseudoponteiro é adicionado a cada nó para indicar a localização dos pais;

Você pode obter rapidamente os nós pais de um nó, mas precisa percorrer a matriz para encontrar os filhos do nó.

Conecte os nós filhos de cada nó com uma única lista vinculada, n nós correspondem a n listas vinculadas

Encontrar filhos é simples, mas encontrar pais requer percorrer n listas vinculadas

Usando uma lista vinculada binária como estrutura de armazenamento da árvore

É fácil encontrar filhos, mas é mais difícil encontrar nós pais (o ponteiro pai pode ser adicionado)

Usando uma lista vinculada binária como meio, existe uma árvore binária única correspondente a cada árvore (e vice-versa)

Regra de conversão: "Filho esquerdo, irmão direito"

Semelhante à conversão acima, cada árvore é primeiro convertida em uma árvore binária e, em seguida, a raiz da enésima árvore é considerada a irmã direita da raiz da enésima árvore.

Percurso raiz primeiro

travessia de raiz traseira

Passagem de nível

passagem de pré-encomenda

travessia em ordem