Árvore Binária de Busca
- #Estrutura de dados
- #Lógica de Programação
A Árvore Binária de Busca é construída de forma que, para cada nó, as chaves menores estarão na subárvore à esquerda e as chaves maiores estarão na subárvore à direita. Portanto, a inserção dos nós na árvore deve obedecer a essa propriedade.
Por exemplo, considerando a imagem acima, durante a busca por um elemento de valor 5, na primeira consulta, se o valor for 1, o algoritmo seguirá para a subárvore direita, já que 5 é maior que 1. Desta forma, o elemento 5 é encontrado.
Essa estrutura proporciona uma eficiente organização dos dados, facilitando operações como busca, inserção e remoção. A propriedade de ordenação das chaves permite uma busca mais rápida, tornando a Árvore Binária de Busca uma ferramenta valiosa em muitos contextos. Ao entender e aplicar corretamente esses princípios, é possível otimizar o desempenho de algoritmos que utilizam essa estrutura.
#include <stdio.h>
#include <stdlib.h>
// Definição da estrutura do nó da árvore
typedef struct TreeNode {
int chave;
struct TreeNode *esquerda;
struct TreeNode *direita;
} TreeNode;
// Função para criar um novo nó
TreeNode* criarNo(int chave) {
TreeNode* novoNo = (TreeNode*)malloc(sizeof(TreeNode));
novoNo->chave = chave;
novoNo->esquerda = NULL;
novoNo->direita = NULL;
return novoNo;
}
// Função para inserir um novo nó na árvore
TreeNode* inserir(TreeNode* raiz, int chave) {
if (raiz == NULL) {
return criarNo(chave);
}
// Inserção na subárvore esquerda ou direita
if (chave < raiz->chave) {
raiz->esquerda = inserir(raiz->esquerda, chave);
} else if (chave > raiz->chave) {
raiz->direita = inserir(raiz->direita, chave);
}
return raiz;
}
// Função para buscar um elemento na árvore
TreeNode* buscar(TreeNode* raiz, int chave) {
if (raiz == NULL || raiz->chave == chave) {
return raiz;
}
// Busca na subárvore esquerda ou direita
if (chave < raiz->chave) {
return buscar(raiz->esquerda, chave);
} else {
return buscar(raiz->direita, chave);
}
}
// Função para percorrer a árvore em ordem
void emOrdem(TreeNode* raiz) {
if (raiz != NULL) {
emOrdem(raiz->esquerda);
printf("%d ", raiz->chave);
emOrdem(raiz->direita);
}
}
// Função principal
int main() {
TreeNode* raiz = NULL;
// Inserção de elementos
raiz = inserir(raiz, 5);
raiz = inserir(raiz, 3);
raiz = inserir(raiz, 7);
raiz = inserir(raiz, 1);
raiz = inserir(raiz, 4);
// Exemplo de busca
int elementoBuscado = 4;
TreeNode* resultadoBusca = buscar(raiz, elementoBuscado);
if (resultadoBusca != NULL) {
printf("Elemento %d encontrado na árvore.\n", elementoBuscado);
} else {
printf("Elemento %d não encontrado na árvore.\n", elementoBuscado);
}
// Exibição da árvore em ordem
printf("Árvore em ordem: ");
emOrdem(raiz);
printf("\n");
return 0;
}