Implementieren der Binärbaum-Datenstruktur in C++

Ein Binärbaum in C++ lässt sich mit einem Knoten-struct darstellen, das einen Wert und zwei Verknüpfungen zu Kindknoten enthält. Das folgende Beispiel erstellt einen kleinen Baum, zählt seine Knoten, misst seine Höhe anhand der Kanten und gibt seine Werte per Inorder-Traversierung aus.

Einen Binärbaum mit einem Knoten-struct darstellen

Ein Knoten eines Binärbaums hat höchstens zwei Kinder, die üblicherweise left und right heißen. Ein struct ist ein Klassentyp, dessen Member standardmäßig öffentlich sind. Das macht ihn für diese kleine Datenstruktur praktisch. Jeder Knoten speichert eine Ganzzahl und besitzt seine Kindknoten über std::unique_ptr; ein Nullzeiger kennzeichnet eine fehlende Kindverknüpfung. Er bedeutet nicht selbst, dass der Knoten ein Blatt ist: Ein Blatt ist ein Knoten, dessen beide Kindverknüpfungen null sind.

Ein voller Binärbaum hat an jedem Knoten entweder kein Kind oder zwei Kinder. Ein perfekter Binärbaum ist voll, und alle seine Blätter liegen auf derselben Tiefe. Der unten erstellte Beispielbaum ist voll, aber nicht vollständig: Auf seiner letzten Ebene fehlt vor einem späteren Knoten eine Position. Diese Begriffe beschreiben unterschiedliche Baumformen und sind nicht austauschbar.

Einen kleinen Binärbaum erstellen

Das Programm erstellt diese feste Baumform mit Werten, an denen sich die Traversierung gut nachvollziehen lässt: 8 (left: 3, right: 10 (left: 9, right: 14)).

std::make_unique erstellt jeden Knoten und gibt einen besitzenden Zeiger zurück. Wird ein Zeiger in einen Kindknoten verschoben, geht der Besitz über. So besitzt die Wurzel den gesamten Baum; sobald die Wurzel ihren Gültigkeitsbereich verlässt, werden die Knoten automatisch freigegeben. Damit entfällt die manuelle Bereinigung, die bei direkten Zuweisungen mit new erforderlich wäre.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#include <iostream>
#include <memory>

struct BinTreeNode {
    int data;
    std::unique_ptr<BinTreeNode> left;
    std::unique_ptr<BinTreeNode> right;

    explicit BinTreeNode(int value) : data(value) {}
};

int treeSize(const BinTreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + treeSize(node->left.get()) + treeSize(node->right.get());
}

int treeHeight(const BinTreeNode* node) {
    if (node == nullptr) {
        return -1;
    }
    const int leftHeight = treeHeight(node->left.get());
    const int rightHeight = treeHeight(node->right.get());
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

void printData(const BinTreeNode* node) {
    if (node == nullptr) {
        return;
    }
    printData(node->left.get());
    std::cout << node->data << ' ';
    printData(node->right.get());
}

int main() {
    auto root = std::make_unique<BinTreeNode>(8);
    root->left = std::make_unique<BinTreeNode>(3);
    root->right = std::make_unique<BinTreeNode>(10);
    root->right->left = std::make_unique<BinTreeNode>(9);
    root->right->right = std::make_unique<BinTreeNode>(14);

    std::cout << "size = " << treeSize(root.get()) << '\n';
    std::cout << "height = " << treeHeight(root.get()) << '\n';
    std::cout << "inorder = ";
    printData(root.get());
    std::cout << '\n';
}

Die Funktionen erhalten einen Zeiger auf einen Knoten, ohne den Besitz zu übernehmen. Ein Aufruf mit root.get() gibt ihnen Zugriff auf den Baum; für dessen Lebensdauer bleibt weiterhin der besitzende unique_ptr verantwortlich. Dieselben rekursiven Definitionen funktionieren für jede Baumform. Die unveränderte Beispielausgabe verwendet die englischen Beschriftungen size = und height =. Sie weist fünf Knoten und eine Höhe von zwei Kanten aus.

Knoten zählen und die Baumhöhe berechnen

treeSize gibt für einen fehlenden Teilbaum null zurück. Andernfalls zählt die Funktion den aktuellen Knoten und addiert die Größen beider Kindteilbäume. treeHeight gibt für einen fehlenden Teilbaum -1 zurück und addiert anschließend eins zur größeren Höhe der beiden Kindteilbäume. Bei dieser Konvention zählt die Höhe die Kanten auf dem längsten Pfad von der Wurzel zu einem Blatt: Ein Blatt hat die Höhe 0, und der oben gezeigte Baum hat die Höhe 2. Manche Definitionen zählen stattdessen Knoten; dann hat ein Blatt die Höhe 1. Entscheiden Sie sich für eine Konvention und wenden Sie sie durchgängig an.

Knoten per Inorder-Traversierung ausgeben

printData besucht zuerst den linken Teilbaum, gibt dann den aktuellen Wert aus und besucht anschließend den rechten Teilbaum. Das ist eine Inorder-Traversierung. Bei einem binären Suchbaum gibt sie die Werte sortiert aus; bei einem allgemeinen Binärbaum hält sie lediglich diese Besuchsreihenfolge ein. Weitere Einzelheiten finden Sie in der Anleitung zur Inorder-Traversierung.

Um die Rekursion nachzuvollziehen, verfolgen Sie den Funktionsaufruf an jedem Knoten: Zuerst geht er so weit wie möglich nach links. Beim Zurückkehren zum Elternknoten wird dessen Wert ausgegeben, danach folgt der rechte Teilbaum. Die Werte des Beispiels erscheinen daher in der Reihenfolge 3 8 9 10 14. Der Baum hat fünf Knoten und eine kantenbasierte Höhe von zwei. Das Programm ist in sich geschlossen. Sie können den Knotentyp anpassen oder weitere Operationen ergänzen; achten Sie dabei auf den Besitz der Knoten und auf eine einheitliche Höhenkonvention.