Inserción de árbol de búsqueda binaria en C++

Este artículo demostrará cómo implementar la función de inserción para la estructura de datos de árbol de búsqueda binaria en C++.

Insertar nuevos nodos en el árbol de búsqueda binaria en C++

Los árboles binarios representan un subconjunto de estructuras de árboles en general. Se denominan binarios porque tienen como máximo dos hijos en un nodo determinado. En este caso, discutimos un árbol de búsqueda binario donde cada nodo contiene un miembro de datos llamado clave, y en cada nivel del árbol, la clave del nodo dado debe ser mayor que las claves en su subárbol izquierdo y menor que todas las claves en el derecho. subárbol. Esta característica nos permitirá usar un algoritmo de búsqueda binaria en el árbol mientras buscamos en un array ordenada.

Al principio, necesitamos declarar un nodo de árbol struct, que incluye dos punteros a los nodos left / right y una clave. En aras de la simplicidad, estamos almacenando claves como valores int, pero es posible que sea necesario construir un diseño diferente para el nodo según el problema. También construimos este árbol manualmente declarando un solo puntero TreeNode como la raíz del árbol y luego llamando a la función insertNode para agregar nuevos nodos.

Para una mejor demostración y verificación de nuestro ejemplo, también incluimos una función para encontrar un nodo con la clave dada y otra para imprimir el contenido de todo el árbol. Esto último nos ayudará a inspeccionar fácilmente la estructura del árbol en cada paso del programa. Tenga en cuenta que las tres funciones utilizan la recursividad, ya que una estructura de árbol es inherente a los algoritmos de división y 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;
}

Producción :

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

En la función main, declaramos dos vectores int arbitrarios y luego empujamos sus elementos al árbol. Tenga en cuenta que nuestra función insertNode toma dos parámetros: nodo raíz y un valor clave. Necesita verificar si el nodo raíz dado es válido o simplemente un nullptr, el último de los cuales indica que la función necesita crear el contenido del nodo raíz.

Si el nodo raíz ya está inicializado, la función debe continuar de acuerdo con el valor de la clave, que se compara con la clave del nodo actual. Si el valor de la clave pasada es menor que la clave dada, deberíamos avanzar al subárbol izquierdo. De lo contrario, el subárbol derecho.

Eventualmente, llegaremos al nodo donde se debe almacenar la clave, y el recorrido en orden siempre imprimirá los valores de clave ordenados como se muestra en el fragmento de código.