Curso de Basic
Árvores binárias


  Árvores são estrutura de dados que são bastante útil para armazenar dados hierárquicos. Ela possui diversos elementos estruturantes chamados de nós.
  Cada nó contem os seguintes elementos:
 

  Uma árvore deverá ter um elemento raiz, que se liga a outros elementos por meio dos ponteiros. A quantidade de filhos é ilimitada, porém cada nó só poderá se ligar a nós de um nível inferior adjacente. Além disso, cada nó não poderá ter mais de 1 nó pai.
  Exemplo uma estrutura em árvore.

 

  Os ponteiros são criados em outras linguagens como C ou Pascal, através de tipos de dado que contém o endereço de memória que contém o nó referido. Entretanto, podemos fazer tudo isso em Basic através de vetores.
  Vamos aplicar esse conceito à árvores binárias, por serem mais simples. Entretanto, podemos estender o conceito visto a seguir a qualquer tipo de árvore. Uma árvore binária é um tipo de estrutura em árvore onde cada nó tem no máximo dois nós filhos.

  Para uma árvore binária, podemos criar um vetor para armazenar os dados e uma matriz de Mx2 para armazenar os ponteiros. O índice de cada linha do vetor e da matriz representam um nó da árvore. Assim, os ponteiros irão referenciar o índice do nó que ele estiver apontando, em vez do endereço de memória. Veja o exemplo a seguir.

 

  Essa árvore pode ser representada pelo vetor "D(i)" e a matriz "P(i,j)".

  Vetor D(i):
Índice - valor
   1   -   1
   2   -   2
   3   -   3
   4   -   4
   5   -   5
   6   -   6
   7   -   7
   8   -   8

  Matriz P(i,j):
   1    2
1  2    3
2  4    5
3  6    0
4  0    7
5  0    0
6  0    8
7  0    0
8  0    0
  O valor 0 indica que aquele ponteiro aponta para ninguém. O valor 1 para "j" indica o nó à esquerda, enquanto que o valor 2 indica o nó à direita.

  O programa a seguir cria uma árvore binária e permite ao usuário navegar por ela.
10 DIM D(8),P(8,2)
20 FOR I=1 TO 8
30 D(I)=I
40 READ P(I,1),P(I,2)
50 NEXT I
100 ' Percorre arvore
110 I=1
120 PRINT:PRINT"Estou no no'";I
130 INPUT"Gostaria de descer para a esquerda (e), direita (d) ou recomecar (r)";D$
140 IF D$<>"d" AND D$<>"e" AND D$<>"r" THEN 130
150 IF D$="r" THEN CLS:GOTO 110
160 IF D$="e" THEN IF P(I,1)<>0 THEN I=P(I,1) ELSE PRINT"Fim de linha"
170 IF D$="d" THEN IF P(I,2)<>0 THEN I=P(I,2) ELSE PRINT"Fim de linha"
180 GOTO 120
200 DATA 2,3,4,5,6,0,0,7,0,0,0,8,0,0,0,0


<< Anterior Basic Próxima >>


/MARMSX/CURSOS/Basic