Drucken Sie Daten im Binärbaum Ebene für Ebene in C++

1. Schreiben Sie einen Algorithmus, der die Warteschlange verwendet, um Daten in einem binären Baum Ebene für Ebene in C++ zu drucken
2. Verwenden Sie den verknüpften Listenknoten, um Daten im binären Baum Ebene für Ebene in C++ zu drucken
3. Verwenden Sie die Hashing-Technik, um Daten im Binärbaum Ebene für Ebene in C++ zu drucken

Das Durchlaufen des Binärbaums Ebene für Ebene wird als Breite-zuerst-Durchquerung bezeichnet. Dieses Tutorial wird Ihnen beibringen, wie Sie Daten in einem binären Baum Ebene für Ebene in C++ drucken und Sie mit verschiedenen Methoden vertraut machen, um diese Aufgabe auszuführen.

Die Verwendung einer Warteschlange ist der richtige Weg, um Daten in einem binären Baum Ebene für Ebene zu drucken, da ein Stack für die Tiefen-zuerst-Durchquerung dient. Es gibt jedoch drei verschiedene Möglichkeiten, dieses Ziel zu erreichen: Schreiben Sie Ihren eigenen Algorithmus unter Verwendung einer Warteschlange (oder eines verknüpften Listenknotens) oder verwenden Sie die Hashing-Technik.

Schreiben Sie einen Algorithmus, der die Warteschlange verwendet, um Daten in einem binären Baum Ebene für Ebene in C++ zu drucken

In C++ können Sie die Funktionen der Warteschlange nutzen, indem Sie #include<queue> einfügen, um einen Algorithmus zu schreiben, der Daten in einem binären Baum Ebene für Ebene in sortierter Reihenfolge ausgibt. Da die Warteschlange dem FIFO-Prinzip (First-In-First-Out-Prinzip) folgt, sollten Sie eine Warteschlange initialisieren und die Wurzel dorthin verschieben.

Schreiben Sie einen logischen Algorithmus und wenden Sie ihn auf den Eingabe-Binärbaum an, und Sie können den null-Knoten verwenden (um die Knoten durch einen Zeilenumbruch zu trennen). Denken Sie daran, dass Ihre Interaktion mit einem null-Knoten bedeutet, dass kein nicht besuchter Knoten auf der aktuellen Ebene verblieben ist, und Sie können einen Zeilenumbruch drucken.

Am Ende jeder Binärbaumebene sollte ein null-Knoten sein, der sein Ende darstellt. Das Initialisieren einer Warteschlange zum Speichern von Daten vom Typ nodes, das Pushen von root darauf und das abschließende Pushen des null-Knotens in die Warteschlange kann einen null-Knoten auf einer Ebene einfügen.

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

Ausgang:

1
2 3
4 5 6 7

Es ist möglich, Knoten auf derselben Ebene in einer Iteration zu drucken, anstatt bei jeder Iteration einen Knoten zu drucken, und dies ist ein weiterer bekannter Ansatz zum Schreiben ähnlicher Algorithmen in C++.

Dieser Ansatz ist dem ersten ein wenig ähnlich, einschließlich der Initialisierung der Warteschlange und dem Pushen der Knoten root und null.

Wenn temp nicht null ist, drucken Sie außerdem den Wert des Knotens temp, drücken Sie temp.left, um es in die Warteschlange zu stellen, wenn es nicht null ist, und drücken Sie temp.right, um es in die Warteschlange zu stellen, wenn es nicht null ist, wiederholen Sie den Vorgang die Schritte, bis die Warteschlange leer ist.

Verwenden Sie den verknüpften Listenknoten, um Daten im binären Baum Ebene für Ebene in C++ zu drucken

Das Besuchen eines Knotens, um seine untergeordneten Knoten in eine FIFO-Warteschlange zu stellen, ist ein Standardansatz, da Sie eine Warteschlange auch als verknüpfte Liste implementieren können. Es ist jedoch möglich, die aktuelle Ebene des Binärbaums mit einer Funktion in C++ auszudrucken.

Verwenden Sie zuerst die Warteschlange (BFS) für das Durchlaufen der Ebenenreihenfolge des Binärbaums, indem Sie eine ArrayList der verknüpften Listenknoten erstellen. Variablen können die Warteschlangengröße speichern und sind wertvoll zum Abrufen und Manipulieren aller Knoten auf jeder Binärbaumebene.

Greifen Sie nun, während die Variable, die die Warteschlangengröße speichert, größer als Null ist, auf die Variable zu und rufen Sie alle Knoten ab, drucken Sie sie aus oder manipulieren Sie sie, indem Sie ihre Kinder zur Warteschlange hinzufügen.

Diese rekursive Lösung ist voll funktionsfähig, aber nicht so effektiv wie eine Warteschlangen- oder Hashing-Technik.

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

Ausgang:

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

printLevelOrder und printCurrentLevel sind die Unterfunktionen dieses Ansatzes (unter Verwendung einer verknüpften Liste zum Drucken von Daten im Binärbaum), die alle Knoten auf einer bestimmten Ebene drucken bzw. die Durchquerung der Ebenenreihenfolge des Binärbaums drucken .

Darüber hinaus kann die Unterfunktion printLevelOrder die Funktion printCurrentLevel nutzen, um Knoten nacheinander ausgehend von der Wurzel auf allen Ebenen des Binärbaums zu drucken.

Die Zeitkomplexität der Breath-First Search (BFS) beträgt O(n^2), wobei das n die maximale Anzahl von Binärbaumknoten darstellt und O(h) der benötigte Hilfsraum ist das C++-Programm, wobei das h die vollständige Höhe eines Binärbaums darstellt.

Jeder Algorithmus, den Sie in diesem Tutorial finden, kann jede Art von Binärbaum verarbeiten, einschließlich; vollständige, perfekte, vollständige, degenerierte oder pathologische, schiefe und ausgeglichene Binärbäume.

Verwenden Sie die Hashing-Technik, um Daten im Binärbaum Ebene für Ebene in C++ zu drucken

Als Teil der Hash-Technik ermöglichen Hash-Tabellen das Drucken von Daten in einem binären Baum Ebene für Ebene und haben sich als äußerst nützliche Datenstrukturen erwiesen, die im Durchschnitt die O(1)-Suchzeit einer Hash-Tabelle benötigen.

Es kann mehrere Probleme im Zusammenhang mit Algorithmen und binären Datenstrukturen äußerst effizient lösen, um die Zeitkomplexität zu reduzieren.

Das Hashing beinhaltet multimap, das die Zuordnung eines einzelnen Schlüssels zu mehreren Werten ermöglicht und es zum Speichern von Binärbaumknoten und seiner Ebene verwendet.

Die Hash-Technik verwendet die Nummer der Binärbaumebene (in einer Variablen gespeichert) als Schlüssel und gibt alle entsprechenden Knoten auf jeder Ebene aus, beginnend mit dem übergeordneten Knoten oder der ersten Ebene des Binärbaums.

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

Ausgang:

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

Im Allgemeinen fungiert ein Binärbaum als Datenstruktur, bei der der oberste Knoten der Eltern- oder Wurzel-Knoten ist und jeder Eltern-Knoten ein Paar untergeordneter Knoten darstellt.

Es gibt vier gängige Arten des Durchlaufens von Binärbäumen, und das Durchlaufen der Reihenfolge Ebene für Ebene ist eine der effizientesten.

Es ist eine Tatsache, dass kein Algorithmus, der auf Sortieren nach Vergleich basiert, besser abschneiden kann als n log n-Leistung. Jeder Knoten des binären Tees repräsentiert einen Vergleich zwischen seinen Kindknoten (ai ≤ aj), und sie repräsentieren eines der n!.

Ein Binärbaum enthält n = (2^h) - 1 Knoten, wobei h die Höhe des Binärbaums darstellt und jeder Nicht-Blatt-Knoten sowohl rechte als auch linke untergeordnete Knoten hat.

Die Höhe eines Binärbaums können Sie bestimmen, indem Sie h = [log(n!)] für einen Baum mit n! berechnen. Blattknoten und h = log(n + 1) Höhe.