Einfügen von Binärer Suchbaum in C++

In diesem Artikel wird veranschaulicht, wie die Einfügefunktion für die binäre Suchbaumdatenstruktur in C++ implementiert wird.

Neue Knoten in den Binärer Suchbaum in C++ einfügen

Binäre Bäume repräsentieren im Allgemeinen eine Untermenge von Baumstrukturen. Sie werden binär genannt, weil sie an jedem Knoten höchstens zwei Kinder haben. In diesem Fall diskutieren wir einen Binärer Suchbaum, bei dem jeder Knoten ein Datenelement namens Schlüssel enthält, und auf jeder Ebene des Baums muss der Schlüssel des gegebenen Knotens größer als Schlüssel in seinem linken Unterbaum und kleiner als alle Schlüssel in der rechten sein Unterbaum. Diese Funktion ermöglicht es uns, einen binären Suchalgorithmus für den Baum zu verwenden, während wir in einem sortierten Array suchen.

Zuerst müssen wir einen Baumknoten struct deklarieren, der zwei Zeiger auf left/right Knoten und einen Schlüssel enthält. Der Einfachheit halber speichern wir Schlüssel als int-Werte, aber je nach Problem muss man möglicherweise ein anderes Layout für den Knoten erstellen. Wir konstruieren diesen Baum auch manuell, indem wir einen einzelnen TreeNode-Zeiger als Wurzel des Baums deklarieren und dann die Funktion insertNode aufrufen, um neue Knoten hinzuzufügen.

Zur besseren Demonstration und Verifizierung unseres Beispiels fügen wir auch eine Funktion hinzu, um einen Knoten mit dem angegebenen Schlüssel zu finden und eine andere, um den Inhalt des gesamten Baums zu drucken. Letzteres hilft uns, die Baumstruktur bei jedem Schritt des Programms leicht zu überprüfen. Beachten Sie, dass alle drei Funktionen Rekursion verwenden, da eine Baumstruktur Teil- und Eroberungsalgorithmen inhärent ist.

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

Ausgabe:

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

In der Funktion main deklarieren wir zwei beliebige int-Vektoren und schieben dann ihre Elemente in den Baum. Beachten Sie, dass unsere Funktion insertNode zwei Parameter benötigt - Wurzelknoten und einen Schlüsselwert. Es muss prüfen, ob der angegebene Root-Knoten gültig ist oder nur ein nullptr, wobei letzteres anzeigt, dass die Funktion den Inhalt des Root-Knotens erstellen muss.

Wenn der Wurzelknoten bereits initialisiert ist, sollte die Funktion gemäß dem Schlüsselwert fortfahren, der mit dem Schlüssel des aktuellen Knotens verglichen wird. Wenn der Wert des übergebenen Schlüssels kleiner als der angegebene Schlüssel ist, sollten wir zum linken Teilbaum vorrücken. Ansonsten - der richtige Teilbaum.

Schließlich erreichen wir den Knoten, in dem der Schlüssel gespeichert werden muss, und der inorder-Traversal gibt immer die sortierten Schlüsselwerte aus, wie im Code-Snippet gezeigt.