Implementieren einer Binärer Suchbaum-Datenstruktur in C++

1. Implementieren Sie einen Binärer Suchbaum mit dem Schlüsselwort struct in C++
2. Implementierung des binären Suchalgorithmus für einen Binärer Suchbaum in C++

In diesem Handbuch wird gezeigt, wie Sie eine binäre Suchbaum-Datenstruktur in C++ implementieren.

Implementieren Sie einen Binärer Suchbaum mit dem Schlüsselwort struct in C++

Ein binärer Suchbaum (BST) ist ein Sonderfall einer binären Baumdatenstruktur. Die Datenstruktur wird normalerweise verwendet, um eine sortierte Liste von Elementen für eine schnelle Suche unter Verwendung des binären Suchalgorithmus zu speichern. Im Gegensatz zum regulären Binärbaum hat BST in jedem Knoten ein spezielles Datenelement namens Schlüssel, das eindeutige Werte haben muss.

Jeder Knoten in einem BST sollte die folgende Anforderung erfüllen: Der Wert key muss größer sein als alle Schlüssel im Teilbaum seines linken Kindes und kleiner als alle Schlüssel im Teilbaum seines rechten Kindes. Die vorherige Anweisung impliziert, dass die Elemente mit kleineren Schlüsselwerten auf der linken Seite der Baumhierarchie positioniert werden; Dies führt zu einer optimalen Struktur, um die binäre Suche zu verwenden.

Im folgenden Beispielcode definieren wir ein struct namens BSTreeNode, bestehend aus zwei Zeigern auf die linken/rechten Knoten und einem string-Member zur Bezeichnung des Schlüssels. Beachten Sie, dass wir nur die einfachste Version von BST implementieren, bei der der Schlüsselwert mit den im Knoten gespeicherten Daten übereinstimmt.

Im Allgemeinen ist es dem Programmierer freigestellt, einen BST-Knoten zu definieren, um andere Datenelemente nach Bedarf für das spezifische Problem zu speichern. Diese Definition ist am besten geeignet, um das sortierte Array von Strings zu emulieren, das nach einem bestimmten String (Schlüssel) durchsucht werden muss. Bevor wir die binäre Suchfunktion implementieren, muss das BST-Objekt von Grund auf neu konstruiert werden. Daher verwenden wir einen vordefinierten Vektor von Strings, um einen neuen Binärer Suchbaum zu initialisieren.

Die Funktion insertNode ist die rekursive Implementierung, um einen neuen untergeordneten BSTreeNode zu erzeugen, wenn die Wurzel des Baums als Argument übergeben wird. Wenn wir selbst einen Wurzelknoten erstellen müssen, können Sie einen Zeiger auf den Typ BSTreeNode deklarieren, ihm nullptr zuweisen und ihn mit dem entsprechenden string-Wert, der dort gespeichert werden muss, an den insertNode übergeben . Sobald wir die Liste mit dem Inhalt von v1 initialisiert haben, kann die Funktion printTree aufgerufen werden, um alle Schlüsselwerte in der sortierten Reihenfolge zu drucken, die als inorder-Traversal von BST bezeichnet wird.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

void printTree(BSTreeNode *n) {
  if (n != nullptr) {
    printTree(n->left);
    cout << n->key << "; ";
    printTree(n->right);
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printTree(root);

  return EXIT_SUCCESS;
}

Ausgabe:

aim; born; camel; maya; wind; xen; zero;

Implementierung des binären Suchalgorithmus für einen Binärer Suchbaum in C++

Der binäre Suchalgorithmus ist bei der BST-Struktur aufgrund der Ordnung effizient, bei der die Schlüssel in der Hierarchie gespeichert werden. Es gibt drei Hauptoperationen, die für die BSTs implementiert sind: Einfügen, Löschen und Nachschlagen.

Im folgenden Beispiel konzentrieren wir uns mehr auf die Suche. Die Funktion findNode ist für das Nachschlagen des angegebenen Schlüssels im BST verantwortlich, der über seinen Wurzelknoten an eine Funktion übergeben wird. Dieser Befehl ist rekursiv und gibt den Zeiger auf den BSTreeNode zurück, wo der Schlüssel gespeichert ist. Wird der Schlüsselwert in keinem Knoten gefunden, wird nullptr zurückgegeben. Zur besseren Demonstration haben wir auch eine printNode-Funktion implementiert, die den Knotenzeiger nimmt und den Schlüsselwert an den cout-Stream ausgibt, um den Rückgabewert der findNode-Funktion direkt in der Funktion zu verketten, um ihn zu drucken.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

BSTreeNode *findNode(BSTreeNode *root, const string &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 printNode(BSTreeNode *n) {
  if (n != nullptr) {
    cout << n->key << endl;
  } else {
    cout << "Not a valid node!" << endl;
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printNode(findNode(root, "zero"));
  printNode(findNode(root, "zeroo"));

  return EXIT_SUCCESS;
}

Ausgabe:

zero
Not a valid node!