Imprimir datos en árbol binario nivel por nivel en C++

1. Escriba un algoritmo usando la cola para imprimir datos en un árbol binario nivel por nivel en C++
2. Use el nodo de lista enlazada para imprimir datos en el árbol binario nivel por nivel en C++
3. Utilice la técnica Hashing para imprimir datos en un árbol binario nivel por nivel en C++

El recorrido nivel por nivel del árbol binario se conoce como recorrido Breadth-first. Este tutorial le enseñará cómo imprimir datos en un árbol binario nivel por nivel en C++ y lo familiarizará con diferentes métodos para realizar esta tarea.

El uso de una cola es la forma adecuada de imprimir datos en un árbol binario nivel por nivel, ya que una pila es para el recorrido de primero en profundidad. Sin embargo, hay tres formas diferentes de lograr este objetivo: escribir su propio algoritmo usando una cola (o nodo de lista enlazada) o usando la técnica Hashing.

Escriba un algoritmo usando la cola para imprimir datos en un árbol binario nivel por nivel en C++

En C++, puede usar las funciones de la cola al incluir #include<queue> para escribir un algoritmo que imprima datos en un árbol binario nivel por nivel en orden ordenado. Como la cola sigue el principio FIFO (Primero en entrar, primero en salir), debe inicializar una cola y enviarle la raíz.

Escriba un algoritmo lógico y aplíquelo al árbol binario de entrada, y puede usar el nodo nulo (para separar los nodos por una nueva línea). Recuerde, su interacción con un nodo nulo significa que ningún nodo no visitado ha permanecido en el nivel actual, y puede imprimir una nueva línea.

Al final de cada nivel del árbol binario, debe haber un nodo nulo que represente su final. Inicializar una cola para almacenar datos de tipo nodos, empujar la raíz hacia ella y finalmente empujar el nodo “nulo” a la cola puede insertar un nodo “nulo” a un nivel.

#include <iostream>
#include <queue>

using namespace std;

class binT_node {
 public:
  int nodeData;

  // declare left and right nodes of the binary tree
  binT_node* left;
  binT_node* right;

  binT_node(int data, binT_node* lef, binT_node* rig) {
    nodeData = data;
    left = lef;
    right = rig;
  }
};

void print_dataT(binT_node* root) {
  queue<binT_node*> que;
  que.push(root);

  while (true) {
    int orderLength = que.size();

    if (orderLength == 0) {
      break;
    }

    int i = 0;

    while (i < orderLength) {
      binT_node* nod = que.front();
      cout << (nod->nodeData) << " ";

      if (nod->left != NULL) {
        que.push(nod->left);
      }

      if (nod->right != NULL) {
        que.push(nod->right);
      }

      que.pop();
      i++;
    }

    cout << endl;
  }
}

int main() {
  binT_node* rootNode;
  rootNode = new binT_node(1, NULL, NULL);
  rootNode->left = new binT_node(2, NULL, NULL);
  rootNode->right = new binT_node(3, NULL, NULL);
  rootNode->left->left = new binT_node(4, NULL, NULL);
  rootNode->left->right = new binT_node(5, NULL, NULL);
  rootNode->right->left = new binT_node(6, NULL, NULL);
  rootNode->right->right = new binT_node(7, NULL, NULL);
  print_dataT(rootNode);

  return 0;
}

Producción :

1
2 3
4 5 6 7

Es posible imprimir nodos al mismo nivel en una iteración en lugar de imprimir un nodo en cada iteración, y es otro enfoque bien conocido para escribir algoritmos similares en C++.

Este enfoque es un poco similar al primero, incluida la inicialización de la cola y el envío de los nodos raíz y nulo.

Además, si temp no es “nulo”, imprima el valor del nodo temp, presione temp.left para poner en cola si no es nulo, y presione temp.right para poner en cola si no es nulo, repita los pasos hasta que la cola esté vacía.

Use el nodo de lista enlazada para imprimir datos en el árbol binario nivel por nivel en C++

Visitar un nodo para colocar sus nodos secundarios en una cola FIFO es un enfoque estándar porque también puede implementar una cola como una lista vinculada. Sin embargo, es posible imprimir el nivel actual del árbol binario usando una función en C++.

En primer lugar, utilice la cola (BFS) para atravesar el orden de niveles del árbol binario mediante la creación de una Lista de matrices de los nodos de la lista enlazada. Las variables pueden almacenar el tamaño de la cola y son valiosas para recuperar y manipular todos los nodos en cada nivel del árbol binario.

Ahora, mientras la variable que almacena el tamaño de la cola es mayor que cero, acceda a la variable y recupere, imprima o manipule todos los nodos agregando sus hijos a la cola.

Esta solución recursiva es completamente funcional pero no tan efectiva como una cola o una técnica Hashing.

#include <iostream>

using namespace std;

class listNode {
 public:
  int data;
  listNode *left, *right;
};

void print_data(listNode* root_node, int level_order);
int lev_height(listNode* node);
listNode* updatedNode(int data);

void printData_LevelOrder(listNode* root_node) {
  int heig = lev_height(root_node);
  int init;
  for (init = 1; init <= heig; init++) print_data(root_node, init);
}

void print_data(listNode* root_node, int level_order) {
  // in case of a `null` or empty root
  if (root_node == NULL) return;

  // in case if root represents `1`
  if (level_order == 1) cout << root_node->data << " ";

  // in case the root is greater than `1`
  else if (level_order > 1) {
    print_data(root_node->left, level_order - 1);
    print_data(root_node->right, level_order - 1);
  }
}

int lev_height(listNode* node_linkedlist) {
  // in case of empty or `NULL`
  if (node_linkedlist == NULL)
    return 0;
  else {
    int level_leftHeight = lev_height(node_linkedlist->left);
    int level_rightHeight = lev_height(node_linkedlist->right);

    // in case the left node is greater than the right node
    if (level_leftHeight > level_rightHeight) {
      return (level_leftHeight + 1);
    }

    // in case the right node is greater than the left node
    else {
      return (level_rightHeight + 1);
    }
  }
}

listNode* updatedNode(int _listdata) {
  listNode* list_node = new listNode();
  list_node->data = _listdata;
  list_node->left = NULL;
  list_node->right = NULL;

  return (list_node);
}

int main() {
  listNode* linkedlistNode = updatedNode(1);
  linkedlistNode->left = updatedNode(2);
  linkedlistNode->right = updatedNode(3);
  linkedlistNode->left->left = updatedNode(4);
  linkedlistNode->left->right = updatedNode(5);

  cout << "Level by Level Data Insertion to a Binary Tree is Complete! \n";
  printData_LevelOrder(linkedlistNode);

  return 0;
}

Producción :

Level by Level Data Insertion to a Binary Tree is Complete!
1 2 3 4 5

El printLevelOrder y printCurrentLevel son las subfunciones de este enfoque (usando una lista enlazada para imprimir datos en el árbol binario) que imprimen todos los nodos en un nivel dado o imprimen el recorrido del orden de nivel del árbol binario, respectivamente .

Además, la subfunción printLevelOrder puede aprovechar la función printCurrentLevel para imprimir los nodos uno por uno comenzando desde la raíz en todos los niveles del árbol binario.

La complejidad temporal de Breath-First Search (BFS) es O(n^2), donde n representa el número máximo de nodos del árbol binario y O(h) es el espacio auxiliar requerido por el programa C++ donde la h representa la altura completa de un árbol binario.

Cada algoritmo que encontrará en este tutorial puede manejar todo tipo de árbol binario, incluidos; árboles binarios completos, perfectos, completos, degenerados o patológicos, sesgados y equilibrados.

Utilice la técnica Hashing para imprimir datos en un árbol binario nivel por nivel en C++

Como parte de la técnica hash, las tablas hash permiten imprimir datos en un árbol binario nivel por nivel y han demostrado ser estructuras de datos extremadamente útiles que toman el tiempo de búsqueda O(1) de una tabla hash en promedio.

Puede resolver varios problemas relacionados con algoritmos y estructuras de datos binarios de manera extremadamente eficiente para reducir la complejidad del tiempo.

El Hashing incluye multimapa, que permite el mapeo de una sola clave a múltiples valores y lo usa para almacenar los nodos del árbol binario y su nivel.

La técnica hash utiliza el número de nivel del árbol binario (almacenado en una variable) como clave e imprime todos los nodos correspondientes a cada nivel, comenzando por el nodo principal o el primer nivel del árbol binario.

#include <iostream>

// associative container that contains key-value pairs
// search, insert and remove elements in average constant-time complexity
#include <unordered_map>
#include <vector>  // initialize the vector contents

using namespace std;

// data structure creation | fulfill the purpose of storing data in a binary
// table
struct _hashnode {
  int key;
  _hashnode *left, *right;

  // `key` -> `_nodekey` will contain all the binary tree info to arrange the
  // nodes
  _hashnode(int _nodekey) {
    this->key = _nodekey;
    this->left = this->right = nullptr;
  }
};

// enable nodes storage in a map (to traverse the tree in a pre_order fashion)
// corresponding to the node's level
void hash_preorder(_hashnode* hash_root, int level, auto& map) {
  // initially: empty binary table
  if (hash_root == nullptr) {
    return;
  }

  // current node and its level insertion into the map
  map[level].push_back(hash_root->key);

  hash_preorder(hash_root->left, level + 1, map);
  hash_preorder(hash_root->right, level + 1, map);
}

// recursive function | fulfill the purpose of printing binary tree's level
// order traversal
void traversal_throughHash(_hashnode* hash_root) {
  // creation of a `null` or an empty map | to store nodes between the given
  // levels of a binary tree
  unordered_map<int, vector<int>> map;

  /* level-wise insertion of nodes to the map after the tree traversal */
  hash_preorder(hash_root, 1, map);

  for (int init = 1; map[init].size() > 0; init++) {
    cout << "[Binary Tree] Level " << init << ":- ";
    for (int juan : map[init]) {
      cout << juan << " ";
    }
    cout << endl;
  }
}

int main() {
  _hashnode* hash_Root = new _hashnode(15);
  hash_Root->left = new _hashnode(10);
  hash_Root->right = new _hashnode(20);
  hash_Root->left->left = new _hashnode(8);
  hash_Root->left->right = new _hashnode(12);
  hash_Root->right->left = new _hashnode(16);
  hash_Root->right->right = new _hashnode(25);
  hash_Root->right->right->right = new _hashnode(30);

  traversal_throughHash(hash_Root);

  return 0;
}

Producción :

[Binary Tree] Level 1:- 15
[Binary Tree] Level 2:- 10 20
[Binary Tree] Level 3:- 8 12 16 25
[Binary Tree] Level 4:- 30

En general, un árbol binario actúa como una estructura de datos en la que el nodo superior es el nodo principal o raíz, y cada nodo principal representa un par de nodos secundarios.

Hay cuatro formas comunes de recorrido de árboles binarios, y el recorrido de orden nivel por nivel es uno de los más eficientes.

Es un hecho que ningún algoritmo basado en “ordenar por comparación” puede funcionar mejor que el rendimiento n log n. Cada nodo del te binario representa una comparación entre sus nodos hijos (ai ≤ aj), y representan uno de los n!.

Un árbol binario contiene n = (2^h) - 1 nodos donde h representa la altura del árbol binario, y cada nodo que no es hoja tiene nodos secundarios derecho e izquierdo.

Puede determinar la altura de un árbol binario calculando h = [log(n!)] para un árbol con n! nodos hoja y altura h = log(n + 1).