Curso de Basic
Árvores binárias


Você está em: MarMSX >> Cursos >> BASIC   Á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 >>