Implementar una estructura de datos de árbol binario de búsqueda en C++

1. Implementar un árbol binario de búsqueda usando la palabra clave struct en C++
2. Implementar el algoritmo de búsqueda binaria para un árbol binario de búsqueda en C++

Esta guía demostrará cómo implementar una estructura de datos de árbol binario de búsqueda en C++.

Implementar un árbol binario de búsqueda usando la palabra clave struct en C++

Un árbol binario de búsqueda (BST) es un caso especial de una estructura de datos de árbol binario. La estructura de datos se utiliza generalmente para almacenar una lista ordenada de elementos para una búsqueda rápida usando el algoritmo de búsqueda binaria. A diferencia del árbol binario normal, BST tiene un miembro de datos especial en cada nodo llamado clave, que debe tener valores únicos.

Cada nodo en una BST debe satisfacer el siguiente requisito: el valor de la key debe ser mayor que todas las claves en el subárbol de su hijo izquierdo y menor que todas las claves en el subárbol de su hijo derecho. La declaración anterior implica que los elementos con valores de clave menores se colocarán en el lado izquierdo de la jerarquía del árbol; esto da como resultado una estructura óptima para utilizar la búsqueda binaria.

En el siguiente código de ejemplo, definimos una struct llamada BSTreeNode, que consta de dos punteros a los nodos izquierdo/derecho y un miembro de cadena para denotar la clave. Tenga en cuenta que solo estamos implementando la versión más simple de BST, donde el valor de la clave es el mismo que los datos almacenados en el nodo.

Generalmente, el programador es libre de definir un nodo BST para almacenar otros miembros de datos según sea necesario para el problema específico. Esta definición es la más adecuada para emular el array ordenada de cadenas, que debe buscarse para una cadena determinada (clave). Antes de implementar la función de búsqueda binaria, el objeto BST debe construirse desde cero. Por lo tanto, usamos un vector predefinido de cadenas para inicializar un nuevo árbol de búsqueda binario.

La función insertNode es la implementación recursiva para crear un nuevo hijo BSTreeNode cuando se pasa la raíz del árbol como argumento. Si necesitamos crear un nodo raíz, puede declarar un puntero al tipo BSTreeNode, asignarle nullptr y pasarlo al insertNode con el valor correspondiente de la string que debe almacenarse allí. Una vez que inicializamos la lista con contenido v1, se puede invocar la función printTree para imprimir todos los valores clave en el orden de clasificación denominado recorrido inorder de 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;
}

Producción :

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

Implementar el algoritmo de búsqueda binaria para un árbol binario de búsqueda en C++

El algoritmo de búsqueda binaria es eficiente en la estructura BST debido al orden, donde las claves se almacenan en la jerarquía. Hay tres operaciones principales implementadas para las BST: inserción, eliminación y búsqueda.

En el siguiente ejemplo, nos centramos más en la búsqueda. La función findNode es responsable de la búsqueda de la clave dada en el BST, que se pasa a una función usando su nodo raíz. Este comando es de naturaleza recursiva y devuelve el puntero al BSTreeNode donde se almacena la clave. Si el valor de la clave no se encuentra en ningún nodo, se devuelve nullptr. Para una mejor demostración, también implementamos una función printNode que toma el puntero del nodo y envía el valor clave al flujo cout para encadenar el valor de retorno de la función findNode directamente en la función para imprimirlo.

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

Producción :

zero
Not a valid node!