Como feito anteriormente com a
lista encadeada e tabela de dispersão, é apresentado aqui uma versão genérica
para árvore binária, seguindo o mesmo padrão de dividir o código em rotinas
primitivas, dependentes da aplicação e o programa exemplo, recomenda-se ler as
postagens sobre noções de árvore, árvore binária, e fica como requisito ler o
exemplo de árvore binária da postagem anterior, nas rotinas aqui utilizadas é
feita a correção quanto ao uso de globais, mantendo o enfoque sempre em montar
módulos.
O arquivo de cabeçalho btgen.h, declara o tipo nó que simbolizam cada elemento dentro
da arvore, cada nó possui um tipo de dado e dois ponteiros usados para apontar
para o elemento direito e esquerdo. Tipo de dado usado é o ponteiro void que consiste no ponteiro genérico
de C, que permite ser moldado através do operador cast para qualquer tipo de dado sem erros, mais a declaração de SLINK como um tipo ponteiro para o nó.
#define RIGHT 0
#define LEFT 1
// tipo de
dados abstrato arvoreh
typedef struct tagSNODE
{
struct tagSNODE *sLink[2]; // ligacaoh das
subarvores
void *pData; // ponteiro
generico de dados
} SNODE;
// define um tipo ponteiro para o noh
typedef SNODE * SLINK;
|
Dentro do mesmo cabeçalho se inclui
o TAD (tipo abstrato de dado) para árvore binária BINTREE, temos o contador de nós e apontamentos para
rotinas especificas, semelhante a maneira feita para lista encadeada, a estrutura ainda contem um nó raiz falso (slkDummyRoot) cujo filho direito é a
verdadeira raiz da árvore, facilita a lógica de programação das rotinas
utilizadas quando o nó raiz tem um pai, vide os problemas relativos a atualizar
o nó raiz na postagem anterior que mostrava um exemplo simples de árvore
binária.
typedef struct tagSBINTREE
{
SLINK slkDummyRoot;
unsigned int uiCount;
void * ( *
fCreateData ) ( void * );
BOOL ( * fDeleteData ) ( void
* );
int ( *
fDuplicatedNode ) ( SLINK, SLINK );
int ( *
fNodeDataCmp ) ( void *, void * );
int iMaxDepth;
char *pPath;
int ( *
fTraversal ) ( void *, void *, int );
}
SBINTREE;
|
Por mais abrangente e genérica
que se possa criar uma função, a árvore binária genérica consegue manipular
apenas as conexões do nó, esse tipo de operação não precisa saber como os dados
se parecem, restando quatro tipos de operações que manipulam os dados
diretamente e dependem do tipo definido. Criar, apagar, comparar e tratar
duplicado são funções que fazem parte do arquivo btapp.c de rotinas especificas da aplicação e passam a integrar a
estrutura de dados lista através dos ponteiros da estrutura mostrada acima.
Foi incluído ainda para parte
especifica uma rotina de travessia para os algoritmos de percorrer a árvore
recursivamente, junto de um indicador da profundidade MaxDepth e o ponteiro pPath para
indicar a percurso , um exemplo de seu uso pode ser visto na rotina PrintForest que imprime a árvore
resultante para auxilio de testes, o uso
desta rotina pode ser descartado.
FUNÇÕES
ESPECIFICAS PARA ÁRVORE BINÁRIA
|
|
Nome
|
Descrição
|
fCreateData
|
Recebe um ponteiro do objeto definido
para a aplicação, espera-se o retorno de um ponteiro para o que venha a ser o
dado armazenado na lista.
|
fDeleteData
|
Recebe um ponteiro do objeto definido
para a aplicação que deve estar armazenado na lista ligada. fDeleteData deve
destruir o objeto
|
fDuplicateNode
|
São passados dois ponteiros. O
primeiro ponteiro é o nó que deve ser adicionado e o segundo é o nó que já se
encontra na lista, mas que é igual(duplicada) a informação do primeiro
ponteiro, retornando:
0 -> destruir duplicada
1 -> adicionar duplicada
|
fNodeDataCmp
|
São passados dois ponteiros do objeto
definido para o dado e deve compara-lo, retornando um numero que é < 0,
zero, ou > 0, dependendo da relação entre o primeiro e segundo objeto.
|
fTraversal
|
São passados dois ponteiros, um para
saída de dados e outro com a entrada de dados, e a indicação de em que nível
a rotina se encontra.
|
Para permitir maior legibilidade
foram feitas as seguintes redefinições:
#define BTRoot (BT->slkDummyRoot)
#define
NodeCount (BT->uiCount)
#define
CreateData (*(BT->fCreateData))
#define
DeleteData (*(BT->fDeleteData))
#define
DuplicatedNode (*(BT->fDuplicatedNode))
#define
NodeDataCmp (*(BT->fNodeDataCmp))
#define Path (BT->pPath)
#define MaxDepth (BT->iMaxDepth)
#define Traversal (*(BT->fTraversal))
|
As rotinas abaixo fazem parte das
primitivas genéricas para árvore binária, tais funções manipulam somente as
ligações do nó, sendo completamente independentes da aplicação e não devem ser
alteradas.
Função
|
CreateBinTree
|
||||||||||
Propósito
|
Cria e inicia uma estrutura de gerenciamento de uma árvore binária
|
||||||||||
Parâmetros
|
ponteiro para as funções especifica da lista
|
||||||||||
Retorno
|
ponteiro SBINTREE
pBT - ponteiro para uma estrutura do tipo árvore
binária inicializada
NULL - não conseguiu
criar a árvore binária
|
||||||||||
Descrição
|
Cria uma estrutura de árvore binária e retorna um ponteiro da mesma.
Em erro, retorna NULL.Esta função aceita ponteiros para as cinco funções
especificas de uma árvore e inicializa a estrutura com elas, aloca o nó que
irá apontar para a raiz da árvore.
|
SBINTREE *CreateBinTree(
void * ( *
fCreateData ) ( void * ),
BOOL ( * fDeleteData ) ( void * ),
int ( *
fDuplicatedNode ) ( SLINK, SLINK ),
int ( *
fNodeDataCmp ) ( void *, void *),
int ( *
fTraversal ) ( void *, void *, int))
{
SBINTREE *pBT;
// aloca uma
estrutura que gerencia uma arvore binaria
pBT = (SBINTREE *) malloc(sizeof(SBINTREE));
if (pBT) { // caso fracasse
em alocar memoria
//
tendo alocado, inicializa as variaveis
pBT->slkDummyRoot = (SLINK)
malloc(sizeof(SNODE));
// naoh
criou o noh raiz falso
if
(pBT->slkDummyRoot == NULL) {
//
libera a estrutura de dados arvore
free(pBT);
return
(NULL); //
indicando o erro
}
//
tendo sucesso na alocacaoh, inicializa as variaveis
pBT->slkDummyRoot->sLink[RIGHT] = NULL;
pBT->slkDummyRoot->sLink[LEFT] = NULL;
pBT->slkDummyRoot->pData
= NULL;
pBT->uiCount
= 0;
// funcoesh especificas p/ tratamento da arvore
pBT->fCreateData =
fCreateData;
pBT->fDeleteData =
fDeleteData;
pBT->fDuplicatedNode =
fDuplicatedNode;
pBT->fNodeDataCmp =
fNodeDataCmp;
pBT->fTraversal = fTraversal;
return
(pBT); // devolve o enderecoh
}
else // caso fracasse em alocar memoria
return
NULL; //
retorna a indicacaoh
}
|
Função
|
DestroyBinTree
|
Propósito
|
Libera toda a memória de uma arvore binária previamente criada
|
Parâmetros
|
SBINTREE *BT -> Árvore a ser destruída
|
Retorno
|
TRUE - memória da estrutura da arvore e todos os nós liberados
FALSE - árvore inválida
|
Descrição
|
Ponto de entrada para a rotinas de travessia recursiva, executa a
rotina DelTree para eliminar nós individualmente, terminado o processo de
atravessar e liberar os nós, libera o nó raiz falso e a estrutura de dados
que gerencia a arvore.
|
BOOL DestroyBinTree( SBINTREE *BT )
{
if (BT) {
// percorre a arvore em pos ordem,
// apagando cada noh
DelTree(BT,
BTRoot->sLink[RIGHT] );
// libera a raiz falsa
free(BT->slkDummyRoot);
// libera a estrutura arvore
free(BT);
return TRUE;
}
else
return FALSE;
}
|
Função
|
DelTree
|
Propósito
|
Libera nós de uma arvore binária em pós-ordem
|
Parâmetros
|
SBINTREE *BT -> estrutura de dados da arvore c/ a rotina de
exclusão do nó
SLINK slk -> nó atual da arvore sendo percorrida recursivamente
|
Retorno
|
Nenhum
|
Descrição
|
Acessa os nós da árvore em sequencia pós-ordenada, eliminando o nó da
posição atual, por ser uma travessia pós-ordenada, o nó liberado não será referenciado novamente durante o
resto do percurso
|
void DelTree(
SBINTREE *BT, SLINK slk )
{
if (slk) {
DelTree(BT,
slk->sLink[LEFT]);
DelTree(BT,
slk->sLink[RIGHT]);
DeleteData(slk->pData); // apaga o dado
do noh
free(slk); // libera a memoria do
noh
--NodeCount; //
subtrai o noh do total
}
}
|
Busca
A rotina de busca se inicia a
partir de um nó e procura pela incidência desejada, encerra ao encontrar, do
contrario, continua a esquerda se for menor que o nó atual, ou a direita se maior, no código abaixo se
faz uso da vantagem de utilizar um vetor de dois ponteiros para os filhos onde
o valor de comparação iCompare decide
qual direção prosseguir através da variável iDir.
Função
|
FindNode
|
Propósito
|
Encontra um nó da árvore binária
|
Parâmetros
|
SBINTREE *BT -> ponteiro para estrutura de dados que trata a
arvore com a função para comparação de dados
void *pData -> informação que devera ser encontrada na árvore
|
Retorno
|
slkCurr - ponteiro para o nó
NULL - não encontrou um nó
equivalente
|
Descrição
|
Realiza uma formatação nos dados apontados por pData, para poder
realizar a comparação necessária durante o percurso de busca do nó
equivalente.
|
SLINK FindNode( SBINTREE *BT, void
*pData )
{
SLINK slkTmp; // noh temporario com o dado de
busca
SLINK slkCurr; // posicao atual na arvore
int
iCompare; //
resultado da comparacaoh
int
iDir; //
seguir direita/esquerda
// formata os
dados dentro do noh temporario
slkTmp = CreateNode(BT, pData);
if
(slkTmp == NULL) // naoh conseguiu alocar o noh
return
NULL; //
retorna indicando fracasso
// inicia com
o noh falso da raiz
slkCurr = BTRoot->sLink[RIGHT];
// desce a
arvoreh em busca de uma ramo vazio.
while
(slkCurr != NULL &&
(iCompare =
NodeDataCmp(slkTmp->pData, slkCurr->pData)))
{
//
corrige -1 e 0(<=) para 1(LEFT) e 1(>) para 0(RIGHT)
iDir = iCompare < 0;
slkCurr =
slkCurr->sLink[iDir]; // atualiza atual
}
// apaga o
dado do noh
DeleteData(slkTmp->pData);
// libera a
memoria do noh temporario
free(slkTmp);
return
slkCurr;
}
|
Inserir Nó
Inserção de nó é simples, basta
descer a árvore como se estivesse procurando o nó que se deseja adicionar,
quando encontrar um nó sem filhos, isto é, nó NULO, insere o novo nó como filho
do ultimo nó, aqui temos um dos motivos pelo qual se declarou um nó pai (BT->slkDummyRoot) para a raiz da
árvore.
Função
|
CreateNode
|
Propósito
|
Criar um nó para a árvore binária
|
Parâmetros
|
SBINTREE *BT -> estrutura árvore c/ ponteiro para a função
CreateData
void *data -> ponteiro genérico c/ o dado do nó
|
Retorno
|
slkNewNode - ponteiro para uma estrutura do tipo nó
NULL - não conseguiu criar um nó
|
Descrição
|
Cria um nó e então chama a função especifica da aplicação CreateData()
para criar o dado da estrutura do nó. Em caso de falha retorna NULO
|
PRIVATE SLINK CreateNode(SBINTREE *BT, void *pData)
{
SLINK slkNewNode;
// aloca os
ponteiros para seguinte, anterior e dado para o noh
slkNewNode = (SLINK) malloc(sizeof(SNODE));
if (slkNewNode == NULL) // caso
fracasse em alocar memoria
return
(NULL); //
retorna indicacaoh de NULO
// tendo
sucesso na alocacaoh, inicializa as variaveis
slkNewNode->sLink[RIGHT] = NULL;
slkNewNode->sLink[LEFT] = NULL;
// agora chama a aplicacaoh especifica para alocacah de dados
slkNewNode->pData =
CreateData(pData);
// caso naoh
consiga alocar memoria para o dado do noh
if
(slkNewNode->pData == NULL) {
free(slkNewNode); // libera a memoria previamente alocada
return
(NULL); //
retorna NULO para indicar falha
}
// alocou
toda a memoria nescessaria
else {
return
(slkNewNode); // retorna o noh criado
}
}
|
Função
|
AddNode
|
Propósito
|
Adiciona um nó na árvore
|
Parâmetros
|
SBINTREE *BT -> ponteiro
para estrutura de dados que trata a arvore c/ ponteiros paras funções de
comparação e tratamento de duplicados
void *pData -> nó a ser inserido na árvore
|
Retorno
|
TRUE - adicionou na lista o
nó, caso seja duplicata, remove, adiciona ou ignora, depende da configuração
da árvore
FALSE - não conseguiu criar um nó para inserir na arvore
|
Descrição
|
Adiciona um nó numa árvore binária
|
BOOL AddNode(SBINTREE *BT, void
*pData)
{
SLINK slkNew; // aponta para o noh a ser
inserido na lista
SLINK slkPrev; // link anterior da lista durante a
busca
SLINK slkCurr; // link atual da lista durante a
busca
int
iAction; //
acaoh em caso de nohs duplicados
int
iCompare; //
resultado da comparacaoh
int
iDir; //
seguir direita/esquerda
slkNew = CreateNode(BT, pData); // cria o noh
if (slkNew
== NULL) // naoh alocou o noh
return FALSE; // indica fracasso
// ignora o
tratamento especial que se
// faz para a
raiz da arvoreh
// utiliza um
noh falso como raiz da arvore
// e passa a
tratar o noh inicial(raiz)
// como um
noh igual aos demais
//
simplificando a logica de tratamento
slkPrev = BTRoot;
// a raiz
falsa utiliza apenas a ramificacaoh direita
iDir = RIGHT;
// igual ao slkCurr = BTRoot->sLink[RIGHT]
slkCurr =
slkPrev->sLink[RIGHT];
// desce a
arvoreh em busca de uma ramo vazio.
while
(slkCurr != NULL)
{
//
avanca a posicaoh 1 - atualiza anterior
slkPrev = slkCurr;
//
Decide qual direcaoh seguir
iCompare =
NodeDataCmp(slkNew->pData, slkCurr->pData);
if
(iCompare == 0) // noh duplicado
{
//
o que fazer com noh duplicado
iAction = DuplicatedNode(slkNew, slkCurr);
// fDuplicateNode retorna:
// 1 -> adicionar duplicada
if
(iAction)
{
// nada faz
}
//
fDuplicateNode retorna:
// 0 -> destruir duplicada
else
// if
(iAction == 0)
{
// naoh inclui o duplicado
// apagamos os dados que dependem da
// da implementacaoh do objeto
DeleteData(slkNew->pData);
// desalocamos o noh
free(slkNew);
return FALSE;
}
}
//
comparacaoh retorna -1(menor), 0(igual) e 1(maior)
iDir = iCompare < 0;
//
corrige <= (-1 e 0) para 1(LEFT) e >(1) para 0(RIGHT)
//
avanca a posicaoh 2 - atualiza atual
slkCurr
= slkCurr->sLink[iDir];
}
// adiciona
novo noh
slkPrev->sLink[iDir] = slkNew;
// soma o
novo noh no total
++NodeCount;
return
TRUE;
}
|
Excluir nó
Dentre as 3 primitivas básicas
(Inserir, excluir e procurar), excluir apresenta maior complexidade devido a
necessidade de manter os nós respeitando a posição relativa entre eles,
mantendo a chave de ordenação, como feito para inserir, desce a arvore
procurando o nó que se deseja apagar.
O modelo de exclusão do nó
mostrado anteriormente era simplificado e tinha fim didático, substituindo o nó
a ser eliminado pelo elemento compatível mais próximo, para este código de
exclusão, o remanejamento dos nós mantém
balanceamento da árvore, ideal para manter as operações de busca eficientes, tratando
os três possíveis casos:
1. Não tem filhos direito,
substitui com o filhos esquerdo, atende também quando não tem ambos os filhos.
2. Filho direito não tem
descendente esquerdo, substitui o nó pai com o filho direito e coloca o nó
irmão esquerdo como filho esquerdo
3. Pior caso, nó a ser excluído
tem os dois filhos, coloca em seu lugar pelo menor nó da ramificação direita,
ou seja, substitui o nó pai pelo menor
descendente do filho direito, a busca é feita sempre seguindo a subárvore
esquerda, por ser o menor não terá filho esquerdo, caso o menor tenha um filho
direito, este assume sua posição.
Função
|
DeleteNode
|
Propósito
|
Apaga um nó da árvore binária
|
Parâmetros
|
SBINTREE *BT -> ponteiro para estrutura de dados que trata a
arvore c/ ponteiros paras funções de comparação e excluir dados
void *pData -> informação que devera ser excluída da árvore
|
Retorno
|
TRUE - exclui o nó e atualizou
a arvore
FALSE - não encontrou um nó equivalente p/ exclusão
|
Descrição
|
Apaga um nó que tenha os dados indicado por pData.Verifica se o nó se
encontra na arvore, Elimina o nó e atualiza a referencia aos demais nós.
|
BOOL DeleteNode( SBINTREE *BT, void
*pData )
{
SLINK slkTmp; // noh temporario com o dado de
busca
SLINK slkPrev; // posicao anterior na arvore
SLINK slkCurr; // posicao atual na arvore
SLINK slkDel; // noh da arvore a ser excluido
int
iCompare; //
resultado da comparacaoh entre dois nohs
int
iDir; //
seguir direita/esquerda
slkTmp = CreateNode(BT, pData); // formata noh tmp
if
(slkTmp == NULL) // naoh conseguiu alocar o noh
return
FALSE; //
retorna indicando fracasso
// inicia com
o noh falso da raiz
slkPrev = BTRoot;
iDir = RIGHT; // a raiz falsa utiliza ramo
direito
slkCurr = slkPrev->sLink[RIGHT];
// desce a
arvoreh em busca de uma ramo vazio.
while
(slkCurr != NULL &&
(iCompare =
NodeDataCmp(slkTmp->pData, slkCurr->pData)))
{
//
comparacaoh retorna -1(menor), 0(igual) e 1(maior)
iDir = iCompare < 0;
//
corrige <= (-1 e 0) para 1(LEFT) e >(1) para 0(RIGHT)
slkPrev = slkCurr; //
atualiza anterior
slkCurr =
slkCurr->sLink[iDir]; // atualiza atual
}
DeleteData(slkTmp->pData); // apaga o dado do
noh
free(slkTmp); // libera o noh temporario
if
(slkCurr == NULL) // naoh encontrou o noh
return
FALSE;
// salva a
posicaoh do noh a ser excluido
slkDel = slkCurr;
// primeiro caso
if (slkCurr->sLink[RIGHT] == NULL)
{
slkCurr = slkCurr->sLink[LEFT];
}
// segundo
caso
else if (slkCurr->sLink[RIGHT]->sLink[LEFT] ==
NULL)
{
slkCurr =
slkCurr->sLink[RIGHT];
slkCurr->sLink[LEFT]
= slkDel->sLink[LEFT];
}
// ultimo
caso
else {
//
aponta para o pai do menor noh esquerdo
SLINK slkSmallFather;
//
procura o menor noh
slkSmallFather = slkCurr->sLink[RIGHT];
while
(slkSmallFather->sLink[LEFT]->sLink[LEFT])
slkSmallFather
= slkSmallFather->sLink[LEFT];
// aponta para o menor noh da ramificacaoh
//
'slkCurr' ira ocupar a posicaoh do noh a ser
// excluido
slkCurr =
slkSmallFather->sLink[LEFT];
// o neto direito substitui a posicaoh do filho
slkSmallFather->sLink[LEFT] = slkCurr->sLink[RIGHT];
// coloca a referencia dos filhos do noh a ser excluido
// no
noh que irah substitui-lo.
slkCurr->sLink[LEFT] = slkDel->sLink[LEFT];
slkCurr->sLink[RIGHT]
= slkDel->sLink[RIGHT];
}
// atualiza a
informacaoh do pai do noh excluido
slkPrev->sLink[iDir] = slkCurr;
DeleteData(slkDel->pData); // apaga o dado do
noh
free(slkDel); // libera a memoria do noh
--NodeCount; //
subtrai o noh do total
return TRUE;
}
|
Travessia
Graças a topologia da árvore
binária, uma importante característica é a ordem de travessia, frequentemente
surgirá a necessidade de visitar todos os nós em uma árvore, assegurando que
cada nó somente será acessado uma única vez e de forma consistente, existem três
maneiras de percorrer uma árvore, todas recursivas, pré-ordem, ordem e
pós-ordem, de grande importância compreender que visitar um filho implica em
recursivamente visitar todos os seus descendentes, mesmo tendo definições
simples, todas as três travessias asseguram visitar todos os nós na árvore e
podem ser utilizadas para diversos propósitos em diferentes ocasiões.
Função
|
TraversalTree
|
Propósito
|
Percorrer uma arvore binária executando rotinas em ordem especifica
|
Parâmetros
|
void *pOut -> aponta a saída dos dados, usada pela função que
percorre a arvore
SBINTREE *BT -> Árvore a ser atravessada e rotina de travessia
ETRAVERSAL eType -> tipo de travessia, ordenada, pós-ordenada ou
pré-ordenada
|
Retorno
|
TRUE - Travessia de árvore completada
FALSE - Arvore vazia
|
Descrição
|
Ponto de entrada para as rotinas ( InOrder, PreOrder e PostOrder )de
travessia recursivas.
|
typedef enum tagETRAVERSAL {
INORDER,
PREORDER,
POSTORDER }
ETRAVERSAL;
. . .
BOOL TraversalTree(void
*pOut, SBINTREE *BT, ETRAVERSAL eType )
{
if (BTRoot->sLink[RIGHT]) {
switch (eType) {
default:
case INORDER:
InOrder(pOut,
BT, BTRoot->sLink[RIGHT], 0);
break;
case PREORDER:
PreOrder(pOut,
BT, BTRoot->sLink[RIGHT], 0);
break;
case POSTORDER:
PostOrder(pOut,
BT, BTRoot->sLink[RIGHT], 0);
break;
}
return TRUE;
}
else
return FALSE;
}
|
Funções
|
InOrder
PreOrder
PostOrder
|
Propósito
|
Percorrer uma arvore binária em sequência pré-ordenada, ordenada ou em pós-ordem.
|
Parâmetros
|
void *pOut -> aponta a saída dos dados, usada pela função que
percorre a arvore
SBINTREE *BT -> estrutura de dados da arvore c/ a rotina de
travessia
SLINK slk -> nó atual da arvore sendo percorrida recursivamente
int iLevel -> profundidade
na arvore em que a rotina se encontra
|
Retorno
|
Nenhum
|
Descrição
|
Acessa os nós da árvore
recursivamente em sequencia ordenada,
pré-ordenada ou pós-ordenada, executando a rotina apontada por fTraversal para tratar o nó
|
void InOrder(void *pOut, SBINTREE *BT, SLINK slk, int iLevel)
{
if (slk) {
InOrder(pOut,
BT, slk->sLink[LEFT], iLevel + 1);
Traversal(pOut,
slk, iLevel);
InOrder(pOut,
BT, slk->sLink[RIGHT], iLevel + 1);
}
}
void
PreOrder(void *pOut, SBINTREE *BT, SLINK slk,
int iLevel)
{
if (slk) {
Traversal(pOut,
slk, iLevel);
PreOrder(pOut,
BT, slk->sLink[LEFT], iLevel + 1);
PreOrder(pOut,
BT, slk->sLink[RIGHT], iLevel + 1);
}
}
void
PostOrder(void *pOut, SBINTREE *BT, SLINK
slk, int iLevel)
{
if (slk) {
PostOrder(pOut,
BT, slk->sLink[LEFT], iLevel + 1);
PostOrder(pOut,
BT, slk->sLink[RIGHT], iLevel + 1);
Traversal(pOut,
slk, iLevel);
}
}
|
Gráfico
Um
aspecto interessante da árvore é poder visualizar e conseguir observar como as
operações de adicionar e apagar altera o formato da mesma, em termos práticos,
dificilmente uma aplicação terá utilidade com a impressão da árvore que não se
seja para testes e validações.
As
rotinas de impressão apresentada abaixo, servem apenas para mostrar toda a ramificação
de uma árvore criada, peço tolerância quanto a qualidade visual, uma vez que para
manter o código estritamente no padrão C, sem o uso de bibliotecas de
terceiros, foi utilizada a saída através do console, que implica em desenhar
uma árvore usando caracteres e imprimindo uma linha por vez de forma lateral.
Função
|
PrintForest
|
Propósito
|
Imprime em um arquivo de saída a árvore resultante
|
Parâmetros
|
FILE *fOut -> arquivo em que a árvore será impressa.
SBINTREE *BT -> Árvore a ser desenhada
Path - buffer
com o caminho percorrido pela função recursiva
MaxDepth -
indica a profundidade(altura) da arvore impressa
|
Retorno
|
TRUE - Impressão concluída
FALSE - Árvore vazia
|
Descrição
|
Ponto de entrada para a rotina de impressão recursiva, reserva um
buffer para manter registro do caminho percorrido pela função, inicia a variável
de profundidade da árvore.
|
BOOL PrintForest(FILE *fOut, SBINTREE *BT)
{
if
(BTRoot->sLink[RIGHT])
{
//
impossivel saber a altura da arvore
//
aloca esperando o pior caso
Path = malloc(NodeCount);
if
(Path)
{
//
comecah no nivel 0, logo profundidade 0
MaxDepth = 0;
PrintTree(fOut,
BT, BTRoot->sLink[RIGHT], 0);
// naoh mais necessarioh, libera
free(Path);
// informacoesh da arvore
fprintf(fOut,
"\nTotal de nohs: %u\n",
NodeCount);
fprintf(fOut,
"Profundidade: %u\n", MaxDepth);
return TRUE;
}
}
else {
fprintf(fOut,
"Arvoreh vazia\n");
}
return
FALSE;
}
|
Função
|
PrintTree
|
Propósito
|
Imprime o nó da árvore e linhas de ramificação
|
Parâmetros
|
FILE *fOut -> arquivo em que a árvore será impressa.
SBINTREE *BT -> Árvore a ser desenhada
Path - buffer
com o caminho percorrido pela função recursiva
MaxDepth -
indica a profundidade(altura) da arvore impressa
SLINK slk -> nó atual da arvore sendo percorrida recursivamente
int iLevel -> profundidade na árvore em que a rotina se encontra
|
Retorno
|
Nenhum
|
Descrição
|
Acessa os nós da árvore em sequência ordenada da direita para a esquerda, durante a impressão da nó na linha, verifica as ramificações
anteriores através do buffer Path, sempre que ocorre desvio da esquerda p/
direita ou vice-versa, deve incluir '|' como indicação de linha horizontal de
uma ramificação.
|
void
PrintTree(FILE *fLog, SBINTREE *BT, SLINK slk, int
iLevel)
{
if
(slk)
{
//
verifica a profundidade da arvore
if (iLevel
> MaxDepth)
MaxDepth
= iLevel;
// Segue a ramificacaoh direita
Path[iLevel] = 'R';
PrintTree(fLog, BT, slk->sLink[RIGHT], iLevel + 1);
// imprime o noh atual
{
char
*pDraw;
int
iX;
//
aloca o tamanho necessario para
//
montar a linha ser desenhada
//
utiliza memoria do heap ao inves da pilha(stack)
pDraw = malloc(iLevel * 2 + 3);
if (pDraw)
{
pDraw[0]
= ' ';
pDraw[1]
= ' ';
for (iX = 1; iX < iLevel; ++iX)
{
// ex: Path = RRRRLRRRL
// sequencia RL(direita/esquerda)
// OU LF(esquerda/direita)
if (Path[iX-1] != Path[iX])
{
// desenha linha horizontal de
// uma ramificacaoh anterior
pDraw[iX
* 2 ] = '|';
pDraw[iX
* 2 + 1] = ' ';
}
// sequencia LL(esquerda/esquerda)
// ou RR(direita/direita)
else
{
// naoh tem linha de
// ramificaoh acima
pDraw[iX * 2
] = ' ';
pDraw[iX
* 2 + 1] = ' ';
}
}
// desenha o noh na linha atual
pDraw[iLevel * 2
] = '+';
pDraw[iLevel
* 2 + 1] = '-';
pDraw[iLevel
* 2 + 2] = '\0';
fprintf(fLog,
pDraw);
free(pDraw);
}
}
Traversal(fLog,
slk, iLevel);
fprintf(fLog,
"\n");
// Segue ramificacaoh esquerda
Path[iLevel] = 'L';
PrintTree(fLog,
BT, slk->sLink[LEFT], iLevel + 1);
}
}
|
Mais
uma vez tenho de dividir o assunto em duas partes devido a extensão, na próxima
postagem todas as primitivas aqui apresentadas serão utilizadas em um
aplicativo exemplo.
Nenhum comentário:
Postar um comentário