Implementieren der Binärbaum-Datenstruktur in C++

1. Implementieren Sie den Binärbaum mit dem Schlüsselwort struct in C++
2. Implementieren Sie Funktionen zum Berechnen der Größe und Höhe der Baumstruktur und eine Funktion zum Drucken von Elementen in C++

In diesem Artikel wird erläutert, wie Sie die binäre Baumdatenstruktur in C++ implementieren.

Implementieren Sie den Binärbaum mit dem Schlüsselwort struct in C++

Bäume sind abstrakte Datenstrukturen, die in verschiedenen grundlegenden Algorithmen verwendet werden. Es handelt sich im Allgemeinen um hierarchische Strukturen, bei denen ein Wurzelknoten und seine Kinder Unterbäume bilden müssen. Außerdem gibt es mehrere Baumstrukturtypen, die jeweils für bestimmte Anforderungen geeignet sind und einige Kompromisse bieten.

Ein binärer Baum ist eine der Unterklassen von Baumdatenstrukturen und wird als ein Baum definiert, bei dem jeder Knoten höchstens zwei Kinder haben muss, einschließlich der Kinderknoten, die als left und right bezeichnet werden. In diesem Fall implementieren wir einen Binärbaum mit der Funktion struct, da sie eine Klasse deklariert, deren Member standardmäßig öffentlich sind. Ein Knoten in einem binären Baum enthält zwei Zeiger auf die linken/rechten Knoten und die erforderlichen Daten. Beachten Sie, dass wir nur zu Erklärungszwecken ein einzelnes int-Element für die im Knoten gespeicherten Daten deklariert haben.

Wir definieren einen Konstruktor, der eine ganze Zahl als Argument nimmt und das Element data mit seinem Wert initialisiert. Dann initialisiert es die Zwei-Knoten-Zeiger mit nullptr-Werten, was eine übliche Art ist, die Blattknoten zu bezeichnen. Der Beispieltreibercode erstellt ein Beispieldiagramm und speichert zufällige ganze Zahlen in jedem Knoten. Es gibt mehrere Untertypen von Binärbäumen, z. B. ist ein vollständiger Binärbaum eine Struktur, bei der jeder Knoten 0 oder 2 Kinder hat. Ein anderer wird als perfekter Binärbaum bezeichnet, bei dem alle inneren Knoten zwei Kinder haben und alle Blattknoten identische Tiefen haben.

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

Beachten Sie, dass der obige Code zu einer vollständigen binären Baumstruktur führt, wie in der folgenden Grafik dargestellt. Wir haben jeden Knoten mit dem Operator new zugewiesen und einen Initialisiererwert mit dem Pseudo-Zufallszahlengenerator übergeben.

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

Implementieren Sie Funktionen zum Berechnen der Größe und Höhe der Baumstruktur und eine Funktion zum Drucken von Elementen in C++

Da die Baumstruktur die Form ist, in der Teile-und-Eroberungs-Algorithmen ausgeführt werden, wird die letztere Methode häufig verwendet, um die Funktionen zu implementieren, die ihre Elemente manipulieren. Die Funktion treeSize ermittelt die Grösse des Baumes, die die Anzahl aller Knoten inklusive der Wurzel angibt. Beachten Sie, dass wir nur eine einfache Rekursion verwenden und die Größe des root-Werts (der 1) plus die Größe der linken/rechten Knoten zurückgeben müssen.

Die nächste Funktion ist treeHeight, die die Höhe des Baums abruft, die allgemein als die Anzahl der Knoten auf dem längsten Pfad von einer Wurzel zu einem Blatt bekannt ist. Diese Funktion verwendet auch die Rekursion, indem sie sich selbst auf beiden untergeordneten Knoten aufruft und die Höhe des root-Werts (der 1) plus den größeren Wert aus den vorherigen Aufrufen zurückgibt.

Andererseits gibt die Funktion printData das Member data von jedem Knoten an den Stream cout aus. Es gibt mehrere Traversierungswege für die binäre Baumstruktur: Inorder-, Preorder- und Postorder-Traversal.

Im folgenden Beispiel wird der Inorder-Traversal-Weg verwendet. Der Prozess druckt die Daten von den am weitesten links liegenden Blattknoten, die nach rechts gehen, zuerst in der gleichen Tiefe und bewegt sich dann zu den oberen Ebenen. Der nächste Codeausschnitt erstellt einen teilweise zufälligen Binärbaum und ruft dann jede der obigen Funktionen darauf auf. Wenn die rekursive Natur dieser Funktionen auf den ersten Blick verwirrend erscheint, sollten Sie versuchen, sie Schritt für Schritt an den kleineren Baumobjekten zu debuggen und das Verhalten bei jedem rekursiven Funktionsaufruf zu beobachten.

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

Ausgabe:

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