Tutorial da estrutura de dados de árvores para iniciantes

Introdução

Uma árvore em software é como uma árvore biológica, mas com as seguintes diferenças:

• É desenhado de cabeça para baixo.
• Tem apenas uma raiz e sem haste.
• Os galhos emergem da raiz.
• Um ponto em que um ramo decola de outra filial ou a raiz é chamada de nó.
• Cada nó tem um valor.

Os galhos da árvore de software são representados por linhas retas. Um bom exemplo de uma árvore de software que você pode ter usado é a árvore do diretório do disco rígido do seu computador.

Existem diferentes tipos de árvores. Há a árvore geral da qual outras árvores são derivadas. Outras árvores são derivadas pela introdução de restrições na árvore geral. Por exemplo, você pode querer uma árvore onde não mais de dois galhos emanam de um nó; Essa árvore seria chamada de árvore binária. Este artigo descreve a árvore em geral e como acessar todos os seus nós.

O hiperlink para baixar o código é fornecido na parte inferior deste artigo.

Para entender as amostras de código deste artigo, você precisa ter conhecimento básico em JavaScript (ECMAScript). Se você não tiver esse conhecimento, poderá obtê -lo de http: // www.Broad-Network.com/chrysanthusforcha-1/ecmascript-2015 Course.htm

O diagrama de árvore geral

'A' é o nó raiz; É o nó de primeiro nível. B, C, D estão na segunda linha; Estes são nós de segundo nível. E, f, g, h, i, j, k estão na terceira linha e eles são nós de terceiro nível. Uma quarta linha teria produzido nós de quarto nível e assim por diante.

Propriedades das árvores

- Todos os ramos de todos os níveis de nós, têm uma fonte, que é o nó raiz.

- Uma árvore possui n - 1 galhos, onde n é o número total de nós. O diagrama acima para a árvore em geral tem 11 nós e 10 galhos.

- Ao contrário dos humanos, onde toda criança tem dois pais, com a árvore de software, toda criança tem apenas um pai. O nó raiz é o maior pai ancestral. Um pai pode ter mais de um filho. Todo nó, exceto o nó raiz, é uma criança.

Vocabulário de árvore

• Nó raiz: Este é o nó mais alto da árvore e não tem pai. Todos os outros nó têm um pai.
• Nós da folha: Um nó foliar é um nó que não tem filho. Eles geralmente estão no fundo da árvore e às vezes estão nos lados esquerdo e/ou direito da árvore.
• Chave: Este é o valor de uma árvore. Pode ser um número; Pode ser uma string; pode até ser um operador como + ou - ou x.
• Níveis: O nó raiz está no primeiro nível. Seus filhos estão no segundo nível; Os filhos dos nós do segundo nível estão no terceiro nível e assim por diante.
• Nó dos pais: Cada nó, exceto o nó raiz, tem um nó pai conectado a ele por um ramo. Qualquer nó, exceto o nó raiz, é um nó infantil.
• Nós irmãos: Nós irmãos são nós que têm o mesmo pai.
• Caminho: Os ramos (linhas retas) que conectam um nó a outro, através de outros nós, formam um caminho. Os galhos podem ou não ser setas.
• Nó ancestral: Todos os nós mais altos conectados a uma criança, incluindo os pais e o nó raiz, são nós ancestrais.
• Nó descendente: Todos os nós inferiores conectados a um nó, até as folhas conectadas, são nós descendentes. O nó em questão não faz parte dos nós descendentes. O nó em questão não precisa ser o nó raiz.
• Subárvore: Um nó mais todos os seus descendentes até as folhas relacionadas, formam uma subárvore. O nó inicial está incluído e não precisa ser a raiz; Caso contrário, seria toda a árvore.
• Grau: O número de crianças que um nó tem é chamado de grau do nó.

Atravessando todos os nós de uma árvore

Todos os nós de uma árvore podem ser acessados ​​para ler ou alterar qualquer valor do nó. No entanto, isso não é feito arbitrariamente. Existem três maneiras de fazer isso, tudo isso envolve a primeira travessia da profundidade da seguinte maneira:

1) na ordem: Simplificando, nesse esquema, a subárvore esquerda é atravessada primeiro; Em seguida, o nó raiz é acessado; Então, a subárvore direita é atravessada. Este esquema é simbolizado como esquerda-> root-> direita. A Fig 1 é re-exibida aqui para facilitar a referência:

Assumindo que existem dois irmãos por nó; Então esquerda-> raiz-> direito significa, você acessa o nó mais baixo e esquerdo primeiro, depois o pai do nó e depois o irmão direito. Quando houver mais de dois irmãos, tome o primeiro como a esquerda e o restante dos nós certos, como o direito. Para a árvore geral acima, a subárvore inferior esquerda é acessada para ter, [ebf]. Esta é uma subárvore. O pai desta subárvore é A; Então, a é acessado em seguida para ter [ebf] a. Em seguida, a subárvore [GCHI] é acessada para ter uma subárvore maior, [[ebf] a [gchi]]. Você pode ver a esquerda-> root-> perfil direito se retratando. Esta grande subárvore esquerda terá a subárvore, [JDK] à sua direita de completar o atravessamento para obter, [[ebf] a [gchi]] [jdk].

2) Pré-encomenda: Simplificando, nesse esquema, o nó raiz é acessado primeiro, depois a subárvore esquerda será atravessada a seguir, e então a subárvore direita é atravessada. Este esquema é simbolizado como raiz-> esquerda-> direita. A Fig 1 é re-exibida aqui para facilitar a referência.

Assumindo que existem dois irmãos por nó; Então raiz-> esquerda-> à direita significa, você acessa a raiz primeiro, depois a criança imediata esquerda e depois a criança imediata direita. Quando houver mais de dois irmãos, tome o primeiro como a esquerda e o restante dos nós certos, como o direito. O filho mais à esquerda do filho esquerdo é o próximo a ser acessado. Para a árvore geral acima, a subárvore raiz é [ABCD]. À esquerda desta subárvore, você tem a subárvore, [EF], dando a sequência de acesso, [ABCD] [EF]. À direita desta subárvore maior, você tem duas subáridas, [GHI] e [JK], dando a sequência completa, [ABCD] [ef] [ghi] [JK]. Você pode ver a raiz-> esquerda-> perfil certo retratando-se.

3) pós-ordem: Simplificando, nesse esquema, a subárvore esquerda é atravessada primeiro, depois a subárvore direita é atravessada e, em seguida, a raiz é acessada. Este esquema é simbolizado como esquerda-> direita-> raiz. A Fig 1 é re-exibida aqui para facilitar a referência.

Para esta árvore, as subáridas são, [efb], [ghic], [jkd] e [a] que formam a sequência, [efb], [ghic], [jkd] [a]. Você pode ver a esquerda-> direita-> perfil de raiz retratando-se.

Criando a árvore

A árvore acima será criada usando o ECMAScript, que é como a versão mais recente do JavaScript. Cada nó é uma matriz. O primeiro elemento de cada matriz de nó é o pai do nó, outra matriz. O restante dos elementos do nó são os filhos do nó, começando da criança mais à esquerda. Existe um mapa Ecmascript que relaciona cada matriz à sua string correspondente (letra). O primeiro segmento de código é:

O = new Array ();
A = new Array ();
B = new Array ();
C = novo array ();
D = new Array ();
//folhas
E = nova matriz (b); F = nova matriz (b); G = nova matriz (c); H = nova matriz (c);
I = nova matriz (c); J = nova matriz (d); K = nova matriz (d);
// Adicionando o conteúdo
O [0] = indefinido; O [1] = a;
A [0] = O; A [1] = b; A [2] = c; A [3] = D;
B [0] = a; B [1] = e; B [2] = f;
C [0] = a; C [1] = g; C [2] = h; C [3] = i;
D [0] = a; D [1] = j; D [2] = k;
// mapeamento de objetos para cartas
pares = [[a, 'a'], [b, 'b'], [c, 'c'], [d, 'd'], [e, 'e'], [f, 'f'] , [G, 'G'],
[H, 'h'], [i, 'i'], [j, 'j'], [k, 'k']];
mapaBJ = novo mapa (pares);

No ECMAScript, você pode acessar uma função que é definida mais abaixo no programa. No entanto, com variáveis, você não pode fazer isso. Você não pode acessar uma variável que é definida mais abaixo no programa. Esta é a razão pela qual as variáveis ​​acima foram desenvolvidas como mostrado.

Além disso, observe que acima do nó raiz A, há outro nó o (não zero). O primeiro elemento desta matriz (nó) é indefinido, o que significa que seu próprio pai é indefinido. O nó extra O foi adicionado para facilitar o código de travessia.

Há também um mapa. O mapa relaciona cada matriz de nomes de uma letra, com o nome da string correspondente de uma letra.

Função recursiva

Para acessar todos os elementos de uma árvore, você precisa de uma função recursiva. Uma função recursiva é uma função que continua se chamando até que uma condição seja cumprida.

Visitar um nó não significa necessariamente acessar o nó. Para acessar um nó, significa que seu valor é lido ou alterado. Nas amostras de código deste artigo, acessar um nó significa ler e exibir o valor (chave) do nó. Nas amostras de código, um nó pode ser visitado mais de uma vez, mas seu valor é acessado apenas uma vez.

Algoritmo e programação

Há um programa para cada uma das três técnicas de travessia.

Algoritmo e programação na ordem

Aqui, o nó mais baixo e mais esquerdo é visitado primeiro. As subáridas [ebf], [[ebf] a [gchi]] e [jdk] são desenvolvidas para dar a sequência completa, [[ebf] a [gchi]] [jdk].

Existem duas funções recursivas para este programa, onde cada um chama o outro. O principal é chamado fn (nó). O programa (código) é curto. Baixe o arquivo combinado abaixo para a codificação de detalhes.

Os três programas têm a mesma configuração de árvore de matriz (nó).

Algoritmo de pré-encomenda e programação

Aqui, há apenas uma função recursiva. É chamado, fn (nó). Aqui, as subáridas [ABCD], [EF], [GHI] e [JK] são desenvolvidas para dar a sequência completa, [ABCD] [EF] [GHI] [JK]. O programa para isso também é curto.

Os três programas têm a mesma configuração de árvore de matriz (nó).

Algoritmo e programação de pós-ordem

Aqui, o nó mais baixo e mais esquerdo é visitado primeiro. O [EFB], [GHIC], [JKD] e [A] subárvores são desenvolvidos para dar a sequência completa, [EFB], [GHIC], [JKD] [A] .

Existem duas funções recursivas para este programa, onde cada um chama o outro. O principal é chamado fn (nó). O programa para isso também é curto. Baixe o arquivo combinado abaixo para a codificação detalhada.

Os três programas têm a mesma configuração de árvore de matriz (nó).

Tipos de árvores

As árvores de programação de computadores são, de fato, estruturas de dados não lineares. As estruturas de dados lineares são listas, matrizes, pilhas, filas, pilhas, etc. Uma árvore com n nós tem galhos n-1. Quando o número de ramificações é igual ou maior que o número de nós, um gráfico é obtido. Um gráfico não é realmente uma árvore.

Existem árvores de software, que descrevem layouts, como a árvore do diretório no disco rígido de um computador. Muitas árvores não descrevem os layouts existentes. De fato, eles descrevem algoritmos. Por exemplo, o algoritmo matemático (x + y) x (x -y) é descrito por uma árvore onde x é o nó raiz, então + e - são nós filhos imediatos da raiz. X e Y são nós para crianças de +. X e Y são novamente os nós de crianças de -. Essa árvore é conhecida como uma árvore de expressão.

Muitos tipos diferentes de árvores podem ser categorizados em diferentes títulos; como árvore binária, árvore B, árvore de expressão, etc. Todos eles são derivados da árvore geral.

Algumas das categorias de árvores são divididas em outras categorias. A árvore binária, por exemplo, tem pelo menos a árvore de busca binária, a árvore AVL e a árvore cartesiana.

Baixando

Três programas foram fornecidos para este artigo. Existe um programa para a técnica em ordem (algoritmo), outra para a técnica de pré-encomenda, e mais uma para a técnica de pós-ordem. Todos eles foram colocados em um arquivo zip, chamado de travessia. O arquivo zip pode ser baixado em: github.

Conclusão

Uma árvore de software é como uma árvore normal no parque ou na floresta. No entanto, a árvore de programação de computador está de cabeça para baixo. Existem diferentes tipos de árvores. Outras árvores são derivadas pela introdução de restrições na árvore geral. Todos os nós de uma árvore podem ser acessados ​​usando um algoritmo de encomenda, pré-encomenda ou pós-ordem. Uma árvore de software pode ser produzida por qualquer linguagem de computador. O ECMAScript foi escolhido aqui porque é a linguagem do computador mais simples. O próximo tipo de árvore que você deve estudar é a árvore binária, pois é a estrutura de dados de árvores mais popular.