Aufgabe 14

Schwierigkeitsgrad: Mittel

Themen: Zeiger Rekursion Programmausgane Kontrollstrukturen Funktionen

---

Aufgabenstellung

Erstellen Sie einen Binary Tree. Ein Binary Tree ist ein spezieller Baum, bei dem jedes Element (Knoten) höchstens zwei Nachfolger hat: einen linken und einen rechten. Dabei gilt: Das linke Element ist kleiner, das rechte Element ist größer als der Wert des aktuellen Knotens.

Zur Vereinfachung ist die Klasse für einen Knoten bereits vorgegeben:

class Node
{
public:
    int data;
    Node *left;
    Node *right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

Implementieren Sie die folgenden drei Funktionen mithilfe von Rekursion:

• void insert(Node *&root, int value) (fügt ein neues Element in den Baum ein und ordnet es an der richtigen Position ein)
• void inorderTraversal(Node *root) (gibt alle Elemente des Baums in aufsteigender Reihenfolge aus)
• void deleteTree(Node *&root) (löscht alle dynamisch allozierten Knoten und gibt den belegten Speicher frei)

 

Lösung

#include <iostream>
using std::cout, std::endl;

class Node
{
public:
    int data;
    Node *left;
    Node *right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

void insert(Node *&root, int value)
{
    if (root == nullptr)
    {
        root = new Node(value);
        return;
    }
    if (value < root->data)
    {
        insert(root->left, value);
    }
    else
    {
        insert(root->right, value);
    }
}

void inorderTraversal(Node *root)
{
    if (root != nullptr)
    {
        inorderTraversal(root->left);
        cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

void deleteTree(Node *&root)
{
    if (root != nullptr)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }
}

int main()
{
    Node *root = nullptr;
    insert(root, 5);
    insert(root, 3);
    insert(root, 7);
    insert(root, 2);
    insert(root, 4);
    insert(root, 6);
    insert(root, 3);
    insert(root, 8);

    cout << "Inorder Traversal: ";
    inorderTraversal(root);
    cout << endl;

    deleteTree(root);

    return 0;
}

---