ESTRUTURAS DE DADOS
Prof. Marcelo Azambuja

1. Lista
         1.1 Lista Estática Sequencial 
                - Exercícios sobre Lista Estática Sequencial
         1.2 Lista Estática Encadeada
                - Exercícios sobre Lista Estática Encadeada
         1.3 Lista Dinâmica Encadeada ==> com Ponteiros
                - Exemplo de Lista Encadeada Dinâmica com Ponteiros

2. Pilha (Estrutura de Dados tipo LIFO)
         2.3 Um exemplo prático de aplicação de Pilha: Notação Polonesa para Cálculos (calculadoras científica tipo HP)
         2.4 Implementação de um programa em Pascal para armazenamento de dados com Pilha 

3. Fila (Estrutura de Dados tipo FIFO)
        Implementação de um programa em Pascal para armazenamento de dados com Fila Sequencial
        3.5 Fila CIRCULAR
            Implementação de um programa em Pascal para armazenamento de dados com Fila CIRCULAR 

4.  DEQUE - Uma Lista (do tipo PILHA) com Acesso nas 2 Extremidades: DEQUE – Double Ended QUEue
            Exemplo de implementação (em Pascal) de uma Lista tipo DEQUE

- Revisão sobre as Estruturas de Dados Pilha, Fila e Deque.

1. 5. Download material (1) sobre Estruturas de Dados tipo "Árvores": 
               Raiz, Sub-árvores, Grau, Altura, Ancestrais e Descendentes. 
               Árvores Binárias: percurso em Árvores Binárias. 
               Árvore Binária de Pesquisa. Árvores Binárias Balanceadas - AVL.    Código Pascal de (árvore binária).

    Download material (2) sobre Árvores (muito bom!!)

            Árvores B
                Material 1
                Material 2

Material de Consulta: excelente livro sobre Estruturas de Dados (Autor: Prof. Paulo Roberto Gomes Luzzardi)

(1a. Aula)

• Livro Prof. Luzzardi: Introdução; Dados; Tipos de Dados: Primitivos e Estruturados; Ponteiros; Vetores e Matrizes. Exercícios práticos sobre Vetores e Matrizes (em Pascal).
  • 1) Revisao Pascal
  • 2) Ler o material teórico até a página  9 (fazer os dois exercícios práticos sobre Vetores da página 9);
  • 3) Discussões:
    • Se após a entrada de todos os valores no Vetor/Matriz for necessário retirar um dos elementos do meio da estrutura?
    • Se após a entrada de todos os valores no Vetor/Matriz for necessário retirar o primeiro elemento da estrutura?
    • Se após a entrada de todos os valores no Vetor/Matriz for necessário inserir um novo elemento no meio da estrutura?
• Material de Consulta e revisão sobre Pascal: página Web Profa. Flávia Carvalho.

1. Lista

Uma Lista, que pode ser visualizadao como um array (vetor), pode conter uma seqüência ordenada de dados primitivos ou de dados estruturados (tais como registros - records). Em uma Lista, estes dados são arranjados de forma consecutiva - Lista Estática Seqüencial - ou não consecutiva - Lista Estática Encadeada.

O Pascal permite construir estruturas de dados avançadas - Listas Dinâmicas, mais versáteis utilizando ponteiros e variáveis dinâmicas.

Um ponteiro é uma variável que contém o endereço de memória de uma outra variável ou estrutura de dados. Uma variável declarada como ponteiro é alocado durante a execução real de um programa.

Variáveis dinâmicas são armazenadas (em Pascal e na maioria das Linguagens de Programação) numa área especial da memória chamada Heap. Um programa pode criar qualquer número de variáveis dinâmicas, enquanto existir espaço disponível no Heap.
 

1.1 Lista Estática Seqüencial

Uma lista estática seqüencial é um arranjo de dados ou registros onde estão estabelecidos regras de precedência entre seus elementos ou é uma coleção ordenada de componentes do mesmo tipo. O sucessor de um elemento ocupa posição física subsequente.
Ex: lista telefônica, lista de alunos

A implementação de operações pode ser feita utilizando array (vetor) e record(registro), onde o vetor associa o elemento a(i) com o índice i (mapeamento sequencial).
 

1.1.1 Características de Lista Estática Sequencial

·         elementos na lista estão ordenados;

·         armazenados fisicamente em posições consecutivas;

·         inserção de um elemento na posição a(i) causa o deslocamento a direita do elemento de a(i) ao último;

·         eliminação do elemento a(i) requer o deslocamento à esquerda do a(i+1) ao último;

Mas, absolutamente, uma lista estática sequencial ou é vazia ou pode ser escrita como ( a(1), a(2), a(3), ... a(n) ) onde a(i) são átomos de um mesmo conjunto S.

Além disso, a(1) é o primeiro elemento, a(i) precede a(i+1), e a(n) é o último elemento.

 Assim as propriedades estruturadas da lista permitem responder a questões como:

·         qual é o primeiro elemento da lista

·         qual é o último elemento da lista

·         quais elementos sucedem um determinado elemento

·         quantos elementos existem na lista

·         inserir um elemento na lista

·         eliminar um elemento da lista

Consequência: As quatros primeiras operações são feitas em tempo constante. Mas, as operações de inserção e remoção requererão mais cuidados.

Vantagem:

·         acesso direto indexado a qualquer elemento da lista

·         tempo constante para acessar o elemento i - dependerá somente do índice.

Desvantagem:

·         movimentação quando eliminado/inserido elemento

·         tamanho máximo pré-estimado

Quando usar:

·         listas pequenas

·         inserção/remoção no fim da lista

·         tamanho máximo bem definido

1.1.2 Definição da ED (Estrutura de Dados)

 Const MAX=100;

 Type lista=record

           A:array[1..MAX] of integer;

           n:0..MAX;

      End;

 Var L: lista;

1) Acesso a um elemento

 Writeln (L.A[i]);

2) Atualização

 L.A[i]:= 'Valor'

3) Tamanho da Lista

 Begin

 tamanho:=L.n;

 End;

4) Inserção de um elemento na posição i
Requer o deslocamento à direita dos elementos a(i+1)...a(n)

{ considerando que a posição foi obtida em um procedimento de consulta executado préviamente }

{ também é necessário verificar se a lista não está cheia }

 Begin

      For j:=L.n+1 downto i+1 do

           lista.A[j]:=L.A[j-1];

      L.A[i]:='novo valor';

      L.n:=L.n+1;

 End;

5) Remoção do i-ésimo elemento
Requer o deslocamento à esquerda dos elementos a(i+1)...a(n)

 Begin

      For j:=i to L.n-1 do

           L.A[j]:=L.A[j+1];

      L.n:=L.n-1;

 End;

 1.1.3 Exercícios

Dada uma lista sequecial ordenada L1, escreva procedimentos Pascal que:

·         verifique se L1 está ordenada ou não (a ordem pode ser crescente ou decrescente)

·         faça uma cópia da lista L1 em uma outra lista L2;

·         faça uma cópia da Lista L1 em L2, eliminando elementos repetidos;

·         inverta L1 colocando o resultado em L2;

·         inverta L1 colocando o resultado na própria L1;

·         intercale L1 com a lista L2, gerando a lista L3. considere que L1, L2 e L3 são ordenadas.

·         gere uma lista L2 onde cada registro contém dois campos de informação: elem contém um elemento de L1, e count contém quantas vezes este elemento apareceu em L1.

·         elimine de L1 todas as ocorrências de um elemento dado, L1 ordenada.

·         assumindo que os elementos da lista L1 são inteiros positivos, forneça os elementos que aparecem o maior e o menor número de vezes (forneça os elementos e o número de vezes correspondente)

1.2 Lista Estática Encadeada

Os elementos da lista são registros com um dos componentes destinado a guardar o endereço do registro sucessor.
Ex: L = anta, cabra, macaco, pato, rato

Cada registro é:

ou

Há duas alternativas para implementação de operações de listas encadeadas: utilizando arrays ou variáveis dinâmicas.

Encadeamento em arrays

Eliminando o elemento "cobra" teremos:

O registro 2 tornou-se disponível para as próximas inserções...

Implementação utilizando array

Após sucessivas inserções e eliminações como descobrir quais registros estão disponíveis?
Juntá-los numa lista DISPO. Assim, os registros 6, 7, ... m estariam inicialmente na lista DISPO.

Como deverá ser Dispo ? Sequencial?
Ela deve ser capaz de anexar os registros eliminados da lista principal L. Suponha que queremos inserir algum elemento:

Isso implica que :

·         a eliminação de um elemento da lista principal causa a inserção de um registro na lista Dispo

·         a inserção de um elemento na lista principal causa a utilização de um dos registros da Dispo

No exemplo dado, ao eliminar "cobra" anexamos esse registro à dispo.

A princípio podemos utilizar qualquer posição (todos são vazios mesmos!!). A posição mais conveniente é a do primeiro elemento do Dispo - uma vez que requer o acesso a poucos ponteiros.

Se a próxima operação é a inserção do elemento ovelha temos:

Com várias inserções e eliminações, os registros da lista principal ficariam espalhados pelo vetor, intermediados por registros disponíveis.

Vantagens:

·         não requer mais a movimentação de elementos na inserção e eliminação (como na lista sequencial);

·         apenas os ponteiros são alterados (lembre que cada registro pode conter elementos muito complexos);

Desvantagens:

·         necessário prever espaco máximo da lista;

·         necessário gerenciar a Dispo.

·         o acesso é não indexado, para acessar a(i) temos que percorrer a(1) ... a(i-1) pois o endereço de a(i) está disponível apenas em a(i-1);

·         aumento do tempo de execução, o qual é gasto na obtenção de espaço de memória;

·         reserva de espaço para a Dispo;

·         tamanho máximo pré-definido.

Quando usar:

·         quando for possível fazer uma boa previsão do espaço utilizado (lista principal + Dispo) e quando o ganho dos movimentos sobre a perda do acesso direto a cada elemento for compensador.

1.2.1 Implementação de Operações

Supondo apenas um campo de informação do tipo T:

 Const N=_____; {número máximo de elementos}

 Type endereço= 0..N; { elementos armazenados nas posições de 1 a N do array; o valor 0 indica fim  da lista }

 Type Rec = record

                info: T

                lig: endereço;

        End;

 Lista = record

               A: array[1..N] of Rec;

               Prim, Dispo: endereco;

        End;

 Var L: lista;

1) Qual é o primeiro elemento da lista ?

 Function Primeiro (L: lista): T;

 Begin

      If L.Prim <> 0 Then

      Primeiro := L.A[L.Prim].info;

 End;

2) Qual é o último ?

 Function Ultimo(L: Lista): T;

 Var p: endereco;

 Begin

      If L.Prim = 0 Then 

               {Retorna lista vazia }

      Else

           Begin

                 p := L.Prim;

           While L.A[p].lig <> 0 do

                 p := L.A[p].lig; {L.A[p].info é o último elemento}

      End;

      Ultimo := L.A[p].info;

 End;

3) Quantos elementos tem a lista ?

 Function No_elementos(L: Lista): integer;

 Var Nelem: integer;

 p: endereco;

 Begin

      If L.Prim = 0 Then

           Nelem := 0 {lista vazia}

      Else

           Begin

                 p := L.Prim;

                 Nelem := 1;

                 While L.A[p].lig <> 0 do

                 Begin

                      Nelem := Nelem + 1; {Nelem contém o Número de elementos}

                 p := L.A[p].lig;

           End;

      End;

      No_elementos := Nelem;

End;

Algoritmos para inserção e eliminação de elementos

Os algoritmos requerem a mudança de vários ponteiros: do antecessor do registro na lista, do ponteiro da lista Dispo, e do registro a ser inserido/eliminado.

Temos ObterNo(j) e DevolverNo(j), as quais permitem obter um registro de índice j da Dispo, ou devolver o registro de indice j, respectivamente.

Na inserção podemos contar com o registro j como sendo disponível, e na eliminação podemos contar com o registro j como a ser deixado disponível.

Para inserir ou eliminar um elemento da lista, temos que saber do endereço do predecessor (lembre que a busca é guiada pelo conteúdo do registro, no caso de listas ordenadas). Este predecessor é quem contém o endereço daquele que será o sucessor do elemento inserido/eliminado.

inserção

eliminação

1) Inserção após o registro de endereço k

 Procedure Insere(var L: Lista; k: endereco, valor: T);

 Var j: endereco;

 Begin

      If L.Dispo <> 0 Then {se a Dispo está vazia, nao pode inserir!}

           Begin

                 ObterNo(j);

                 L.A[j].info := valor;

                 L.A[j].lig := L.A[k].lig;

                 L.A[k].lig := j;

           End

      Else {não pode inserir registro}

      ...

 End;

2) Eliminação do registro de endereço j precedido por k

 Procedure Remover(var L: Lista; k,j: endereco);

 Begin

      L.A[k].lig := L.A[j].lig;

      DevolverNo(j);

 End;

3) Casos especiais

Inserção antes do primeiro elemento

 Procedure Insere_prim(var L: Lista; valor: T);

 Var j: endereco;

 Begin

      If L.Dispo <> 0 Then

      Begin

           ObterNo(j);

            L.A[j].info:= valor;

           L.A[j].lig := L.Prim;

           L.Prim := j;

       End

      Else

      { não pode inserir }

 End;

OBS: No caso da lista estar vazia, Prim passa a apontar o único elemento da lista.

Inserção em lista vazia

 Procedure Insere_ListaVazia(var L: Lista; valor: T);

 Var j: endereco;

 Begin

      If L.Dispo <> 0 Then { lista vazia ou prim = 0 }

           Begin

                 Obter_No(j);

                 L.A[j].info:=valor;

                 L.A[j].lig:=0; {null}

                 L.Prim:=j;

           End;

 End;

Eliminação do primeiro elemento

 Procedure Remove_Primeiro(var L: Lista);

 Var j: endereco;

 Begin

      j := L.Prim;

      L.Prim := L.A[L.Prim].lig;

      DevolverNo(j);

 End;

4) Acesso ao i-ésimo elemento A[i].info

 Function Acessa_iesimo(L: Lista; Var dado: T): boolean;

 Var p,j: endereço;

 Begin

      p := L.Prim; { começa do primeiro elemento }

      j := 1;

      While (j < i) and (p <> 0) do

           Begin

                 p := L.A[p].lig; { fim := (p=0) }

                 j := j + 1; { achou := (j=i) }

           End;

      If p = 0 Then

           Begin

                 Acessa_iesimo:=false;{ lista não possui i elementos }

                 dado:=0;

           End

           Else

                 Begin

                      Acessa_iesimo:=true;

                 dado:=L.A[p].info; { A[p] é o elemento procurado}

           End;

End;

5) Eliminar o registro de conteúdo dado pela variável valor

 Procedure Remove_elem(var L: lista; valor: T);

 Var pa, p, endereco;

 acabou: boolean;

 Begin

      pa := 0; { ponteiro anterior }

      p := L.Prim; { busca a partir do primeiro }

      acabou := (p=0); { termina quando fim da lista ]

      While not (acabou) do

           Begin

                 If L.A[p].info <> valor Then

                 Begin

                      pa := p;

                      p := L.A[p].lig;

                      acabou := (p=0);

                 End

                 Else

                      acabou := true;

           End;

      If p=0 Then

           { não existe o conteúdo `valor' na lista }

      Else

           Begin

                 If pa = 0 Then

                      L.Prim := L.A[L.Prim]lig; { eliminar o primeiro elemento }

                 Else

                      L.A[pa].lig := L.A[p].lig;

                 DevolverNo(p);

           End;

 End;

1.2.2 Alocação de Nó em Lista Estática Encadeada

Inicialização da Lista

Inicialmente todas as posições do vetor A estão disponíveis, portanto fazem parte de "Dispo".

 Procedure Init(L: Lista);

 Begin

      L.Dispo:=1; {primeiro elemento}

      L.Prim:=0; {lista principal está vazia}

      For i:=1 to n-1 do

           L.A[i].lig:=i+1;

      L.A[n].lig:=0; {receber 0 corresponde ao nil}

 End;

1.2.3 Exercícios

1) Dada uma lista encadeada ordenada L1, escreva procedimentos Pascal que:

·         verifique se L1 está ordenada ou não (a ordem pode ser crescente ou decrescente)

·         faça uma cópia da lista L1 em uma outra lista L2;

·         faça uma cópia da Lista L1 em L2, eliminando elementos repetidos;

·         inverta L1 colocando o resultado em L2;

·         inverta L1 colocando o resultado na própria L1;

·         intercale L1 com a lista L2, gerando a lista L3. considere que L1, L2 e L3 são ordenadas.

·         gere uma lista L2 onde cada registro contém dois campos de informação: elem contém um elemento de L1, e count contém quantas vezes este elemento apareceu em L1.

·         elimine de L1 todas as ocorrências de um elemento dado, L1 ordenada.

·         assumindo que os elementos da lista L1 são inteiros positivos, forneça os elementos que aparecem o maior e o menor número de vezes (forneça os elementos e o número de vezes correspondente)

1.3 Lista Dinâmica Encadeada ==> com Ponteiros

As linguagens de programação modernas tornaram possível explicitar não apenas o acesso aos dados, mas também aos endereços desses dados.

Isso significa que ficou possível a utilização de ponteiros explicitamente implicando que uma distinção notacional deve existir entre os dados e as referências (endereços) desses dados.

A notação em Pascal, é:

 Type Tp = ^T

Essa declaração expressa que valores do tipo Tp são ponteiros para dados do tipo T.
Portanto, lemos o simbolo ^ como sendo ponteiro para... e na declaração acima lemos Tp é um ponteiro para variáveis do tipo T.

O fato de que o tipo dos elementos apontados ser evidente na declaração do ponteiro tem importância fundamental. Isso distingue ponteiros de linguagens de alto nível de endereços em Assembly.

Valores para ponteiros são gerados quando dados correspondentes a seus tipos são alocados/desalocados dinamicamente. Em Pascal, os procedimentos new e dispose existem com esse propósito.

Portanto, deixa-se a cargo do programa (via linguagem de programação), e não do programador, prover e devolver espaço para inserções e eliminações em tempo de execução.

Custo: Tempo de execução comprometido.

Idéia: O programador declara apenas o tipo de registro que contém um elemento da lista, e avisa que a alocação será dinâmica. Sempre que requisitar um registro novo para a inserção, ou liberar um registro a ser eliminado, o programador lança mão de duas rotinas pré-definidas para este fim.

1) Registros com ponteiros

Dizemos que uma variável do tipo prec aponta para, ou é um ponteiro para um registro do tipo rec . Ponteiro é o único tipo que pré-referencia outro em Pascal.

 Type prec = ^rec;

 Lista = prec;

 rec = record

        info: T; {seu tipo preferido}

        lig: Lista;

 End;

 Var p, L: Lista; {nossos ponteiros }

Um ponteiro do tipo Lista pode assumir o conjunto de valores que correspondem a endereços reais de memória. Por exemplo, sendo var p: Lista podemos ter:

onde o conteúdo de p corresponderia ao endereço do objeto. Esses endereços serão as ligações das listas encadeadas dinâmicas.

Sendo o registro: 

Para designar ponteiro, objeto e campos, a notação utilizada é:

 ponteiro: p

 objeto: p^

 campos: p^.info

 p^.lig

2) Endereço nulo (terra)

Pascal provê uma constante pré-definida para denotar o endereço nulo nil. Podemos utilizá-la para atribuições e testes, como nos exemplos abaixo:

 1: L := nil;

 2: If (p = nil) Then ...

Ponteiro x Objeto Apontado

Nos exemplos abaixo, é ilustrada a diferença entre as operações de atribuição entre ponteiros (por exemplo, p : = q ) e a atribuição entre o conteúdo dos registros apontados pelos ponteiros (isto é: p^ : = q^).

 var p,q: Lista;

Dada a situação abaixo, chamada de (a):

Dada a situação (a), após a atribuição p : = q temos a representação abaixo (b). Esta atribuição só é válida para ponteiros do mesmo tipo e é a única operação entre ponteiros.

Dada a situação (a), após a atribuição p^ : = q^ temos a representação abaixo (c), onde o conteúdo é atribuido (lembre que p^ equivale a L.A[p]).

1.3.1 Manipulação de Registros

1) Declaração de Variável

Registro do tipo rec

 var p: ^rec;

2) Criação de um registro

new(p);

a) efetivamente aloca uma variável do tipo rec
b) gera um ponteiro do ^rec apontando para aquela variável
c) atribui o ponteiro à variável p

A partir daí:

a) o ponteiro pode ser referenciado como p
b) variável referenciada por p é denotada por p^

3) Atribuição de conteúdo ao registro:

 p^.info := valor;

4) Liberação de um registro

dispose(p)

a) operação libera o espaço apontado por p
b) p passa a ter valor indefinido
 

 Definição da Estrutura de Dados

 Type prec = ^rec;

 Lista = prec;

 rec = record

        info: T; {seu tipo preferido}

        lig: Lista

 End;

 Var p: Lista; {em nossos exemplos, representará um ponteiro para qualquer elemento da lista}

 L: Lista; {em nossos exemplos, representará o ponteiro para o primeiro elemento da lista }

·         Operações sobre Listas Dinâmicas

1.3.3 Implementação das Operações

1) Criação da lista vazia

Procedure Create (Var L : Lista);

Begin

 L:= nil;

End;

2) Inserção do primeiro elemento

Procedure Insere_Prim(Var L: Lista; valor: T);

Var p: Lista;

Begin

 new(p);

 p^.info := valor;

 p^.lig := nil;

 L := p;

End;

3) Inserção no início de uma lista

Procedure Insere_Inic(Var L: Lista; valor: T);

Var p: Lista;

Begin

 new(p);

 p^.info := valor;

 p^.lig := L;

 L := p;

End;

4) Acesso ao primeiro elemento da lista

Function Prim(L: Lista): T;

Begin

 Prim:= L^.info;

End;

5) Acesso ao último elemento da lista

Function Ultimo(L: Lista): T;

Begin

 If L = nil Then

        { lista vazia}

 Else

        Begin

               p := L;

               While p^.lig <> nil do

                       p := p^.lig;

               Ultimo := p^.info; {p^.info é último elemento}

        End; {p^ é o último registro}

End;

6) Qual o número de elementos da lista ?

Function Nelem(L: Lista): integer;

Begin

 If L = nil Then

        Nelem := 0

 Else

        Begin

               p := L;

               Nelem := 1;

               While p^.lig <> nil do

               Begin

                       Nelem := Nelem + 1;

                       p := p^.lig;

               End;

        End;

End;

7) Remoção do elemento apontado por j, que segue k

Procedure Elimina_depois(Var L: Lista; k, j: Lista);

Begin

 k^.lig := j^.lig;

 dispose(j);

 End;

8) Remoção do primeiro elemento

Procedure Remove_Prim(Var L: Lista);

 Begin

         p := L;

        L:= L^.lig;

        dispose(p)

 End;

OBS: funciona no caso de remocao em lista com um único elemento. 

10) Eliminar um valor v de uma lista ordenada L

 Procedure Elimina(v: T; Var L: Lista);

 Var

 p, pa: Lista;

 acabou: boolean;

 Begin

        pa := nil;

        p := L;

        acabou := (p = nil);

        While (not acabou) do

               If p^.info < v Then

               Begin

                       pa := p;

                       p := p^.lig;

                       acabou := (p = nil);

               End

               Else acabou := true;

               {While acaba aqui!}

               { p = nil ou p^.info = v ou p^.info > v }

        If (p = nil) Then

               "lista não contém v"

        Else

               If p^.info > v Then

                       "lista não contém v"

               Else

               Begin

                       If pa = nil Then

                               L := p^.lig

                       Else pa^.lig := p^.lig;

                               dispose(p);

                       End;

 End;

11) Inserção do valor v antes do elemento apontado por p

Uma alternativa para evitarmos percorrer a lista para encontrar o antecessor de p é inserirmos o valor dado, de fato, após o elemento apontado por p, após realizar uma cópia de conteúdo entre ponteiros....

Procedure Insere_antes(Var L: Lista; v: T; p: Lista);

Var q: Lista;

Begin

 new(q);

 q^ := p^;

 p^.info := v;

 p^.lig := q;

End;

12) Criação de uma lista L com registros numerados de 1 .. n

Procedure Cria_Lista_num(Var L: Lista);

 Var L, q: Lista;

 Begin

 L := nil; { começa com lista vazia }

 While n > 0 do

 Begin

 new(q);

 q^.lig := L;

 q^.info := n;

 L := q;

 n := n-1;

 End;

 End;

13) Remoção do registro sucessor de p e inserção do mesmo como cabeça em uma lista apontada por q

Procedure Remove_Insere(Var q: Lista; p: Lista);

 Begin

 r := p^.next; {r aponta o sucessor de p^}

 p^.lig := r^.lig; {r^ sai da lista}

 r^.lig := q; {r^ passa a apontar q^ }

 q := r; {r^ passa a ser o primeiro elemento da lista

 End; apontada por q}

14) Impressão recursiva de uma lista

 Procedure Printlist(p: Lista);

 Begin

        If (p <> nil) Then

        Begin

               write(p^.info);

               Printlist(p^.lig);

        End;

 End;

1.3.1 Exemplo de Uso de Ponteiros

Este programa cria uma lista de N elementos cujo conteúdo é o quadrado da sua posição e a impressão inclui um hifem entre cada elemento 'info' (o dado) da lista.

Program Listas;

Uses wincrt; {ou crt - dependendo do compilador utilizad}

Type

 prec = ^fred;

 lista = prec;

 fred = record

        info: integer;

        lig: prec;

 End;

Var

 L, p,r: lista;

 N,i: 0..10;

Begin

 ClrScr;

 write('Dê o número de elementos da lista [1..10]: ');

 readln(N);

 L := nil;

 new(p);       {gerou ponteiro para alocacao do primeiro objeto}

 p^.info := 1; {o campo info deste primeiro objeto recebeu um valor qualquer... }

 L := p;       {armazenado o endereco do primeiro objeto no ponteiro L para sabermos onde inicia nossa lista}

 For i := 2 to N do

 Begin

        r := p;         {armazenou no ponteiro r o endereco atual do ponteiro p}

        new(p);         {gerou um novo endereco em p para objeto}

        r^.lig := p;    {o objeto anterior - armazenado em r - recebeu o endereco do novo objeto criado: p}

        p^.lig := nil;  {o atual recebeu nil para indicar final da lista}

        p^.info := i*i; {geracao de um numero qualquer para o campo info deste objeto...}

 End;

 writeln('*** Impressão de sua lista ***');

 p := L;

 While (p <> nil) do

 Begin

        write(' - ',p^.info);

        p := p^.lig;

 End;

 writeln;

 writeln('*** Fim ***');

 readln;

End.

2. Pilhas
* Estruturas de Dados tipo LIFO (Last In First Out) (último dado a entrar é o primeiro a sair)

2.1 Conceito de Pilhas

Pilhas são listas onde a inserção de um novo item ou a remoção de um item já existente se dá em uma única extremidade, no topo.

Pilha vazia 

Insere(A) 

Insere(B) 

Retira(B) 

Insre(C) 

Retira(C) 

Retira(A) 

Definição

Dada uma pilha P=( a(1), a(2), ..., a(n) ), dizemos que a(1) é o elemento da base da pilha; a(n) é o elemento topo da pilha; e a(i+1) está acima de a(i).

Pilhas são também conhecidas como listas LIFO (last in first out).

Operações Associadas:

1. criar (P) - criar uma pilha P vazia

2. inserir (x, P) - insere x no topo de P (empilha): push(x,P)

3. vazia (P) - testa se P está vazia

4. topo (P) - acessa o elemento do topo da pilha (sem eliminar)

5. elimina (P) - elimina o elemento do topo de P (desempilha): pop(P)

Um exemplo prático de Estruturas de Dados tipo Pilha pode ser demonstrado com, por exemplo, a lista de "últimas chamadas" (feitas ou recebidas) na memória de um telefone celular. Sempre a última chamada é a que aparece ao consultarmos esta lista, ou seja, o último valor a entrar é o primeiro a ser consultado (sair). E os seguintes são sempre nesta ordem... de mais 'novos' até o mais 'antigo'.

2.2 Implementação de Pilhas

Como lista Sequencial ou Encadeada ?

No caso geral de listas ordenadas, a maior vantagem da alocação encadeada sobre a sequencial - se a memória não for problema - é a eliminação de deslocamentos na inserção ou eliminação dos elementos. No caso das pilhas, como essas operações de deslocamento não ocorrem (pois todas as operações são  baseadas somente no topo da lista), podemos dizer que a alocação sequencial é mais vantajosa na maioria das vezes.

2.3 Um exemplo prático de aplicação de Pilha: Notação Polonesa para Cálculos (calculadoras científica tipo HP)

Um bom exemplo de como alguns programas utilizam Estruturas de Dados tipo Pilha pode ser demonstrado com, por exemplo, a 'Notação Polonesa', método para representação de expressões aritméticas que torna possível o cálculo no ponto de vista computacional. 

A notação tradicional ('humana' ou 'infix') é inviável no ponto de vista computacional: ((A*B)-(C/D)). Por este motivo, foi criada a Notação Polonesa, que 'empilha' operandos até encontrar um operador (Notação Polonesa 'reversa' ou 'posfix'):   A B * C D / -        

Desta forma, a avaliação de expressões aritméticas poderia se dar da seguinte forma:

     programa fonte - notação infix: x := A / B + D * E - A
     objetivo- notação posfix: x := A B / D E * + A -

O algoritmo para a avaliação de Expressões PosFix poderia ser o seguinte:

     empilha operandos até encontrar um operador
     retira o número de operandos; calcula e empilha o valor resultante
     até que chegue ao final da expressão

Vamos testar o algoritmo acima. Considerando que:
A = 4
B = 2

D = 3
E = 3

E a expressão fosse:
    programa fonte - notação infix:     x := A / B + D * E - A        (resultado = 7)

Agora com a Notação Polonesa:
    notação posfix:                 x := A  B  /  D  E  *  +   A  - 
teríamos:                                                 2           9   11      7         (resultado correto)

O mesmo exemplo mostrado 'graficamente': A B / D E * + A -

 

2.4  Implementação de um programa em Pascal para armazenamento de dados com Pilha

program testa_pilha;

uses wincrt;  (* ou, dependendo do compilador, uses crt *)

const m=7;

const sucesso=1;

      pilha_cheia=2;

      pilha_vazia=3;

type tipo_nodo=integer;

pilha=record      

        topo:byte;

        elem:array[1..m] of tipo_nodo;

      end;

var p:pilha;

    ch:char;

    valor:tipo_nodo;

    erro:byte;

    cont:integer;

(*cria a pilha*)

procedure cria_pilha(var p:pilha);

 begin

  p.topo:=0;

 end;

(*push*)

function push(var p:pilha;i:tipo_nodo):byte;

 begin

  if p.topo=m then

   push:=pilha_cheia

  else

   begin

    p.topo:=p.topo+1;

    p.elem[p.topo]:=i;

    push:=sucesso;

   end;

 end;

(*pop*)

function pop(var p:pilha;var i:tipo_nodo):byte;

 begin

  if p.topo=0 then

   pop:=pilha_vazia

  else

   begin

    i:=p.elem[p.topo];

    p.topo:=p.topo-1;

    pop:=sucesso;

   end;

 end;

(*consulta a pilha*)

function consulta_pilha(var p:pilha;var j:tipo_nodo):byte;

 begin

  if p.topo=0 then

   consulta_pilha:=pilha_vazia

  else

   begin

    j:=p.elem[p.topo];

    consulta_pilha:=sucesso;

   end;

 end;

(*imprimir erro*)

procedure imprime_erro(erro:byte);

 begin

  case erro of

   pilha_cheia:writeln('Erro: Pilha Cheia!');

   pilha_vazia:writeln('Erro: Pilha Vazia!');

  end;

  readln;

 end;

(*Programa Principal*)

begin

 cria_pilha(p);

 repeat

  clrscr;

  write('[P]ush, p[O]p, [C]onsultar ou [F]im  -->   <--');

   for cont:=1 to p.topo do

    begin

     gotoxy(3,3+cont);

     writeln(cont,'-> | ',p.elem[cont],' |');

    end;

   gotoxy(42,1);

   repeat

    ch:=upcase(readkey);

   until ch in ['P','O','C','F'];

  if ch='P' then

   begin

    gotoxy(1,2);

    write('Valor: ');

    readln(valor);

   end;

  case ch of

   'P':begin

        erro:=push(p,valor);

        if erro<>sucesso then

         imprime_erro(erro);

       end;

   'O':begin

       erro:=pop(p,valor);

       if erro<>sucesso then

        imprime_erro(erro)

       else

        begin

         gotoxy(1,2);

         writeln('Valor: ',valor);

         readln;

        end;

       end;

   'C':begin

       erro:=consulta_pilha(p,valor);

       if erro<>sucesso then

        imprime_erro(erro)

       else

        begin

         gotoxy(1,2);

         writeln('Valor: ',valor);

         readln;

        end;

       end;

  end;

 until ch='F';

end.

3 Fila
* Estruturas de Dados tipo FIFO (First In First Out) (o primeiro a entrar é o primeiro a sair)

3.1 Conceito

É uma Lista Linear na qual as inserções são feitas no FIM e as exclusões e consultas no INÍCIO da Fila.

              ( a1, a2  , ..., an)

3.2 Implementação Sequencial de Fila

Definição da Estrutura de Dados:

const m=7;

type tipo_nodo=integer;

fila=record
            primeiro:byte;
            ultimo:byte;
            elem:array[1..m] of tipo_nodo;
        end;

var f:fila; 

Exemplo de implementação (em Pascal) de uma estrutura FIFO (Fila), utilizando uma Lista Sequencial Estática

program filavet;

uses wincrt;

const m=7;

const sucesso=1;

      fila_cheia=2;

      fila_vazia=3;

type tipo_nodo=integer;

fila=record

      primeiro:byte;

      ultimo:byte;

      elem:array[1..m] of tipo_nodo;

      end;

var f:fila;

    ch:char;

    valor:tipo_nodo;

    erro:byte;

    cont:integer;

(*cria a fila*)

procedure cria_fila(var f:fila);

 begin

  f.primeiro:=1;

  f.ultimo:=0;

 end;

(*push*)

function push(var f:fila;i:tipo_nodo):byte;

 begin

  if f.ultimo=m then

   push:=fila_cheia

  else

   begin

    f.ultimo:=f.ultimo+1;

    f.elem[f.ultimo]:=i;

    push:=sucesso;

   end;

 end;

(*pop*)

function pop(var f:fila):byte;

 begin

  if f.ultimo<f.primeiro then

   pop:=fila_vazia

  else

   begin

    f.primeiro:=f.primeiro+1;

    pop:=sucesso;

   end;

 end;

(*consulta a fila*)

function consulta_fila(var f:fila;var j:tipo_nodo):byte;

 begin

  if f.ultimo=0 then

   consulta_fila:=fila_vazia

  else

   begin

    j:=f.elem[f.primeiro];

    consulta_fila:=sucesso;

   end;

 end;

(*imprimir erro*)

procedure imprime_erro(erro:byte);

 begin

  case erro of

   fila_cheia:writeln('Erro: fila Cheia!');

   fila_vazia:writeln('Erro: fila Vazia!');

  end;

  readln;

 end;

(*Programa Principal*)

begin

 cria_fila(f);

 repeat

  clrscr;

  write('[P]ush, p[O]p, [C]onsultar ou [F]im  -->   <--');

   for cont:=f.primeiro to f.ultimo do

   begin

     gotoxy(3,3+cont);

     writeln(cont,'-> | ',f.elem[cont],' |');

   end;

   gotoxy(42,1);

   repeat

    ch:=upcase(readkey);

   until ch in ['P','O','C','F'];

  if ch='P' then

   begin

    gotoxy(1,2);

    write('Valor: ');

    readln(valor);

   end;

  case ch of

   'P':begin

        erro:=push(f,valor);

        if erro<>sucesso then

         imprime_erro(erro);

       end;

   'O':begin

        erro:=pop(f);

        if erro<>sucesso then

           imprime_erro(erro);

       end;

   'C':begin

       erro:=consulta_fila(f,valor);

       if erro<>sucesso then

        imprime_erro(erro)

       else

        begin

         gotoxy(1,2);

         writeln('Valor: ',valor);

         readln;

        end;

       end;

  end;

 until ch='F';

end.

3.3 Implementação Encadeada de Fila

Definição da Estrutura de Dados

  Type tpont    = ^reg_fila;
       fila     = tpont;
       reg_fila = record
                    info: TipoElem;
                    lig: tpont;
                  End;

  Var Começo, Fim: fila;

3.4 Problema na Implementação com Fila

O que acontece com a fila considerando a seguinte sequência de operações sobre um fila:

 IEIEIEIEIE. (I - inserção e E - eliminação)

A fila terá sempre 1 ou 0 elementos, no entanto num certo instante:

Ou seja, apenas um elemento na fila, o qual ocupa a última posição do array!
Na próxima inserção, teremos uma condição de overflow e a fila está vazia !

Alternativa: no algoritmo de eliminação após a atualização de Começo, verificar se a fila ficou
vazia, i.e, Começo = Fim; se este for o caso, reinicializar Começo = Fim := 0;

Portanto, ficaria:

  Procedure Eliminar (Var Começo, Fim: indice);
  Begin
  If ( Começo = Fim) Then
    {FILA VAZIA}
  Else
    Begin
      Começo := Começo + 1;
      If Começo = Fim Then
        Begin
          Começo := 0;
          Fim := 0;
         End;
    End;
  End;

O que aconteceria se a sequência fosse IIEIEIEIEI...

A lista estaria com no máximo dois elementos, mas ainda ocorreria overflow com a lista quase
vazia.

Alternativa:Forçar Fim a usar o espaço liberado por Começo (Fila Circular)
 

3.5 Fila Circular

Fila Circular Implementada como Anel:

Exemplo de implementação (em Pascal) de uma estrutura FIFO (Fila) CIRCULAR, utilizando uma Lista Sequêncial Estática:

Program Fila_Circular;

uses wincrt;

const m=7;

      SUCESSO=1;

      FILA_CHEIA=2;

      FILA_VAZIA=3;

type tipo_nodo=integer;

     Fila = Record

                primeiro:byte;

                ultimo:byte;

                tamanho:byte;

                elem: array[1..m] of tipo_nodo;

            end;

var F:Fila;

    Ch:Char;

    I,Erro:byte;

    valor:tipo_nodo;

(*----------------------- Cria Fila Circular *)

Procedure Cria_Fila_Circular(var f:Fila);

Begin

   f.primeiro:=1;

   f.ultimo:=0;

   f.tamanho:=0;

end;

(*----------------------- Insere na Fila Circular *)

Function Insere_Fila_Circular(var f:Fila; i:tipo_nodo):Byte;

Begin

   if f.tamanho = m then

      Insere_Fila_Circular:=FILA_CHEIA

   else

      Begin

         f.tamanho:=f.tamanho+1;

         f.ultimo:=(f.ultimo MOD m)+1;    {MOD retorna o RESTO de uma divisao. Enquanto f.ultimo for menor q M, retorna o proprio f.ultimo}

         gotoxy (1,22);write ('Calculo ==> (f.ultimo MOD m) = ',f.ultimo,' (Pressione <qualquer tecla> para continuar!)');readln;

         f.elem[f.ultimo]:=i;

         Insere_Fila_Circular:=SUCESSO;

      end;

end;

(*----------------------- Exclui da Fila Circular *)

Function Exclui_Fila_Circular(var f:Fila):Byte;

Begin

   if f.tamanho = 0 then

        Exclui_Fila_Circular:=FILA_VAZIA

   else

        Begin

          f.elem[f.primeiro]:=0;    {sobrescreve valor antigo com 0}

          f.tamanho:=f.tamanho -1;  {diminui numero de posicoes ocupadas na Fila}

          f.primeiro:=(f.primeiro MOD m)+1;  {calcula nova posicao do primeiro. Quando f.primeiro for 7, resultará 0, fazendo a Fila circular.}

          Exclui_Fila_Circular:=SUCESSO;

   end;

end;

(*----------------------- Consulta Fila Circular *)

Function Consulta_Fila_Circular(f:Fila; var j:tipo_nodo):Byte;

Begin

   Consulta_Fila_Circular:=SUCESSO;

   if f.tamanho = 0 then

        Consulta_Fila_Circular:=FILA_VAZIA

   else

        j:=f.elem[f.primeiro];

end;

(*----------------------- Programa Principal *)

Begin

   Cria_Fila_Circular(F);

   for i:=1 to m do

       f.elem[i]:=0;

   Repeat

       ClrScr;

       Write('Lista Circular: ');

       for i:=1 to m do

           Write(f.elem[i],'');

       WriteLn;

       Write('[I]ncluir, [E]xcluir, [C]onsultar ou [F]im? ');

       Repeat

           Ch:=UpCase(ReadKey);

       Until Ch IN ['I','E','C','F'];

       if Ch='I' then

       Begin

          GotoXY(1,3);

          Write('Valor: ');

          ReadLn(valor);

       End;

       Case Ch

       Of

       'I':Erro:=Insere_Fila_Circular(F,valor);

       'E':Erro:=Exclui_Fila_Circular(F);

       'C':Begin

             Erro:=Consulta_Fila_Circular(F,valor);

             If Erro=SUCESSO then

               Begin

                  GotoXY(1,4);

                  WriteLn('Valor Consultado: ',valor);

                  ReadLn;

               end;

           end;

      end;

      if(Erro<>SUCESSO) and (Ch<>'F') then

      Begin

          GotoXY(1,5);

          Case Erro

          Of

            FILA_CHEIA:WriteLn('ERRO: Lista Cheia');

            FILA_VAZIA:WriteLn('ERRO: Lista Vazia');

          end;

          ReadLn;

      end;

  Until Ch = 'F';

end.

3.6 Uma Lista (tipo Pilha) com Acessos nas 2 extremidades: DEQUE - Double Ended QUEue

É uma Lista de duas extremidades, onde as inserções, consultas e retiradas são permitidas nas duas extremidades (Double Ended QUEue).

É uma alternativa à Pilha tradicional (com uma só extremidade), permitindo, desta forma, simular a existência de 2 Pilhas, mas na realidade controlando uma só estrutura física e lógica na memória.

Exemplo de implementação (em Pascal) de uma Lista tipo DEQUE:

Program Testa_Deque;

Uses WinCrt;

Const m = 9;

      SUCESSO = 1;

      DEQUE_CHEIO_ESQUERDA= 2;

      DEQUE_CHEIO_DIREITA = 3;

      DEQUE_VAZIO = 4;

Type Tipo_Nodo = Integer;

     Deque = Record

                 esq, dir: Byte;

                 v: Array [1..m] Of Tipo_Nodo;

             End;

Var D : Deque;

    Valor: Tipo_Nodo;

    Ch, Op: Char;

    Erro: Byte;

(*---------------------------Cria_Deque*)

Procedure Cria_Deque (Var d: Deque);

Begin

    d.esq := 0;

    d.dir := 0;

End;

(*---------------------------Insere_Esquerda*)

Function Insere_Esquerda (Var d: Deque; no: Tipo_Nodo): Byte;

Begin

    Insere_Esquerda := SUCESSO;

    If d.esq = 1 Then

         Insere_Esquerda := DEQUE_CHEIO_ESQUERDA

    Else

       Begin

           If d.esq = 0 Then

               Begin

                   d.esq := (m DIV 2) + 1;

                   d.dir := d.esq;

                   gotoxy (01,20);

                   write ('Valor do d.esq (posicao esquerda) calculado: ', d.esq);

               End

           Else

               Begin

                   d.esq := d.esq -1;

                   gotoxy (01,20);

                   write ('Valor do d.esq (posicao esquerda) calculado: ', d.esq);

               End

           ;

           d.v [d.esq] := no;

       End;

End;

(*---------------------------Insere_Direita*)

Function Insere_Direita (Var d: Deque; no: Tipo_Nodo): Byte;

Begin

    Insere_Direita := SUCESSO;

    If d.dir = m Then

         Insere_Direita := DEQUE_CHEIO_DIREITA

    Else

       Begin

           If d.dir = 0 Then

               Begin

                   d.dir := (m DIV 2) + 1;

                   d.esq := d.dir;

                   gotoxy (01,20);

                   write ('Valor do d.dir (posicao direita) calculado: ', d.dir);

               End

           Else

               Begin

                   d.dir := d.dir + 1;

                   gotoxy (01,20);

                   write ('Valor do d.dir (posicao direita) calculado: ', d.dir);

               End

           ;

           d.v [d.dir] := no;

       End;

End;

(*---------------------------Retira_Esquerda*)

Function Retira_Esquerda (Var d: Deque; Var no: Tipo_Nodo): Byte;

Begin

    If d.esq = 0 Then

         Retira_Esquerda := DEQUE_VAZIO

    Else

       Begin

           no := d.v [d.esq];

           d.esq := d.esq + 1;

           If d.esq > d.dir Then

               Cria_Deque (d);

           Retira_Esquerda := SUCESSO;

       End;

End;

(*---------------------------Retira_Direita*)

Function Retira_Direita (Var d: Deque; Var no: Tipo_Nodo): Byte;

Begin

    If d.dir = 0 Then

         Retira_Direita := DEQUE_VAZIO

    Else

       Begin

           no := d.v [d.dir];

           d.dir := d.dir - 1;

           If d.dir < d.esq Then

               Cria_Deque (d);

           Retira_Direita := SUCESSO;

       End;

End;

(*--------------------------Consulta_Esquerda*)

Function Consulta_Esquerda (d: Deque; Var no: Tipo_Nodo): Byte;

Begin

    If d.esq = 0 Then

         Consulta_Esquerda := DEQUE_VAZIO

    Else

       Begin

           no := d.v [d.esq];

           Consulta_Esquerda := SUCESSO;

       End;

End;

(*---------------------------Consulta_Direita*)

Function Consulta_Direita (d: Deque; VAr no: Tipo_Nodo): Byte;

Begin

    If d.dir = 0 Then

         Consulta_Direita := DEQUE_VAZIO

    Else

       Begin

           no := d.v [d.dir];

           Consulta_Direita := SUCESSO;

       End;

End;

(*---------------------------Lista_Deque*)

Procedure Lista_Deque (d: Deque);

Var i: Byte;

Begin

    If d.esq <> 0 Then

         Begin

             gotoxy (5,10);

             Write ('SITUACAO DO DEQUE: ');

             For i := d.esq To d.dir Do

                Write (d.v [i]:2, '');

         End;

End;

(*-----------------------------Exibe_erro*)

Procedure Exibe_Erro (erro: Byte);

Begin

    WriteLn;

    Write ('ERRO:');

    Case erro Of

        DEQUE_CHEIO_ESQUERDA: WriteLn ('Deque Cheio a Esquerda');

        DEQUE_CHEIO_DIREITA: WriteLn ('Deque Cheio a Direita');

        DEQUE_VAZIO: WriteLn ('Deque Vazio');

    End;

End;

(*-----------------------------Programa Principal*)

Begin

    Cria_Deque (D);

    Repeat

         ClrScr;

         Write ('[I]nsere, [R]etira, [C]onsulta ou [F]im: ');

         Repeat

              Op := UpCase (ReadKey);

         Until Op IN ['I', 'R', 'C', 'F'];

         If Op IN ['I', 'R', 'C'] Then

               Begin

                  WriteLn;

                  Write ('[E]squerda ou [D]ireita: ');

                  Repeat

                       Ch := UpCase (ReadKey);

                  Until Ch IN ['E', 'D'];

                  WriteLn;

                  Case Op Of

                       'I': Begin

                                Write ('Valor: ');

                                ReadLn (Valor);

                                If Valor <> 0 Then

                                     Case Ch Of

                                         'E': Erro := Insere_Esquerda (D, Valor);

                                         'D': Erro := Insere_Direita (D, Valor);

                                     End;

                             End;

                       'R': Begin

                                Case Ch Of

                                     'E': Erro := Retira_Esquerda (D, Valor);

                                     'D': Erro := REtira_Direita (D, valor);

                                End;

                                If Erro = SUCESSO Then

                                     WriteLn ('Valor Retirado: ', Valor);

                             End;

                       'C': Begin

                                Case Ch Of

                                     'E': Erro := Consulta_Esquerda (D, Valor);

                                     'D': Erro := Consulta_Direita (D, Valor);

                                End;

                                If Erro = SUCESSO Then

                                     WriteLn ('Valor Consultado: ', Valor);

                             End;

                  End;

                  If Erro <> SUCESSO Then

                        Exibe_Erro (Erro)

                  Else

                     Lista_Deque (D);

                  ReadLn;

               End;

    Until Op = 'F';

    End.

Revisão sobre Fila, Pilha e Deque:

Trabalho sobre Árvores:

01) Crie (na forma tradicional: em forma de árvore) uma Árvore Binária de Busca, com 
altura/nível 5 (determine qualquer tipo de valor). OBS: considere que a raiz possua nível 1.
02) Represente a mesma árvore utilizando agora a representacao 'ligada' (pág 5 arquivo 
'arvores_e_binarias.pdf - prof. Fábio).
03) Percorra (leia) a árvore nos 3 tipos de acessos tradicionais.

• T = 0 e a árvore é dita vazia ou
• existe um nó especial r, chamado raiz de T, os restantes podem ser divididos em dois subconjuntos disjuntos, Tre e Trd, que são as subárvores esquerda e direita de r, respectivamente e as quais, por sua vez, também são árvores binárias.

Definição da Estrutura de Dados

  Type
    PNo = ^no;
    no = record
            info: Telem;
            esq, dir: PNo;
         End;

  Type tree: PNo;

Operações associadas a árvore binária padrão:

1. Define uma árvore vazia
Define uma árvore vazia e deve ser utilizado antes de qualquer outro.

  Procedure Define(var t: tree);
  Begin
    t:=nil;
  End;

2. Cria um nó raiz
Retorna o nó raiz da árvore em t

  Procedure Cria_Raiz(var t: tree; item: Telem);
  Var no: tree;
  Begin
    new(nó);
    no^.esq:=nil;
    no^.dir:=nil;
    no^.info:=item;
    t:=no;
  End;

3. Verifica se árvore vazia ou não
Retorna true se árvore vazia, false c.c.

  Function Vazia (t:tree):boolean;
  Begin
    vazia:=(t=nil);
  End;

4. Criar um filho à direita de um dado nó

• Busca elemento contendo Item_Pai
• Se Item_Pai ainda não possui filho à direita, então cria um filho à sua direita com o conteúdo de item.

  Procedure Adicionar_Dir(t: tree; item_pai, item: Telem)

  Var pai,
      no: tree;
  Begin
    pai:=Localiza(t,item_pai);
    If(pai<>nil) Then
      If (pai^.dir<>nil) Then
        erro("item já possui subárvore direita")
      Else
        Begin
          New(nó);
          no^.esq:=nil;
          no^.dir:=nil;
          no^.info:=item;
          pai^.dir:=nó;
        End;
  End;

5. Criar um filho à esquerda de um dado nó

  Procedure Adicionar_Dir(t: tree; item_pai, item: Telem)

  Var pai,
      no: tree;
  Begin
    pai:=Localiza(t,item_pai);
    If(pai<>nil) Then
      If (pai^.esq<>nil) Then
        erro("item já possui subárvore direita")
      Else
        Begin
          New(nó);
          no^.esq:=nil;
          no^.dir:=nil;
          no^.info:=item;
          pai^.esq:=nó;
        End;
  End;

6. Verificar qual o nível de um dado nó

• Retorna o nível onde está um nó com item pesquisado
• Se item não existe retorna zero

  Function Nível (t: tree; item: Telem): integer;
  Var p: integer;

    Procedure Travessia (ptr: tree; niv: integer);
    Begin
      If ptr<>nil Then
	Begin
          niv:=niv+1;
          If Igual(ptr^.info, item) Then 
            p:=niv;
          Else
            Begin
              Travessia(ptr^.esq, niv);
              If p=0 Then
                Travessia(ptr^.dir, niv);
            End;
        End;
    End;

  Begin   {nivel}
    p:=0;
    Travessia(t,p);
    nivel:=p;
  End;

7. Retornar o pai de um dado nó

• Dado um item, procura se item existe na árvore
• Caso positivo retorna o conteúdo do pai do nó

  Function Pai(t: tree; item:Telem):Telem;
  Var achou: boolean;
      it : Telem;

    Procedure Travessia(t: tree; var it: Telem);
    Begin
      If not Vazia(t) Then
        Begin
          If t^.esq<>nil Then
            If Igual(item, t^.esq^.info) Then
              Begin
                achou:=true;
                it:=t^.info;
              End;
          If not achou Then
            If t^.dir<>nil Then
              If Igual(item, t^.dir^.info) Then
                Begin
                  achou:=true;
                  it:=t^.info;
                End;
          If not achou Then
            Travessia(t^.esq, it);
          If not achou Then
            Travessia(t^.dir, it);
        End;
    End;   {Travessia}

  Begin {pai}
    If t<>nil Then
      Begin
        achou:=false;
        If Igual(item, t^.info) Then
          pai:=t^.info;   {pai do raiz é ele próprio}
        Else
          Begin
            Travessia(t,it);
            pai:=it;
          End;
      End;
  End;