Inserção de árvore binária de busca em C++

Este artigo demonstrará como implementar a função de inserção para a estrutura de dados da árvore binária de busca em C++.

Insira novos nós na árvore binária de busca em C++

Árvores binárias representam um subconjunto de estruturas de árvore em geral. Eles são chamados de binários por terem no máximo dois filhos em qualquer nó. Neste caso, discutimos uma árvore binária de busca onde cada nó contém um membro de dados chamado de chave, e em cada nível da árvore, a chave do nó fornecido deve ser maior que as chaves em sua subárvore esquerda e menor que todas as chaves na direita subárvore. Esse recurso nos permitirá usar um algoritmo de pesquisa binária na árvore à medida que pesquisamos em um array ordenado.

Primeiramente, precisamos declarar um nó de árvore struct, que inclui dois ponteiros para nós left / right e uma chave. Por motivos de simplicidade, estamos armazenando chaves como valores int, mas pode ser necessário construir um layout diferente para o nó, dependendo do problema. Também construímos essa árvore manualmente, declarando um único ponteiro TreeNode como a raiz da árvore e, em seguida, chamando a função insertNode para adicionar novos nós.

Para melhor demonstração e verificação de nosso exemplo, também incluímos uma função para encontrar um nó com a chave fornecida e outra para imprimir o conteúdo de toda a árvore. O último nos ajudará a inspecionar facilmente a estrutura da árvore em cada etapa do programa. Observe que todas as três funções utilizam recursão, pois uma estrutura de árvore é inerente aos algoritmos de divisão e conquista.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct TreeNode {
  int key;
  struct TreeNode *left{};
  struct TreeNode *right{};
};

void insertNode(TreeNode *&root, const int k) {
  if (root == nullptr) {
    root = new TreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

TreeNode *findNode(TreeNode *root, const int k) {
  if (root == nullptr) return nullptr;

  if (k == root->key) return root;

  if (k < root->key)
    return findNode(root->left, k);
  else
    return findNode(root->right, k);
}

void printTree(TreeNode *n) {
  if (n != nullptr) {
    printTree(n->left);
    cout << n->key << "; ";
    printTree(n->right);
  }
}

int main() {
  std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};

  TreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }
  printTree(root);
  cout << endl;

  std::vector<int> v2{1, 22, 4, 16};
  for (const auto &item : v2) {
    insertNode(root, item);
  }
  printTree(root);
  cout << endl;

  return EXIT_SUCCESS;
}

Produção:

2; 3; 5; 9; 11; 15; 20; 23;
1; 2; 3; 4; 5; 9; 11; 15; 16; 20; 22; 23;

Na função main, declaramos dois vetores int arbitrários e, em seguida, enviamos seus elementos para a árvore. Observe que nossa função insertNode leva dois parâmetros - nó raiz e um valor-chave. É necessário verificar se o nó raiz fornecido é válido ou apenas um nullptr, o último dos quais indica que a função precisa criar o conteúdo do nó raiz.

Se o nó raiz já foi inicializado, a função deve prosseguir de acordo com o valor da chave, que é comparado com a chave do nó atual. Se o valor da chave passada for menor do que a chave fornecida, devemos avançar para a subárvore esquerda. Caso contrário - a subárvore certa.

Eventualmente, chegaremos ao nó onde a chave precisa ser armazenada, e a travessia em ordem sempre imprimirá os valores de chave classificados conforme demonstrado no trecho de código.