Uma árvore binária (chamada de binária pois de cada nó podem nascer até 2 novos nós) é uma estrutura de dados caracterizada por:
- Ou não tem elemento algum (árvore vazia).
- Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.

Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.

Uma definição mais concreta
Uma árvore binária (= binary tree) é formada de nós; cada nó tem um certo conteúdo (por exemplo, um número inteiro) e os endereços (das raízes) de duas subárvores: uma esquerda e uma direita.

Eis um exemplo de nó em C:

typedef struct node *link;

struct node{
   int  item;  // conteúdo do nó
   link l, r;  // 'l' de "left" e 'r' de "right"
};

Principais Operações em Árvore Binária!

Termos técnicos importantes
- raiz de uma árvore: primeiro elemento da árvore;
- nó filho / nó pai: o filho é apontado pelo seu pai, então um nó que tem outro nó em seu link direito/esquerdo é pai do nó que está no seu link direito/esquerdo e esse nó por sua vez é filho do dono do link que está apontando para ele;
- folha de uma árvore: um nó folha é um nó sem filhos (seus links são nulos);
- nó interno de uma árvore: é um nó que tem pelo menos um filho;
- nível de um nó: distância dele até a raiz (a raiz está no nível 0), a cada link a distância é aumentada em 1 unidade.

Alguns tipos de árvore (creio que a imagem é auto-explicativa):

Como percorrer uma árvore

O seguinte exemplo é uma versão simplificada do programa 5.14, p.231, do Sedgewick.  Ele imprime o item de cada nó da árvore binária cuja raiz é h (o "h" é inicial de "here").

// Imprime o item de cada nó de uma árvore binária h, que tem nós do tipo node.
void imprime (link h) { 
    if (h == NULL) return;
    printf("%d\n", h->item); 
    imprime(h->l);
    imprime(h->r);
}

Essa função percorre a árvore em ordem raiz-esquerda-direita (= preorder).

Se as três últimas instruções forem trocadas por

    imprime(h->l);
    printf("%d\n", h->item); 
    imprime(h->r);

a árvore será percorrida em ordem esquerda-raiz-direita  (= inorder).

Se as três últimas instruções forem trocadas por

    imprime(h->l);
    imprime(h->r);
    printf("%d\n", h->item); 

a árvore será percorrida em ordem esquerda-direita-raiz  (= posorder).

Principais Operações em Árvore Binária!

Esqueci algo importante sobre as Árvores Binárias? Comente já e assim que possível adicionarei ao post!

Dúvidas, críticas e correções são muito bem-vindas e de extrema importância! Então comente, participe e demonstre seus conhecimentos!

Mais detalhes sobre árvores em:
Wikipédia
IME