Implementar uma estrutura de dados de árvore binária de busca em C++

Este guia demonstrará como implementar uma estrutura de dados de árvore binária de busca em C++.

Implementar uma árvore binária de busca usando a palavra-chave struct em C++

Uma árvore binária de busca (BST) é um caso especial de uma estrutura de dados de árvore binária. A estrutura de dados é geralmente utilizada para armazenar uma lista ordenada de elementos para pesquisa rápida usando o algoritmo de pesquisa binária. Em contraste com a árvore binária regular, o BST tem um membro de dados especial em cada nó denominado key, que deve ter valores únicos.

Cada nó em um BST deve satisfazer o seguinte requisito: o valor key deve ser maior que todas as chaves na subárvore de seu filho esquerdo e menor que todas as chaves na subárvore de seu filho direito. A declaração anterior implica que os elementos com valores de chave menores serão posicionados no lado esquerdo da hierarquia da árvore; isso resulta em uma estrutura ideal para usar a pesquisa binária.

No código de exemplo a seguir, definimos uma struct chamada BSTreeNode, consistindo em dois ponteiros para os nós esquerdo/direito e um membro string para denotar a chave. Observe que estamos apenas implementando a versão mais simples do BST, onde o valor da chave é o mesmo que os dados armazenados no nó.

Geralmente, o programador é livre para definir um nó BST para armazenar outros membros de dados conforme necessário para o problema específico. Essa definição é mais adequada para emular a matriz classificada de strings, que precisa ser pesquisada por uma determinada string (chave). Antes de implementar a função de pesquisa binária, o objeto BST precisa ser construído do zero. Assim, usamos um vector predefinido de strings para inicializar uma nova árvore binária de busca.

A função insertNode é a implementação recursiva para criar um novo filho BSTreeNode quando a raiz da árvore é passada como argumento. Se precisarmos criar um nó raiz, você pode declarar um ponteiro para o tipo BSTreeNode, atribuir nullptr a ele e passá-lo para insertNode com o valor string correspondente que precisa ser armazenado lá . Assim que inicializamos a lista com o conteúdo v1, a função printTree pode ser chamada para imprimir todos os valores-chave na ordem de classificação chamada travessia inorder do BST.

#include <iostream>
#include <vector>

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

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

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

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

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printTree(root);

  return EXIT_SUCCESS;
}

Resultado:

aim;
born;
camel;
maya;
wind;
xen;
zero;

Implementar o algoritmo de pesquisa binária para uma árvore binária de busca em C++

O algoritmo de busca binária é eficiente na estrutura BST por causa da ordenação, onde as chaves são armazenadas na hierarquia. Existem três operações principais implementadas para os BSTs: inserção, exclusão e pesquisa.

No exemplo a seguir, estamos nos concentrando mais na pesquisa. A função findNode é responsável pela pesquisa da chave fornecida no BST, que é passada para uma função usando seu nó raiz. Este comando é de natureza recursiva e retorna o ponteiro para o BSTreeNode onde a chave está armazenada. Se o valor da chave não for encontrado em nenhum nó, nullptr é retornado. Para melhor demonstração, também implementamos uma função printNode que pega o ponteiro do nó e produz o valor da chave para o fluxo cout para encadear o valor de retorno da função findNode diretamente na função para imprimi-lo.

#include <iostream>
#include <vector>

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

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

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

BSTreeNode *findNode(BSTreeNode *root, const string &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 printNode(BSTreeNode *n) {
  if (n != nullptr) {
    cout << n->key << endl;
  } else {
    cout << "Not a valid node!" << endl;
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printNode(findNode(root, "zero"));
  printNode(findNode(root, "zeroo"));

  return EXIT_SUCCESS;
}

Resultado:

zero Not a valid node !