ADS/P1/ADS_P1_2_Binaerbaum/Tree.cpp

/*************************************************
 * ADS Praktikum 1.2
 * Tree.cpp
 * Erweiterung um Hilfsfunktionen gestattet.
 *************************************************/
#include "Tree.h"
#include "TreeNode.h"
#include <iomanip>
#include <iostream>
#include <queue>

using namespace std;


Tree::Tree() {
    currentNodeChronologcalID = 0;
}
Tree::~Tree() {
    while (m_anker != nullptr) {
        deleteNode(m_anker->getNodeOrderID());
    }
}

TreeNode* Tree::getAnker() {
    return m_anker;
}

void Tree::setAnker(TreeNode* node) {
    m_anker = node;
}

void Tree::addNode(string Name, int Age, double Income, int PostCode) {
    TreeNode* newNode = new TreeNode { Age + int(Income) + PostCode , currentNodeChronologcalID++, Name, Age, Income, PostCode };
    TreeNode* ptr = getAnker();
    TreeNode* tmp = nullptr;

    /*
     * Allg. Baumaufbau
     *      Anker
     *  klein -> groß
     */

     // bis zum passenden Parentknoten traversieren
    while (ptr != nullptr) {
        tmp = ptr;
        // wenn NodeID > ptrID dann rechts sonst links
        // Dublikate?
        newNode->getNodeOrderID() > ptr->getNodeOrderID() ?
            ptr = ptr->getRight() : ptr = ptr->getLeft();
    }

    if (getAnker() == nullptr)
        setAnker(newNode);

    // wenn NodeID > tmpID dann rechts sonst links
    else newNode->getNodeOrderID() > tmp->getNodeOrderID() ?
        tmp->setRight(newNode) : tmp->setLeft(newNode);
}

bool Tree::deleteNode(int delNodeID) {
    // Baum ist leer
    if (!getAnker())
        return false;

    // Loeschen von Nodes - ab Wurzel
    if (getAnker()->getNodeOrderID() == delNodeID) {

        // 1. Fall: der Baum bestehet aus 1 Knoten.
        if (!getAnker()->getRight() && !getAnker()->getLeft()) {
            delete getAnker();
            setAnker(nullptr);
            cout << "+ Datensatz wurde gelöscht.\n";
            return true;
        }

        // 2. Fall: Wurzel, mit einem Nachfolger
        else if ((getAnker()->getRight() && !getAnker()->getLeft()) || (!getAnker()->getRight() && getAnker()->getLeft())) {
            TreeNode* tmp = getAnker();

            // Nachfolger wird Anker
            getAnker()->getRight() ?
                setAnker(getAnker()->getRight()) : setAnker(getAnker()->getLeft());
            delete tmp;
            cout << "+ Datensatz wurde gelöscht.\n";
            return true;
        }

        // 3. Fall: Wurzel, mit zwei Nachfolger
        else if (getAnker()->getRight() && getAnker()->getLeft()) {
            TreeNode* minimumRTB = getAnker()->getRight();
            TreeNode* minimumParent = nullptr;

            // Minimum von RTB suchen.
            while (minimumRTB->getLeft() != nullptr) {
                minimumParent = minimumRTB;
                minimumRTB = minimumRTB->getLeft();
            }

            // Minimum von RTB gefunden
            if (minimumParent != nullptr) {
                minimumParent->setLeft(minimumRTB->getRight());
                minimumRTB->setLeft(getAnker()->getLeft());
                minimumRTB->setRight(getAnker()->getRight());
            }

            // Minimum von RTB ist RTB-Wurzel (RTB->left == nullptr)
            else
                minimumRTB->setLeft(getAnker()->getLeft());

            delete getAnker();
            setAnker(minimumRTB);
            cout << "+ Datensatz wurde gelöscht.\n";
            return true;
        }
    }

    // Loeschen von Nodes - Node != Wurzel
    else {
        // zu loeschende Node und Parent_Node 
        TreeNode* ptr = getAnker();
        TreeNode* parent = getAnker();

        // suche zuloeschenden Node
        while ((ptr->getRight() || ptr->getLeft()) && ptr->getNodeOrderID() != delNodeID && ptr) {
            parent = ptr;
            delNodeID < ptr->getNodeOrderID() ?
                ptr = ptr->getLeft() : ptr = ptr->getRight();
        }

        // 1. Fall Loeschen von Nodes - ohne Nachfolger
        if (!ptr->getRight() && !ptr->getLeft()) {
            parent->getNodeOrderID() < ptr->getNodeOrderID() ?
                parent->setRight(nullptr) : parent->setLeft(nullptr);
            delete ptr;
            cout << "+ Datensatz wurde gelöscht.\n";
            return true;
        }

        // 2. Fall Loeschen von Nodes - mit einem Nachfolger
        else if ((!ptr->getRight() && ptr->getLeft()) || (ptr->getRight() && !ptr->getLeft())) {
            if (parent->getNodeOrderID() < ptr->getNodeOrderID())
                ptr->getRight() ?
                parent->setRight(ptr->getRight()) : parent->setRight(ptr->getLeft());
            else
                ptr->getRight() ?
                parent->setLeft(ptr->getRight()) : parent->setLeft(ptr->getLeft());

            delete ptr;
            cout << "+ Datensatz wurde gelöscht.\n";
            return true;
        }

        // 3. Fall Loeschen von Nodes - mit zwei Nachfolger
        if (ptr->getRight() != nullptr && ptr->getLeft() != nullptr) {
            TreeNode* minimumRTB = ptr->getRight();
            TreeNode* minimumParent = nullptr;

            //Minumum von RTB suchen.
            while (minimumRTB->getLeft() != nullptr) {
                minimumParent = minimumRTB;
                minimumRTB = minimumRTB->getLeft();
            }

            //Minimum von RTB gefunden
            if (minimumParent != nullptr) {
                minimumParent->setLeft(minimumRTB->getRight());
                minimumRTB->setLeft(ptr->getLeft());
                minimumRTB->setRight(ptr->getRight());
            }

            //Minimum von RTB ist RTB-Wurzel (RTB->left == nullptr)
            else
                minimumRTB->setLeft(ptr->getLeft());

            //verknuepfe parent von zu loeschende Node
            parent->getNodeOrderID() < ptr->getNodeOrderID() ?
                parent->setRight(minimumRTB) :
                parent->setLeft(minimumRTB);

            delete ptr;
            cout << "+ Datensatz wurde gelöscht.\n";
            return true;
        }
    }
    return false;
}

bool Tree::searchNode(std::string name) {

    // Baum muss vorhanden sein
    if (getAnker() != nullptr) {
        bool found = false;
        TreeNode* ptr = getAnker();
        TreeNode* node;

        cout << endl <<
            "ID | Name       | Alter | Einkommen | PLZ   | OrderID\n"
            "---+------------+-------+-----------+-------+--------\n";

        queue<TreeNode*> q;
        q.push(ptr);
        while (!q.empty()) {
            node = q.front();
            q.pop();
            if (node->getName() == name) {
                printNode(node);
                found = true;
                // break; // damit werden alle Knoten mit dem Namen ausgegeben
            }
            if (node->getLeft() != nullptr)
                q.push(node->getLeft());
            if (node->getRight() != nullptr)
                q.push(node->getRight());
        }

        if (!found)
            cout << "--------------- Kein Eintrag vorhanden --------------" << endl;
        return found;
    }
    else
        return false;
}

void Tree::printNode(TreeNode* node) {
    cout << setw(3) << node->getNodeChronologicalID() << '|' << setw(12) << node->getName() << '|'
        << setw(7) << node->getAge() << '|' << setw(11) << node->getIncome() << '|'
        << setw(7) << node->getPostCode() << '|' << setw(8) << node->getNodeOrderID() << endl;
}

void Tree::printLevelOrder() {

    TreeNode* root = getAnker();

    // 2 Queues instanzieren
    std::queue<TreeNode*> q;
    std::queue<int> nq;

    cout << endl <<
        "ID | Name       | Alter | Einkommen | PLZ   | OrderID\n"
        "---+------------+-------+-----------+-------+--------\n";

    if (root == nullptr) {
        cout << "--------------- Kein Eintrag vorhanden --------------" << endl;
        return;
    }

    // Wurzelknoten und Startniveau in die Queues pushen
    q.push(root);
    nq.push(0);

    // vorheriges Niveau merken bzw. den Niveauwechsel irgendwie mitbekommen
    int prev_niveau = -1;
    int niveau;

    // Schleife
    while (!q.empty()) {
        // Entnahme aus den Queues und loeschen
        TreeNode* ptr = q.front();
        q.pop();
        niveau = nq.front();
        nq.pop();

        // Ausgabe Niveauwechsel
        if (prev_niveau != niveau) {
            std::cout << std::endl << "Niveau " << niveau << ": " << endl;
            prev_niveau = niveau;
        }
        // Ausgabe des Knotens
        printNode(ptr);

        // Linker Nachfolgeknoten in die Queues
        if (ptr->getLeft() != nullptr) {
            q.push(ptr->getLeft());
            nq.push(niveau + 1);
        }
        // Rechter Nachfolgeknoten in die Queues
        if (ptr->getRight() != nullptr) {
            q.push(ptr->getRight());
            nq.push(niveau + 1);
        }
    }
}

void Tree::printPreOrder(TreeNode* ptr) {
    if (ptr != nullptr) {
        printNode(ptr);
        printPreOrder(ptr->getLeft());
        printPreOrder(ptr->getRight());
    }
}

void Tree::printPostOrder(TreeNode* ptr) {
    if (ptr != nullptr) {
        printPreOrder(ptr->getLeft());
        printPreOrder(ptr->getRight());
        printNode(ptr);
    }
}

void Tree::printInOrder(TreeNode* ptr) {
    if (ptr != nullptr) {
        printPreOrder(ptr->getLeft());
        printNode(ptr);
        printPreOrder(ptr->getRight());
    }
}


void Tree::printAll() {
    if (getAnker() != nullptr) {
        string ausgabeFormat;
        cout << "Ausgabereihenfolge ?> ";
        cin >> ausgabeFormat;
        TreeNode* ptr = getAnker();
        cout << endl <<
            "ID | Name       | Alter | Einkommen | PLZ   | OrderID\n"
            "---+------------+-------+-----------+-------+--------\n";
        if (ausgabeFormat == "pre")
            printPreOrder(getAnker());

        else if (ausgabeFormat == "post")
            printPostOrder(getAnker());

        else if (ausgabeFormat == "in")
            printInOrder(getAnker());

        else
            cout << "falsches Formatkürzel";

    }
    else
        cout << "--------------- Kein Eintrag vorhanden --------------\n";
}