Á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;
}