Para a manipulação de árvores binárias, é necessário a  implementação
das seguintes rotinas:

        * VisitaArvore ();
        * AdicionaNo ();
        * NoSucessor ();
        * NoPai ();
        * ExcluiNo ();

	1)   VisitaArvore:  esta  é  uma  rotina  recursiva  que  pode  ser
"in-order", "pos-order" ou "pre-order". Esses termos dizem respeito à ordem
com que os nós são visitados:

	VisitaPreOrder (No: Raiz)
	.	se Raiz = NULL então retorna
	.	ProcessaNo (Raiz)
	.	VisitaPreOrder (Raiz.LinkEsquerdo)
	.	VisitaPreOrder (Raiz.LinkDireito)
	fim

	VisitaPosOrder (No: Raiz)
	.	se Raiz = NULL então retorna
	.	VisitaPosOrder (Raiz.LinkEsquerdo)
	.	VisitaPosOrder (Raiz.LinkDireito)
	.	ProcessaNo (Raiz)
	fim

	VisitaInOrder (No: Raiz)
	.	se Raiz = NULL então retorna
	.	VisitaInOrder (Raiz.LinkEsquerdo)
	.	ProcessaNo (Raiz)
	.	VisitaInOrder (Raiz.LinkDireito)
	fim

        A rotina "VisitaInOrder" é a mais importante pois essa visita os  nós
em ordem crescente independentemente de sua  disposição na  árvore. A  rotina
"VisitaPosOrder"  também é muito importante,  pois  visita  os  nós  do  mais
distante ao mais próximo da raiz, o que é utilizado para desalocar a  memória
utilizada pelos nós. A função "ProcessaNo" é uma função abstrata que pode ser
qualquer coisa que seja necessária, como por  exemplo,  mostrar a  informação
guardada no nó.


        2) AdicionarNó: Esta função deve  encontrar um nó que possa  "adotar"
o nó a ser guardado na árvore e guardá-lo:

	AdicionarNó (Dado: X; No: Raiz)
	.	Nó: Pai, Filho
	.
	.	(procura do nó que vai receber X como filho)
	.	Filho = Raiz
	.	Enquanto Filho <> NULL faça
	.	.	Pai = Filho
	.	.	se X <= Pai.Dado então
	.	.		Filho = Pai.LinkEsquerdo
	.	.	senão
	.	.		Filho = Pai.LinkDireito
	.	Fim_Enquanto
	.
	.	(Nó é requisitado e adotado por PAI)
	.	Filho = RequisitaNo ()
	.	se X <= Pai.Dado então
	.		Pai.LinkEsquerdo = Filho
	.	senão
	.		Pai.LinkDireito = Filho
	fim

        3) NóSucessor:  Esta  rotina  procura o sucessor, ou seja, o menor nó
de informação maior a de um  determinado  nó.  Esse  nó,  devido à forma  que
é construída a árvore, é o nó mais à esquerda dos nós que estão à direita  do
nó a que estamos nos referindo. Confuso? Pense um pouco sobre isso analisando
a figura e depois construa você mesmo uma árvore em um papel.

	(retorna o sucessor de X ou X, caso X não tenha sucessor)
	Nó: NóSucessor (Nó: X)
	.	Nó: Pai, Filho
	.
	.	Pai = X
	.	X = Pai.LinkDireito
	.	Enquanto Filho <> NULL faça
	.	.	Filho = Pai.LinkEsquerdo
	.	Fim_Enquanto
	.	retorna Pai
	fim

        4) NóPai: Esta rotina procura o pai de um determinado nó:

	(procura o pai de X a partir de uma determinada Raiz)
	Nó: NóPai (Nó: X, Raíz)
	.	se Raíz = NULL então retorna NULL
	.	se (Raiz.LinkEsquerdo = X) ou (Raiz.LinkDireito = X)
	.		então retorna Raiz
	.	se Raíz.Dado <= X.Dado então
	.		retorna NóPai (X, Raiz.LinkEsquerdo)
	.	senão
	.		retorna NóPai (X, Raiz.LinkDireito)
	fim		

        ExcluirNó: Esta, que é a rotina mais coplexa de todas as demonstradas
nesta  seção,  exclui,  mas  não  destroi  um  determinado  nó.  Ela  retorna
o seu  endereço, para que a rotina que a evocou possa excluir ou  mover  esse
nó. Existem 3 possibilidades:

        * X ser um nó folha. Aí a exclusão é muito  simples: basta fazer  com
que seu pai não faça referência a ele mais.
        * X ter apenas um filho. Nesse caso, o seu pai "adota" seu filho.
        * X tem dois filhos. Aí o seu sucessor deve ser excluído  da  árvore,
ser adotado pelo pai de X e adotar os filhos de X.

	Nó: ExcluiNó (Nó: X, Raiz)
	.	Nó: Pai, Filho, Sucessor
	.
	.	Pai = NóPai (X, Raiz)
	.
	.	(se X for um nó-folha...)
	.	se (X.LinkEsquerdo = NULL) e (X.LinkDireito = NULL) então
	.	.	se Pai.LinkExquerdo = X então
	.	.		Pai.LinkEsquerdo = NULL
	.	.	senão
	.	.		Pai.LinkDireito = NULL
	.	.	retorna X
	.	fim_se
	.
	.	(se X tiver apenas um filho...)
	.	se (X.LinkEsquerdo = NULL) ou (X.LinkDireito = NULL) então
	.	.
	.	.	(descobre quem é o único filho de X)
	.	.	se X.LinkEsquerdo = NULL então
	.	.		Filho = X.LinkDireito		
	.	.	senão
	.	.		Filho = X.LinkEsquerdo
	.	.
	.	.	(o Pai de X adota seu filho)
	.	.	se Pai.LinkExquerdo = X então
	.	.		Pai.LinkEsquerdo = Filho
	.	.	senão
	.	.		Pai.LinkDireito = Filho
	.	.
	.	.	retorna X
	.	fim_se
	.
	.	(se X tiver dois filhos...)
	.	Sucessor = NóSucessor (X)
	.	ExcluirNó (Sucessor, Raiz)
	.
	.	(o pai de X adota o Sucessor)
	.	se Pai.LinkExquerdo = X então
	.		Pai.LinkEsquerdo = Sucessor
	.	senão
	.		Pai.LinkDireito = Sucessor
	.
	.	(o Sucessor adota os filho de X)
	.	Sucessor.LinkEsquerdo = X.LinkEsquerdo
	.	Sucessor.LinkDireito = X.LinkDireito
	.
	.	retorna X
	fim

        Note que este algoritmo não verifica condições de erro e nem se o  nó
a ser excluído é a raiz. Note também que esta última rotina  evoca a si mesma
para excluir o nó Sucessor, por isso a tarefa de  desalocar o  nó excluído  é
atribuída à rotina que a chamou, um nível acima.


        Este  tipo  de estrutura, em  condições  ótimas, é muito  eficiente e
muito rápido, se  comparado à  estruturas  lineares. A  profundidade  de  uma
árvore binária é dada por P = log2 (T+1)-1, ou seja, se uma árvore tiver, por
exemplo, 63 nós, qualquer nó procurado estará no máximo a 5 nós da raiz.  Mas
para que isso aconteça, é necessário que a árvore esteja balanceada, ou seja,
é necessário que o número de nós a direita e a esquerda  de  cada nó  seja  o
mesmo ou perto disso. Não é preciso muito esforço mental  para  perceber  que
uma árvore binária desbalanceada pode se tornar uma lista encadeada  simples.
O que seria desastroso em termos de performance.


        Para saber mais...

------> Exemplo de Árvores Binnárias em Pascal
------> Árvores Binárias - parte #1
------> Pilhas
------> Recursividade