Prev Up Next
Go backward to Várias implementações do "stack"
Go up to Alguns exercícios a exemplos dados nas aulas teóricas
Go forward to Manipulação de bits

Usando uma árvore binária de pesquisa para ordenar um vector

Noção de árvore binária (definição indutiva): ou é nula ou é da forma:

(árvore binária, raiz, árvore binária)

Modos de visita:

Um modo de ordenar vectores:

  1. Inserir os elementos a ordenar numa árvore binária.
  2. Listar a árvore em-ordem.
typedef struct no{
  int valor;
  struct no *esq;
  struct no *dir;
} NO, *ARVORE;

/* insert: Arv x N -> Arv       */
ARVORE insert(int,ARVORE);    
void em_ordem(ARVORE);
/* Exemplo:                     */
int v[]={55,12,88,3,21,4};    

main()
{
  ARVORE a=0;
  int i;
  for(i=0;i<6;i++)
    a=insert(v[i],a);
  em_ordem(a);
}
/*----------------------------------------------------------*/
ARVORE insert(int x,ARVORE a)
{
  if(a==0){
    ARVORE nova;
    nova=(ARVORE)malloc(sizeof(NO));
    nova->valor = x;
    nova->esq   = 0;
    nova->dir   = 0;
    return(nova);
  }
  if(x <= a->valor){
    a->esq = insert(x,a->esq);
    return(a);
  }
  a->dir = insert(x,a->dir);
  return(a);
}

/*----------------------------------------------------------*/
void em_ordem(ARVORE a)
{
  if(a==0)
    return;
  em_ordem(a->esq);
  printf(" %d ",a->valor);
  em_ordem(a->dir);
}

Prev Up Next