Travessia em Pré-Ordem

1. se árvore vazia; fim
2. visitar o nó raiz
3. percorrer em pré-ordem a subárvore esquerda
4. percorrer em pré-ordem a subárvore direita

Pré-ordem:

• ABDCEGFHI
• visita o nó quando passar a sua esquerda
• notação pré-fix
• Exercício: aplique para a expressão aritmética ilustrada anteriormente

Travessia em In-Ordem

1. se árvore vazia, fim
2. percorrer em in-ordem a subárvore esquerda
3. visitar o nó raiz
4. percorrer em in-ordem a subárvore direita

• DBAEGCHFI
• visita o nó quando passar embaixo do nó
• notação in-fix
• Exercício: aplique para a expressão aritmética ilustrada anteriormente

Travessia em Pós-Ordem

1. se árvore vazia, fim
2. percorrer em Pós-Ordem a subárvore esquerda
3. percorrer em Pós-Ordem a subárvore direita
4. visitar o nó raiz

• DBGEHIFCA
• visita o nó quando passar a sua direita
• notação pós-fix
• Exercício: aplique para a expressão aritmética ilustrada anteriormente

Algoritmos de Percurso - versão recursiva

  
  Procedure PreOrdem(N:tree);
  Begin
    If N <> nil Then
      Begin
        Processa(N); {p. ex. imprime}
        PreOrdem(N^.esq);
        PreOrdem(N^.dir);
      End;
  End;

  
  Procedure InOrdem(N:tree);
  Begin
    If N <> nil Then
      Begin
        InOrdem(N^.esq);
        Processa(N); {p. ex: imprime}
        InOrdem(N^.dir);
      End;
  End;

  
  Procedure PosOrdem(N:tree)
  Begin
    If N <> nil Then
      Begin
        PosOrdem(N^.esq);
        PosOrdem(N^.dir);
        Processa(N); {p.ex.: imprime}
      End;
  End;

Operações Facilitadas pelos Algoritmos de Percurso:

• retorna true se elemento está na árvore
• árvore binária comum (não é ABBusca)
• sem sentinela

  Function Esta_Presente(t: tree; item: Telem): boolean;
  Begin
    Esta_Presente:= busca(t, item) <> nil;
  End;

• Busca declarada apenas na implementation: Esta_Presente é disponível na interface
• Retorna nil se elemento não encontrado
• Usa Pós-Ordem para percorrer a árvore - visita equivale à verificar se elemento é encontrado

  Function Busca(t:tree; item: Telem): Tree;
  Var
    achou: boolean;
    ptr: tree;

  Procedure Pós-Ordem(t:tree; var prt:tree; var achou:boolean);
  Begin
    If (t<>nil) and (not achou) then
      Begin
        Pós-Ordem(t^.esq,ptr,achou);
        if not achou then Pós-Ordem(t^.dir,ptr,achou);

        If not achou then
            If Igual(item, t^.info) Then
            Begin
              achou:=true;
              ptr:=t;
            End;
      End;
  End;     {Pós-Ordem}

  Begin    {busca}
    achou:=false;
    ptr:=nil;
    Pós-Ordem(t,ptr,achou);
    busca:=ptr;
  End;     {busca}

• Utiliza implicitamente percurso em Pré-Ordem

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

    Function Local(t: tree; item: Telem; var achou:boolean):tree;
    Begin
      If not vazia (t) then
        If t^.info=item then local:=t;
        Else
          Begin
            local:=local(t^.esq, item, achou);
            If not achou Then 
              local=local(t^.dir, item, achou);
          End;
    End;        {local}

  Begin         {busca1}
    busca1:= nil;

    busca1:=local(t, item, achou);
  End;

• Desaloca todo o espaço de memória da árvore e retorna a árvore ao estado equivalente ao define, isto é, nula.
• Utiliza o algoritmo de Pós-Ordem para percurso

  Procedure Tornar_Vazia(var t: tree);

  Begin
    If not Vazia(t) Then
      Begin
        Tornar_Vazia(t^.esq);
        Tornar_Vazia(t^.dir);
        Dispose(t);
       End;
    t:=nil;
  End;

Exercícios

Árvore Balanceada

Índice