Árvore Binária

Prévia do material em texto

---- ÁRVORE BINÁRIA ----
Nó da árvore
typedef struct tree{
 char Chave; // Conteudo
// Pode ser qualquer coisa
 struct tree* Left; // Ponteiro para Esquerda
 struct tree* Right; // Ponteiro para Direita
}Tree;
 
Tree* pTree=NULL; // Ponteiro inicial da árvore
// Aponta para a raiz da árvore
Inserir elementos na árvore
void Insert( Tree** pTree, char iChave ){
 
 if( (*pTree)==NULL ){
 // Aloca um novo nó da árvore
 (*pTree) = (Tree*)malloc( sizeof(Tree));
 
 if( (*pTree) ){
 (*pTree)->Chave = iChave;
 (*pTree)->Left = NULL;
 (*pTree)->Right = NULL;
 }
 }
// Enquanto ponteiro != NULL, existe elemento
// Se menor insere à esquerda da raiz, se maior à direita
 else{
 if( iChave < (*pTree)->Chave )
 Insert( &(*pTree)->Left, iChave );
 else
 Insert( &(*pTree)->Right, iChave );
 }
}
Pesquisar elemento na árvore
void Search( Tree** pTree, char iChave ){
 
 if( (*pTree) == NULL ){
 // ELEMENTO NAO ENCONTRADO OU NAO EXISTE
 // Alterar conforme a necessidade do problema
 return;
 }
 else{
 if( iChave == (*pTree)->Chave ){
 // ELEMENTO ENCONTRADO
 // Alterar conforme a necessidade do problema
 return;
 }
 else{ // Vai descendo ate encontrar (ou nao) 
 if( iChave < (*pTree)->Chave ){
 Search( &(*pTree)->Left, iChave );
 return;
 }
 else{
 Search( &(*pTree)->Right, iChave );
 return;
 }
 }
 }
}
Chamada na main
Insert( &pTree, Elemento); // Elemento a ser inserido
Search( &pTree, Elemento ); // Elemento a ser procurado
Remove( &pTree, Elemento ); // Elemento a ser removido
IN( &pTree ); PRE( &pTree ); POST( &pTree );
Remover elemento da árvore
void Remove( Tree** pTree, tipo C ){
 
 Tree* pN; // Ponteiro auxiliar
 
 if( (*pTree)==NULL )// arvore nula
 return;
 if( C == (*pTree)->Chave ){
 pN = (*pTree);
 
 if( (*pTree)->Left==NULL ) // nao tem filho a Esq
 (*pTree) = (*pTree)->Right;
 else if( (*pTree)->Right==NULL ) //nao tem filho a Dir
 (*pTree) = (*pTree)->Left;
 else{ // tem ambos os filhos
 
 pN = Menor( &(*pTree)->Left );
 (*pTree)->Chave = pN->Chave;
 }
 
 pN=NULL;
 return;
 }
 else if( C < (*pTree)->Chave ){
 Remove( &(*pTree)->Left );
 return;
 }
 else{
 Remove( &(*pTree)->Right );
 return;
 }
}
Tree* Menor( Tree** pTree ){
 
 Tree* pAux = (*pTree);
 
 if( pAux->Right == NULL ){// Encontrou o menor
 (*pTree) = (*pTree)->Left;
 return pAux;
 }
 else{ // Continua a busca
 // alterar se deseja o menor da esquerda ou direita
 return Menor( &(*pTree)->Right );
 }
}
** Para não perder a característica de uma árvore binária não basta apenas 
remover o elemento, deve substituir em seu lugar o elemento mais à esquerda 
do filho da direita ou o elemento mais a direita do filho da esquerda (mais 
profundo). A função Menor é responsável de encontrar esse elemento **
Percurso Prefixo ( ou Pré-ordem )
void PRE( Tree** pTree ){
 
 if( (*pTree) != NULL ){
 
 // Se necessitar de espaços entre cada elemento
 // inserir aqui
 printf( "%c", (*pTree)->Chave );
 
 PRE( &(*pTree)->Left );
 PRE( &(*pTree)->Right );
 }
}
Percurso Infixo ( ou Em-ordem )
void IN( Tree** pTree ){
 
 if( (*pTree) != NULL ){
 
 IN( &(*pTree)->Left );
 // Se necessitar de espaços entre cada elemento inserir aqui
 printf( "%c", (*pTree)->Chave );
 
 IN( &(*pTree)->Right );
 }
}
Percurso Posfixo ( ou Pós-ordem )
void POST( Tree** pTree ){
 
 if( (*pTree) != NULL ){
 
 POST( &(*pTree)->Left );
 POST( &(*pTree)->Right );
 
 // Se necessitar de espaços entre cada elemento inserir aqui
 printf( "%c", ((*pTree)->Chave) );
 }
}
Percurso por Nível
queue<Tree*> Que; // Fila auxiliar
void Nivel( Tree** pTree ){
 
 Tree* pN=NULL;
 
 if( pTree != NULL ){
 
 Que.push( (*pTree) );
 while( !( Que.empty() ) ){
 
 pN = Que.front();
 Que.pop();
 
 if( (pN->Left) != NULL )
 Que.push( pN->Left );
 if( (pN->Right) != NULL )
 Que.push( pN->Right );
 
 // Imprime elemento
 printf( "%d", pN->Chave );
 }
 }
}
Conceitos
Raiz → Primeiro nó da árvore
Folha → Nó que não possui filhos
Numeração → Raiz recebe nº 1 (índice 1), filho da esquerda recebe o dobro de 
seu pai (2i) e filho da direita o dobro de seu pai mais 1 (2i + 1).
Nível → A raiz possui nível zero e o nível de cada elemento é o de seu pais 
mais um
Altura → É dada por log(n ) ou o nº de arestas até a folha mais profunda.
Thiago
Texto digitado
Feito por: Thiago Barbosa de Souza
Thiago
Texto digitado
Engenharia de Computação