Implementar la estructura de datos de árbol binario en C++

1. Implementar el árbol binario usando la palabra clave struct en C++
2. Implementar funciones para calcular el tamaño y la altura de la estructura de árbol y una función para imprimir elementos en C++

Este artículo explicará cómo implementar la estructura de datos de árbol binario en C++.

Implementar el árbol binario usando la palabra clave struct en C++

Los árboles son estructuras de datos abstractas que se utilizan en varios algoritmos fundamentales. Generalmente son estructuras jerárquicas donde debe haber un nodo raíz y sus hijos formando subárboles. Además, existen múltiples tipos de estructura de árbol, cada uno adecuado para necesidades particulares y que ofrece algunas ventajas y desventajas.

Un árbol binario es una de las subclases de estructuras de datos de árbol, y se define como un árbol donde cada nodo debe tener dos hijos como máximo, incluidos los nodos hijos designados como left y right. En este caso, implementamos un árbol binario usando la función struct ya que declara una clase donde los miembros son públicos por defecto. Un nodo en un árbol binario contiene dos punteros a los nodos izquierdo/derecho y los datos necesarios. Tenga en cuenta que declaramos un único miembro int para representar los datos almacenados en el nodo sólo con fines explicativos.

Definimos un constructor que toma un número entero como argumento e inicializa el miembro data con su valor. Luego, inicializa los punteros de dos nodos con valores nullptr, que es una forma común de denotar los nodos hoja. El código del controlador de ejemplo construye un gráfico de muestra y almacena números enteros aleatorios en cada nodo. Hay múltiples subtipos de árboles binarios, por ejemplo, un árbol binario completo es una estructura en la que cada nodo tiene 0 o 2 hijos. Otro se llama árbol binario perfecto, donde todos los nodos interiores tienen dos hijos y todos los nodos hoja tienen profundidades idénticas.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  root->left = new BinTreeNode(distr(eng));
  root->right = new BinTreeNode(distr(eng));
  root->right->left = new BinTreeNode(distr(eng));
  root->right->right = new BinTreeNode(distr(eng));

  return EXIT_SUCCESS;
}

Observe que el código anterior da como resultado una estructura de árbol binaria completa, como se muestra en el siguiente gráfico. Asignamos cada nodo usando el operador new y pasamos un valor de inicializador usando el generador de números pseudoaleatorios.

root / left right / \ / nullptr nullptr left right /   \ /
    nullptr nullptr nullptr nullptr

Implementar funciones para calcular el tamaño y la altura de la estructura de árbol y una función para imprimir elementos en C++

Dado que la estructura de árbol es la forma en que se ejecutan los algoritmos de división y conquista, el último método se utiliza a menudo para implementar las funciones que manipulan sus elementos. La función treeSize recupera el tamaño del árbol que denota el número de todos los nodos, incluida la raíz. Observe que solo necesitamos usar una recursividad simple y devolver el tamaño del valor root (que es 1) más los tamaños de los nodos izquierdo / derecho.

La siguiente función es treeHeight que recupera la altura del árbol, que generalmente se conoce como la cantidad de nodos en el camino más largo desde una raíz hasta una hoja. Esta función también utiliza la recursividad llamándose a sí misma en ambos nodos hijos y devolviendo la altura del valor root (que es 1) más el valor mayor de las llamadas anteriores.

Por otro lado, la función printData envía el miembro data de cada nodo al flujo cout. Hay varias formas de recorrido para la estructura de árbol binario: recorrido en orden, preorden y posorden.

En el siguiente ejemplo, se utiliza la forma transversal en orden. El proceso imprime los datos de los nodos de hoja más a la izquierda yendo hacia la derecha en la misma profundidad al principio y luego se mueve a los niveles superiores. El siguiente fragmento de código construye un árbol binario parcialmente aleatorio y luego llama a cada una de las funciones anteriores en él. Si la naturaleza recursiva de estas funciones parece ser confusa a primera vista, debería intentar depurarlas paso a paso en los objetos de árbol más pequeños y observar el comportamiento en cada llamada de función recursiva.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

int treeSize(BinTreeNode *n) {
  if (n == nullptr)
    return 0;
  else
    return 1 + treeSize(n->left) + treeSize(n->right);
}

int treeHeight(BinTreeNode *n) {
  int lh, rh;

  if (n == nullptr)
    return -1;
  else {
    lh = treeHeight(n->left);
    rh = treeHeight(n->right);
    return 1 + (lh > rh ? lh : rh);
  }
}

void printData(BinTreeNode *n) {
  if (n != nullptr) {
    printData(n->left);
    cout << n->data << "; ";
    printData(n->right);
  }
}

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  auto tmp = root;

  auto iter = 100;
  while (iter > 0) {
    auto val = distr(eng);
    if (val % 5 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
      tmp = tmp->left;
    } else if (val % 4 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
      tmp = tmp->right;
    } else if (val % 6 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
    } else if (val % 100 == 0) {
      tmp = root;
    } else if (val % 2 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
    }
    iter -= 1;
  }

  cout << "size of tree = " << treeSize(root) << endl;
  cout << "height of tree = " << treeHeight(root) << endl;
  printData(root);

  return EXIT_SUCCESS;
}

Producción :

size of tree = 45
height of tree = 37
...(elements in the tree)