São estruturas necessárias em árvores de busca binária

Question

Eu olhei em algum código para BSTs e eu posso ver que cada nó é um struct. Isso é necessário?

Answer 1

int flat_tree[ 1000 ][ 3 ];
    // for each tree node, value is stored in element [id][0]
                        // id of left_child stored in element [id][1]
                        // id of right_child stored in element [id][2]

...

Eu não vou ir mais longe com isso.

De modo geral, structs / classes são usados ??para qualquer tipo de estrutura de dados ligados. Também geralmente, qualquer característica do sistema tipo pode ser derrotado ou ignorado e você pode fazer tudo (alocação de pilha, etc) em um conjunto de ints de forma muito dolorosa.

Answer 2

Não, isso poderia ser uma classe. Não pode ser um primitivo, porque ele precisa para armazenar um valor e também apontam para crianças.

Bem, eu deveria dizer que você poderia também representar sua BST como uma matriz, onde as crianças esquerda e direita do nó na posição i estão em posições 2 * i + 1 e 2 * i + 2, respectivamente. Mas então você teria que se preocupar sobre o redimensionamento, e você precisaria de um valor especial para representar nulo, e operações de exclusão tornar-se bastante complicado. Eu não recomendo esta abordagem como outra coisa senão um exercício acadêmico.

Answer 3

A sua não é obrigatório.
Mas desde que os dados de um nó contém, juntamente com os dois links, juntos, formam uma entidade lógica que geralmente são colocados juntos em um struct. Para que se torne mais fácil de funções de código que levam um nó como um argumento ou retornar um nó.

Answer 4

Não, não é, estritamente falando. Nos dias Fortran, as pessoas usadas matrizes paralelas, ou matrizes bidimensionais.

seção "Programação Estruturada", de Dahl, Dijkstra, e Hoare, de Tony Hoare falou sobre tipos de estruturação de dados e de registro.

Answer 5

Você pode fazer mais simples do que matrizes paralelas se a sua carga útil admite um valor sentinal: você pode usar uma árvore implícita (isto é, não se preocupar com links em tudo).

payload_type a[tree_size];

Apenas uma matriz plana longa contendo apenas valores de carga il, com a posição na matriz de codificação para a estrutura de ligação:

• a[0] é root
• a[1] é raiz-> esquerdo
• a[2] é raiz-> direito
• a[3] é raiz-> esquerdo> esquerdo
• a[4] é raiz-> esquerdo> direito
• ...

Para o nó na posição i, vá para o 2 * i + 1 para a esquerda e 2 * i + 2 para a direita

Você inicialize-o a todos os valores sentinal, e começar a adicionar coisas ...