Wie templates richtig anwenden?



  • Ich würde gerne mit templates meinen Suchbaum der zurzeit nur int Elemente aufnehmen kann generalisieren, sodass er zb auch char Elemente aufnehmen kann.

    Hier mal ein paar Auszüge aus meinem Code welchen ich via template generalsieren möchte

    class treenode {
    public:
        treenode(int data = 0);
        bool red;
        int item;
        treenode *left;
        treenode *right;
        treenode *parent;
    }; 
    
    class RSTree
    {
    public:
        RSTree();
        void insert(int x);
        void levelorder();
        void inorder();
    private:
        treenode* head;
        void RedBlackInsert(treenode* &node, treenode* &parent, int x, bool sw);
    
    };
    
    void RSTree::insert(int x)
    {
        // Wurzel = head->right
        RedBlackInsert(head->right, head, x, 0);
        head->right->red = 0;
    }
    

    Im Mainprogramm muss ich ja nur bei der Objekterstellung <char> dazu schreiben,
    jedoch wie passe ich Klasse in der Header Datei und die Funktionen in der cpp Datei an?
    Hier mal mein Versuch, welcher jedoch zu viele Fehlermeldungen führt

    template<class type>
    class treenode {
    public:
        treenode;
        bool red;
        type item;
        treenode<type> *left;
        treenode<type> *right;
        treenode<type> *parent;
    };
    
    template<class type>
    class RSTree
    {
    public:
        RSTree();
        void insert(type & x);
        void levelorder();
        void inorder();
    private:
        treenode<type> * head;
        void RedBlackInsert(treenode* &node, treenode* &parent, int x, bool sw);
    
    };
    
    template<class type>
    void RSTree::insert(type * x)
    {
        // Wurzel = head->right
        RedBlackInsert(head->right, head, x, 0);
        head->right->red = 0;
    }
    

    Sprich was muss ich alles anpassen? Geht das alles wie template<class Type>
    oder brauch man für funktionsausformulierungen diese template<typename T> Formulierung?
    lg



  • Na, du musst das Template dann natürlich überall durchziehen. Also auch z.B. in void RedBlackInsert(treenode .

    Wenn du viele Fehler bekommst, schaue dir den ersten an und behebe diesen. Wiederhole, bis fertig.

    Zur Frage:

    Geht das alles wie template<class Type>
    oder brauch man für funktionsausformulierungen diese template<typename T> Formulierung

    Ob class oder typename - das ist hier völlig egal. Entscheide dich für eines und zieh das durch.

    Persönlich bevorzuge ich template<typename T> , aber du kannst auch gerne template<class Type> verwenden - als Typ ist jedoch T üblicher als Type .

    Siehe auch (inkl. Spezialfall, wo es doch nen Unterscheid macht): http://stackoverflow.com/questions/2023977/c-difference-of-keywords-typename-and-class-in-templates



  • Okay, hab es jetzt versucht überall hinzuzufügen, jedoch immer ncoh viele Fehler.
    Am meisten bekomme ich diesen Fehler angezeigt
    Fehler C2244 "RSTree::inorder": Keine Übereinstimmung für Funktionsdefinition mit vorhandener Deklaration gefunden
    Jedoch keine Ahnung was ich falsch mache. Glaub ich vergesse einfach eine grundlegende Sachen bzw. weiss sie einfach nicht wie man es korrekt anwendet.

    template<class Type>
    class treenode {
    public:
    //treenode;
    bool red;
    Type item;
    treenode<Type> *left;
    treenode<Type> *right;
    treenode<Type> *parent;
    };
    
    template<class Type>
    class RSTree
    {
    public:
    
    RSTree();
    void insert(Type & x);
    //void levelorder();
    void inorder();
    private:
    treenode<Type> *head;
    void RedBlackInsert(treenode* &node, treenode* &parent, Type & x, bool sw);
    int red(treenode* &node);
    void leftRotation(treenode * &leftNode);
    void rightRotation(treenode * &leftNode);
    void inorder(treenode* node);
    
    template<class Type>
    treenode::treenode(Type & data)
    {
        this->item = data;
    
        parent = nullptr;
        left = nullptr;
        right = nullptr;
        red = true;
    }
    
    template<class Type>
    RSTree::RSTree()
    {
        head = new treenode();
    }
    
    template<class Type>
    void RSTree::insert(Type * x)
    {
        // Wurzel = head->right
        RedBlackInsert(head->right, head, x, 0);
        head->right->red = 0;
    }
    
    template<class Type>
    int RSTree::red(treenode* &node)
    {
        if (node == nullptr) return 0;
        return node->red;
    }
    
    template<class Type>
    void RSTree::RedBlackInsert(treenode *& node, treenode *&parent, Type & x, bool sw)
    {
        if (node == 0)
        {
            node = new treenode(x);
            node->parent = parent;
            if (node->parent == this->head)
            {
                node->red = 0;
            }
            return;
        }
    
        if (red(node->right) && red(node->left))
        {
    
            if (node != head->right)
            {
                cout << "Knoten: " << node->left->item << ", " << node->item << ", " << node->right->item << " umfarben " << endl;
                node->red = 1;
                node->left->red = 0;
                node->right->red = 0;
            }
            else if (node == head->right)
            {
                cout << "Knoten: " << node->left->item << ", " << node->right->item << " umfarben. " << node->item << " ist die Wurzel!" << endl;
                node->left->red = 0;
                node->right->red = 0;
            }
        }
    
        if (x < node->item)
        {
            RedBlackInsert(node->left, node, x, 0);
    
            if (red(node) && red(node->left) && sw)
            {
                rightRotation(node);
            }
    
            if (red(node->left) && red(node->left->left))
            {
                rightRotation(node);
                node->red = !(node->red);
                if (node->right != 0)
                {
                    node->right->red = !(node->right->red);
                }
            }
    
        }
        else if (x > node->item)
        {
            RedBlackInsert(node->right, node, x, 1);
    
            if (red(node) && red(node->right) && !sw)
            {
                leftRotation(node);
            }
    
            if (red(node->right) && red(node->right->right))
            {
                leftRotation(node);
                node->red = !(node->red);
                if (node->left != 0)
                {
                    node->left->red = !(node->left->red);
                }
            }
        }
        return;
    }
    
    template<class Type>
    void RSTree::leftRotation(treenode* &leftNode)
    {
        treenode * middleNode = leftNode->right;
        treenode *parentNode = leftNode->parent;
    
        cout << "LR ( " << leftNode->item << ", " << middleNode->item << ")" << endl;
    
        leftNode->right = middleNode->left;
    
        if (leftNode->right != nullptr)
        {
            leftNode->right->parent = leftNode;
        }
    
        middleNode->left = leftNode;
        middleNode->parent = leftNode->parent;
        leftNode->parent = middleNode;
    
        if (parentNode->left == leftNode)
        {
            parentNode->left = middleNode;
        }
        else
        {
            parentNode->right = middleNode;
        }
    }
    
    template<class Type>
    void RSTree::rightRotation(treenode* &rightNode)
    {
        treenode *middleNode = rightNode->left;
        treenode *parentNode = rightNode->parent;
    
        cout << "RR ( " << rightNode->item << ", " << middleNode->item << ")" << endl;
    
        rightNode->left = middleNode->right;
        if (rightNode->left != nullptr)
        {
            rightNode->left->parent = rightNode;
        }
    
        middleNode->right = rightNode;
        middleNode->parent = rightNode->parent;
        rightNode->parent = middleNode;
    
        if (parentNode->left == rightNode)
        {
            parentNode->left = middleNode;
        }
        else
        {
            parentNode->right = middleNode;
        }
    }
    


  • treenode ist ein template, daß auch in zB void leftRotation(treenode * &leftNode); seinen Typ wissen muss.

    // (bis auf die Fehler) vollständiger, kompilierbarer Code wär a Hit.



  • Okay, das habe ich wohl immer vergessen.
    Quasi vor dem ::funktionsname immer noch <Type> einfügen.
    template<class Type>
    void RSTree<Type>::rightRotation(treenode* &rightNode)
    Hab jetzt aufjedenfall schon weniger Fehlermeldungen. Aber immer noch ein paar.
    Hier mal der Code.
    Hab paar FUnktionen auskommentiert bzw. weggelassen. Geht ja im Prinzip nur um
    den Templateeinsatz und weniger um das Programm. Aber hoffe es läuft auch so in abgespeckter Form wenn die templates alle richtig eingestellt sind.
    lg

    #include "2-3-4-Baum.h"
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
    
        RSTree<int> tree;
    
        int choice = 0;
    
        while (choice != 4)
        {
            cout << "1: Ausgabe des Baumes in Levelorder" << endl <<
                "2: Element einfuegen" << endl <<
                "3: Ausgabe in Inorder" << endl <<
                "4: Quit" << endl;
            cin >> choice;
            cout << endl;
            switch (choice)
            {
            case 1:
                cout << "Baum in Levelorder:";
            //  tree.levelorder();
                cout << endl;
                break;
            case 2:
            {
                cout << "Knoten einfuegen:" << endl;
                int num = 0;
                cin >> num;
                tree.insert(num);
                cout << "Element " << num << " erfolgreich eingefuegt!" << endl << endl;
                break;
            }
            case 3:
                cout << "Baum in Inorder:" << endl;
                tree.inorder();
                cout << endl;
                break;
            }
        }
    
        return 0;
    }
    
    #pragma once
    #include <vector>
    
    template<class Type>
    class treenode {
    public:
    //treenode;
    bool red;
    Type item;
    treenode *left;
    treenode *right;
    treenode *parent;
    };
    
    template<class Type>
    class RSTree
    {
    public:
    
    RSTree();
    void insert(Type & x);
    //void levelorder();
    void inorder();
    private:
    
    treenode<Type> *head;
    void RedBlackInsert(treenode* &node, treenode* &parent,Type & x, bool sw);
    int red(treenode* &node);
    void leftRotation(treenode * &leftNode);
    void rightRotation(treenode * &leftNode);
    void inorder(treenode* node);
    
    //void levelorder(treenode* node, std::vector<treenode*> &nodeQueue, int niveau, std::vector<int> &niveauQueue);
    //void insertionSort(std::vector<treenode*> &nodeQueue, std::vector<int> &niveauQueue);
    };
    
    #include "2-3-4-Baum.h"
    #include <iostream>
    using namespace std;
    
    template<class Type>
    treenode<Type>::treenode(Type & data)
    {
        this->item = data;
    
        parent = nullptr;
        left = nullptr;
        right = nullptr;
        red = true;
    }
    
    template<class Type>
    RSTree<Type>::RSTree()
    {
        head = new treenode();
    }
    
    template<class Type>
    void RSTree<Type>::insert(Type & x)
    {
        // Wurzel = head->right
        RedBlackInsert(head->right, head,Type & x, 0);
        head->right->red = 0;
    }
    
    template<class Type>
    int RSTree<Type>::red(treenode* &node)
    {
        if (node == nullptr) return 0;
        return node->red;
    }
    
    template<class Type>
    void RSTree<Type>::RedBlackInsert(treenode *& node, treenode *&parent, Type & x, bool sw)
    {
        if (node == 0)
        {
            node = new treenode(x);
            node->parent = parent;
            if (node->parent == this->head)
            {
                node->red = 0;
            }
            return;
        }
    
        if (red(node->right) && red(node->left))
        {
    
            if (node != head->right)
            {
                cout << "Knoten: " << node->left->item << ", " << node->item << ", " << node->right->item << " umfarben " << endl;
                node->red = 1;
                node->left->red = 0;
                node->right->red = 0;
            }
            else if (node == head->right)
            {
                cout << "Knoten: " << node->left->item << ", " << node->right->item << " umfarben. " << node->item << " ist die Wurzel!" << endl;
                node->left->red = 0;
                node->right->red = 0;
            }
        }
    
        if (x < node->item)
        {
            RedBlackInsert(node->left, node, x, 0);
    
            if (red(node) && red(node->left) && sw)
            {
                rightRotation(node);
            }
    
            if (red(node->left) && red(node->left->left))
            {
                rightRotation(node);
                node->red = !(node->red);
                if (node->right != 0)
                {
                    node->right->red = !(node->right->red);
                }
            }
    
        }
        else if (x > node->item)
        {
            RedBlackInsert(node->right, node, x, 1);
    
            if (red(node) && red(node->right) && !sw)
            {
                leftRotation(node);
            }
    
            if (red(node->right) && red(node->right->right))
            {
                leftRotation(node);
                node->red = !(node->red);
                if (node->left != 0)
                {
                    node->left->red = !(node->left->red);
                }
            }
        }
        return;
    }
    
    // Linksrotation
    template<class Type>
    void RSTree<Type>::leftRotation(treenode* &leftNode)
    {
        treenode * middleNode = leftNode->right;
        treenode *parentNode = leftNode->parent;
    
        cout << "LR ( " << leftNode->item << ", " << middleNode->item << ")" << endl;
    
        leftNode->right = middleNode->left;
    
        if (leftNode->right != nullptr)
        {
            leftNode->right->parent = leftNode;
        }
    
        middleNode->left = leftNode;
        middleNode->parent = leftNode->parent;
        leftNode->parent = middleNode;
    
        if (parentNode->left == leftNode)
        {
            parentNode->left = middleNode;
        }
        else
        {
            parentNode->right = middleNode;
        }
    }
    
    // Rechtsrotation
    
    template<class Type>
    void RSTree<Type>::rightRotation(treenode* &rightNode)
    {
        treenode *middleNode = rightNode->left;
        treenode *parentNode = rightNode->parent;
    
        cout << "RR ( " << rightNode->item << ", " << middleNode->item << ")" << endl;
    
        rightNode->left = middleNode->right;
        if (rightNode->left != nullptr)
        {
            rightNode->left->parent = rightNode;
        }
    
        middleNode->right = rightNode;
        middleNode->parent = rightNode->parent;
        rightNode->parent = middleNode;
    
        if (parentNode->left == rightNode)
        {
            parentNode->left = middleNode;
        }
        else
        {
            parentNode->right = middleNode;
        }
    }
    
    template<class Type>
    void RSTree<Type>::inorder()
    {
        inorder(head->right);
        cout << endl;
    }
    
    template<class Type>
    void RSTree<Type>::inorder(treenode* node)
    {
        if (node != nullptr)
        {
            inorder(node->left);
            cout << node->item << " ";
            inorder(node->right);
        }
    }
    


  • as1as schrieb:

    Hab jetzt aufjedenfall schon weniger Fehlermeldungen. Aber immer noch ein paar.

    Und welche Frage hast Du? Nachdem du jetzt ja weißt, worum es geht ...

    treenode *middleNode = rightNode->left;
    	treenode *parentNode = rightNode->parent;
    

    -->

    treenode<Type> *middleNode = rightNode->left;
    	treenode<Type> *parentNode = rightNode->parent;
    

    Was anderes:
    void RSTree<Type>::rightRotation( treenode<Type>* &rightNode )
    Referenzen auf Pointer? Echt jetz?



  • Swordfish schrieb:

    as1as schrieb:

    Hab jetzt aufjedenfall schon weniger Fehlermeldungen. Aber immer noch ein paar.

    Und welche Frage hast Du? Nachdem du jetzt ja weißt, worum es geht ...

    treenode *middleNode = rightNode->left;
    	treenode *parentNode = rightNode->parent;
    

    -->

    treenode<Type> *middleNode = rightNode->left;
    	treenode<Type> *parentNode = rightNode->parent;
    

    Ah okay. Also man muss auch in den FUnktionen wenn man temoräre Objekte erstellt ect. <Type> benutzen. Mal schauen ob ich danach alle Meldungen weghabe


  • Mod

    Swordfish schrieb:

    Referenzen auf Pointer? Echt jetz?

    Find ich genau richtig an dieser Stelle. Spart eine Menge Syntaxlärm vom ständigen dereferenzieren (wie der aussieht, wissen wir aus C - lesbarer wird es damit nicht).



  • Uuuups. Bin da ohne wirklich zu lesen von *& statt * anstatt *& statt ** ausgegangen. 😮



  • Ich habe nochmal ein kürzer und leichteres Programm rausgesucht mit dem ich mehr Erfahrung habe und versucht dies
    mittels Templates zu generalisieren. Jedoch ohne Erfolg.
    Hier das funktionnierende Ausgangsprogramm.
    Nicht verunsichern lassen von 2-3-4.h ect. ist nur ein Binärbaum.
    Welchen ich jedoch später in 2-3-4 überführe.

    class Baumknoten {
    public:
        int zahl; // Datenelement vom Typ int
        Baumknoten *links; // Zeiger auf linken Nachfolger
        Baumknoten *rechts; // Zeiger auf rechten Nachfolger
    
        Baumknoten() : zahl(), links(0), rechts(0) {} // Konstruktor
    
    };
    
    class Binaerbaum {
    private:
        Baumknoten *kopfzeiger; // Kopfzeiger: rechter Nachfolger zeigt auf die Wurzel
        Baumknoten *nullknoten; // Pseudoknoten als Nullzeiger für die Nachfolger eines Blattes
    public:
    
        // Konstruktor
        Binaerbaum()
        {
            kopfzeiger = new Baumknoten;
            nullknoten = new Baumknoten;
        }
    
        void neues_element_einfuegen(int zahl); // neues Element einfügen
    
        Baumknoten* liefer_wurzel(Binaerbaum a);//liefert wurzel ins mainprogramm
    
        void Inorder(Baumknoten *n);
    
        void Levelorder(Baumknoten *n);
    
    };
    
    #include "2-3-4-tree.h"
    #include <iostream>
    #include <queue>
    using namespace std;
    
    // neues Element einfügen
    
    void Binaerbaum::neues_element_einfuegen(int zahl) {
    
        // erstelle neue Knoteninstanz
        Baumknoten *neues_element = new Baumknoten;
        neues_element->zahl = zahl;
        neues_element->links = nullknoten;
        neues_element->rechts = nullknoten;
    
        // wenn Baum leer so wird die erste Eingabe zur "Wurzel"
        if (kopfzeiger->rechts == nullptr)
        {
            kopfzeiger->rechts = neues_element;
    
        }
        // Baum besitzt schon eine "Wurzel"
        else
        {
            // temporäre Datei sodass die Baumstruktur beim traversieren nicht verändert wird
            Baumknoten *tmp_wurzelknoten = kopfzeiger->rechts;
    
            while (true)
            {
                // fängt doppelte Eingaben ab
                if (neues_element->zahl == tmp_wurzelknoten->zahl)
                {
                    cout << "Element schon vorhanden. Bitte geben Sie eine andere Zahl ein. " << endl;
                    break;
                }
    
                // für jeweils die rechts Baumhälfte, bzw. für den ist größer Fall
                if (neues_element->zahl > tmp_wurzelknoten->zahl)
                {
                    if (tmp_wurzelknoten->rechts == nullknoten)
                    {
    
                        tmp_wurzelknoten->rechts = neues_element;
                        break;
    
                    }
                    else
                    {
                        tmp_wurzelknoten = tmp_wurzelknoten->rechts;
                    }
    
                }
    
                // für jeweils die linke Baumhälfte, bzw. für den ist kleiner Fall
                if (neues_element->zahl < tmp_wurzelknoten->zahl)
                {
                    if (tmp_wurzelknoten->links == nullknoten)
                    {
                        tmp_wurzelknoten->links = neues_element;
                        break;
                    }
                    else
                    {
                        tmp_wurzelknoten = tmp_wurzelknoten->links;
                    }
                }
    
            }
    
        }
    
    }
    
    Baumknoten*  Binaerbaum::liefer_wurzel(Binaerbaum a) {
    
        Baumknoten * tmp = kopfzeiger->rechts;
    
        return tmp;
    
    }
    
    //traversiert zuerst rekursiv den linken Teilbaum, dann den Knoten selbst und anschließend den rechten Teilbaum
    void Binaerbaum::Inorder(Baumknoten *n) {
    
        if (n->zahl != 0) {
            Inorder(n->links);
            cout << n->zahl << " ";
            Inorder(n->rechts);
        }
    }
    
    // traversiert niveau- bzw. levelweise die Knoten
    void Binaerbaum::Levelorder(Baumknoten *n)
    {
        // wenn Baum leer ist
        if (n == NULL)  return;
    
        // Erstelle leere Warteschlange
        queue<Baumknoten *> q;
    
        // Wurzel in warteschlange einfügen
        q.push(n);
    
        //solange warteschlange niht leer ist
        while (q.empty() == false)
        {
            // erstelle mir referenz auf nächstes element und gebe element aus , dann entfernen
            Baumknoten *node = q.front();
    
            cout << node->zahl << " ";
    
            q.pop();
    
            //  linker knoten in warteschlange einreihen
            if (node->links != nullknoten)
                q.push(node->links);
    
            //  rechter knoten in warteschlange einreihen
            if (node->rechts != nullknoten)
                q.push(node->rechts);
        }
    }
    
    #include "2-3-4-tree.h"
    #include <iostream>
    using namespace std;
    
    int main()
    {
        // erstelle Instanz der Binärbaumklasse um später Funktionen/Methoden auf sie anwenden zu können
        Binaerbaum a;
    
        // Baum wird aufgebaut
        // Ende mit Eingabe der Null
        int eingabe = 0;
        do
        {
            cout << "Bitte geben Sie Zahlen ein (Ende durch Eingabe der Null) " << endl;
            cin >> eingabe;
            if (eingabe == 0)
            {
                break;
            }
    
            a.neues_element_einfuegen(eingabe);
    
        } while (true);
        cout << endl;
    
        // liefert mir die wurzel von a, sodass ich sie im hauptprogramm zur verfügung habe
        Baumknoten *wurzel = a.liefer_wurzel(a);
    
        do
        {
            cout << endl;
            cout << "1  : Ausgabe des Baumes in Levelorder" << endl;
    
            cout << "2  : Ausgabe des Baumes in Inorder" << endl;
    
            cout << "3  : Element einfuegen" << endl;
    
            cout << "4 : Quit" << endl;
    
            int menueeingabe = 0;
            cin >> menueeingabe;
            cout << endl;
    
            if (menueeingabe == 2)
            {
                // Ausgabe Inorder
                cout << "Baum in Inorder: " << endl;
                a.Inorder(wurzel);
                cout << endl;
            }
    
            if (menueeingabe == 1)
            {
                //Ausgabe Levelorder
                cout << "Baum in Levelorder: " << endl;
                a.Levelorder(wurzel);
                cout << endl;
            }
    
            if (menueeingabe == 3)
            {
                int zahl;
                cout << "Geben Sie Ihre gewuenschte Zahl ein: ";
                cin >> zahl;
                a.neues_element_einfuegen(zahl);
            }
    
            if (menueeingabe == 4)
            {
                break;
            }
    
        } while (true);
    
        system("PAUSE");
        return 0;
    }
    

    Hier mein template Versuch.
    Ich habe die Stellen wo vermutlich ein Fehler ist, jedoch ich nicht weiterweiß mit !!! kommentiert ( bzw. Zeile 20)

    template <class Type>
    class Baumknoten {
    public:
        Type zahl; // Datenelement vom Typ int
        Baumknoten *links; // Zeiger auf linken Nachfolger
        Baumknoten *rechts; // Zeiger auf rechten Nachfolger
    
        Baumknoten() : zahl(), links(0), rechts(0) {} // Konstruktor
    
    };
    
    template <class Type>
    class Binaerbaum {
    private:
        Baumknoten<Type> *kopfzeiger; // Kopfzeiger: rechter Nachfolger zeigt auf die Wurzel
        Baumknoten<Type> *nullknoten; // Pseudoknoten als Nullzeiger für die Nachfolger eines Blattes
    public:
    
    //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        // Konstruktor
        Binaerbaum()
        {
            kopfzeiger = new Baumknoten<Type>;
            nullknoten = new Baumknoten<Type>;
        }
    //ich hatte erst das <Type> hinter den new baumknoten nicht, 
    // nun wo ich es habe bekomme ich einne fehler in main.obj bzw. in der exe
    //4 nicht aufgelöste elemente
     //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        void neues_element_einfuegen( :confused: Type zahl); // neues Element einfügen
    
        Baumknoten<Type>* liefer_wurzel(Binaerbaum<Type> a);//liefert wurzel ins mainprogramm
    
        void Inorder(Baumknoten<Type> *n);
    
        void Levelorder(Baumknoten<Type> *n);
    
    };
    
    #include "2-3-4-tree.h"
    #include <iostream>
    #include <queue>
    using namespace std;
    
    // neues Element einfügen
    template <class Type>
    void Binaerbaum<Type>::neues_element_einfuegen(Type zahl) {
    
        // erstelle neue Knoteninstanz
        Baumknoten *neues_element = new Baumknoten;
        neues_element->zahl = zahl;
        neues_element->links = nullknoten;
        neues_element->rechts = nullknoten;
    
        // wenn Baum leer so wird die erste Eingabe zur "Wurzel"
        if (kopfzeiger->rechts == nullptr)
        {
            kopfzeiger->rechts = neues_element;
    
        }
        // Baum besitzt schon eine "Wurzel"
        else
        {
            // temporäre Datei sodass die Baumstruktur beim traversieren nicht verändert wird
            Baumknoten *tmp_wurzelknoten = kopfzeiger->rechts;
    
            while (true)
            {
                // fängt doppelte Eingaben ab
                if (neues_element->zahl == tmp_wurzelknoten->zahl)
                {
                    cout << "Element schon vorhanden. Bitte geben Sie eine andere Zahl ein. " << endl;
                    break;
                }
    
                // für jeweils die rechts Baumhälfte, bzw. für den ist größer Fall
                if (neues_element->zahl > tmp_wurzelknoten->zahl)
                {
                    if (tmp_wurzelknoten->rechts == nullknoten)
                    {
    
                        tmp_wurzelknoten->rechts = neues_element;
                        break;
    
                    }
                    else
                    {
                        tmp_wurzelknoten = tmp_wurzelknoten->rechts;
                    }
    
                }
    
                // für jeweils die linke Baumhälfte, bzw. für den ist kleiner Fall
                if (neues_element->zahl < tmp_wurzelknoten->zahl)
                {
                    if (tmp_wurzelknoten->links == nullknoten)
                    {
                        tmp_wurzelknoten->links = neues_element;
                        break;
                    }
                    else
                    {
                        tmp_wurzelknoten = tmp_wurzelknoten->links;
                    }
                }
    
            }
    
        }
    
    }
    
    template <class Type>
    Baumknoten<Type>*  Binaerbaum<Type>::liefer_wurzel(Binaerbaum<Type> a) {
    
        Baumknoten * tmp = kopfzeiger->rechts;
    
        return tmp;
    
    }
    
    //traversiert zuerst rekursiv den linken Teilbaum, dann den Knoten selbst und anschließend den rechten Teilbaum
    template <class Type>
    void Binaerbaum<Type>::Inorder(Baumknoten<Type> *n) {
    
        if (n->zahl != 0) {
            Inorder(n->links);
            cout << n->zahl << " ";
            Inorder(n->rechts);
        }
    }
    
    // traversiert niveau- bzw. levelweise die Knoten
    template <class Type>
    void Binaerbaum<Type>::Levelorder(Baumknoten<Type> *n)
    {
        // wenn Baum leer ist
        if (n == NULL)  return;
    
        // Erstelle leere Warteschlange
        queue<Baumknoten<Type> * q;
    
        // Wurzel in warteschlange einfügen
        q.push(n);
    
        //solange warteschlange niht leer ist
        while (q.empty() == false)
        {
            // erstelle mir referenz auf nächstes element und gebe element aus , dann entfernen
            Baumknoten<Type> *node = q.front();
    
            cout << node->zahl << " ";
    
            q.pop();
    
            //  linker knoten in warteschlange einreihen
            if (node->links != nullknoten)
                q.push(node->links);
    
            //  rechter knoten in warteschlange einreihen
            if (node->rechts != nullknoten)
                q.push(node->rechts);
        }
    }
    
    #include "2-3-4-tree.h"
    #include <iostream>
    using namespace std;
    
    int main()
    {
        // erstelle Instanz der Binärbaumklasse um später Funktionen/Methoden auf sie anwenden zu können
        Binaerbaum<int> a;
    
        // Baum wird aufgebaut
        // Ende mit Eingabe der Null
        int eingabe = 0;
        do
        {
            cout << "Bitte geben Sie Zahlen ein (Ende durch Eingabe der Null) " << endl;
            cin >> eingabe;
            if (eingabe == 0)
            {
                break;
            }
    
            a.neues_element_einfuegen(eingabe);
    
        } while (true);
        cout << endl;
    
        // liefert mir die wurzel von a, sodass ich sie im hauptprogramm zur verfügung habe
        Baumknoten<int> *wurzel = a.liefer_wurzel(a);
    
        do
        {
            cout << endl;
            cout << "1  : Ausgabe des Baumes in Levelorder" << endl;
    
            cout << "2  : Ausgabe des Baumes in Inorder" << endl;
    
            cout << "3  : Element einfuegen" << endl;
    
            cout << "4 : Quit" << endl;
    
            int menueeingabe = 0;
            cin >> menueeingabe;
            cout << endl;
    
            if (menueeingabe == 2)
            {
                // Ausgabe Inorder
                cout << "Baum in Inorder: " << endl;
                a.Inorder(wurzel);
                cout << endl;
            }
    
            if (menueeingabe == 1)
            {
                //Ausgabe Levelorder
                cout << "Baum in Levelorder: " << endl;
                a.Levelorder(wurzel);
                cout << endl;
            }
    
            if (menueeingabe == 3)
            {
                int zahl;
                cout << "Geben Sie Ihre gewuenschte Zahl ein: ";
                cin >> zahl;
                a.neues_element_einfuegen(zahl);
            }
    
            if (menueeingabe == 4)
            {
                break;
            }
    
        } while (true);
    
        system("PAUSE");
        return 0;
    }
    


  • #include <iostream>
    #include <queue>
    
    using namespace std;
    
    template <class Type>
    class Baumknoten {
    public:
    	Type zahl;
    	Baumknoten<Type> *links;
    	Baumknoten<Type> *rechts;
    
    	Baumknoten() : zahl(), links( 0 ), rechts( 0 ) {}
    
    };
    
    template <class Type>
    class Binaerbaum {
    private:
    	Baumknoten<Type> *kopfzeiger; // Kopfzeiger: rechter Nachfolger zeigt auf die Wurzel
    	Baumknoten<Type> *nullknoten; // Pseudoknoten als Nullzeiger für die Nachfolger eines Blattes  // <<== was jetzt? nullptr oder doch was? new im c-tor??
    public:
    
    	Binaerbaum()
    	{
    		kopfzeiger = new Baumknoten<Type>;
    		nullknoten = new Baumknoten<Type>;
    	}
    
    	void neues_element_einfuegen( Type zahl );
    	Baumknoten<Type>* liefer_wurzel( Binaerbaum<Type> a );
    	void Inorder( Baumknoten<Type> *n );
    	void Levelorder( Baumknoten<Type> *n );
    
    };
    
    template <class Type>
    void Binaerbaum<Type>::neues_element_einfuegen( Type zahl ) {
    
    	// erstelle neue Knoteninstanz
    	Baumknoten<Type> *neues_element = new Baumknoten<Type>;
    	neues_element->zahl = zahl;
    	neues_element->links = nullknoten;
    	neues_element->rechts = nullknoten;
    
    	// wenn Baum leer so wird die erste Eingabe zur "Wurzel"
    	if( kopfzeiger->rechts == nullptr )
    	{
    		kopfzeiger->rechts = neues_element;
    	}
    	// Baum besitzt schon eine "Wurzel"
    	else
    	{
    		// temporäre Datei sodass die Baumstruktur beim traversieren nicht verändert wird
    		Baumknoten<Type> *tmp_wurzelknoten = kopfzeiger->rechts;
    
    		while( true )
    		{
    			// fängt doppelte Eingaben ab
    			if( neues_element->zahl == tmp_wurzelknoten->zahl )
    			{
    				cout << "Element schon vorhanden. Bitte geben Sie eine andere Zahl ein.\n";
    				break;
    			}
    
    			// für jeweils die rechts Baumhälfte, bzw. für den ist größer Fall
    			if( neues_element->zahl > tmp_wurzelknoten->zahl )
    			{
    				if( tmp_wurzelknoten->rechts == nullknoten )
    				{
    					tmp_wurzelknoten->rechts = neues_element;
    					break;
    				}
    				else
    				{
    					tmp_wurzelknoten = tmp_wurzelknoten->rechts;
    				}
    			}
    
    			// für jeweils die linke Baumhälfte, bzw. für den ist kleiner Fall
    			if( neues_element->zahl < tmp_wurzelknoten->zahl )
    			{
    				if( tmp_wurzelknoten->links == nullknoten )
    				{
    					tmp_wurzelknoten->links = neues_element;
    					break;
    				}
    				else
    				{
    					tmp_wurzelknoten = tmp_wurzelknoten->links;
    				}
    			}
    		}
    	}
    }
    
    template <class Type>
    Baumknoten<Type>*  Binaerbaum<Type>::liefer_wurzel( Binaerbaum<Type> a ) {
    
    	Baumknoten<Type> * tmp = kopfzeiger->rechts;
    	return tmp;
    }
    
    //traversiert zuerst rekursiv den linken Teilbaum, dann den Knoten selbst und anschließend den rechten Teilbaum
    template <class Type>
    void Binaerbaum<Type>::Inorder( Baumknoten<Type> *n ) {
    
    	if( n->zahl != 0 ) {
    		Inorder( n->links );
    		cout << n->zahl << " ";
    		Inorder( n->rechts );
    	}
    }
    
    // traversiert niveau- bzw. levelweise die Knoten
    template <class Type>
    void Binaerbaum<Type>::Levelorder( Baumknoten<Type> *n )
    {
    	// wenn Baum leer ist
    	if( n == NULL )  return;
    
    	// Erstelle leere Warteschlange
    	queue<Baumknoten<Type>*> q;
    
    	// Wurzel in warteschlange einfügen
    	q.push( n );
    
    	//solange warteschlange niht leer ist
    	while( q.empty() == false )
    	{
    		// erstelle mir referenz auf nächstes element und gebe element aus , dann entfernen
    		Baumknoten<Type> *node = q.front();
    
    		cout << node->zahl << " ";
    
    		q.pop();
    
    		//  linker knoten in warteschlange einreihen
    		if( node->links != nullknoten )
    			q.push( node->links );
    
    		//  rechter knoten in warteschlange einreihen
    		if( node->rechts != nullknoten )
    			q.push( node->rechts );
    	}
    }
    
    int main()
    {
    	// erstelle Instanz der Binärbaumklasse um später Funktionen/Methoden auf sie anwenden zu können
    	Binaerbaum<int> a;
    
    	// Baum wird aufgebaut
    	// Ende mit Eingabe der Null
    	int eingabe = 0;
    	do
    	{
    		cout << "Bitte geben Sie Zahlen ein (Ende durch Eingabe der Null)\n";
    		cin >> eingabe;
    		if( eingabe == 0 )
    			break;
    
    		a.neues_element_einfuegen( eingabe );
    
    	} while( true );
    	cout.put('\n');
    
    	// liefert mir die wurzel von a, sodass ich sie im hauptprogramm zur verfügung habe
    	Baumknoten<int> *wurzel = a.liefer_wurzel( a );
    
    	do
    	{
    		cout << "\n1: Ausgabe des Baumes in Levelorder\n";
    		cout << "2: Ausgabe des Baumes in Inorder\n";
    		cout << "3: Element einfuegen\n";
    		cout << "4: Quit\n";
    
    		int menueeingabe = 0;
    		cin >> menueeingabe;
    		cout.put('\n');
    
    		if( menueeingabe == 2 )
    		{
    			// Ausgabe Inorder
    			cout << "Baum in Inorder:\n";
    			a.Inorder( wurzel );
    			cout.put('\n');
    		}
    
    		if( menueeingabe == 1 )
    		{
    			//Ausgabe Levelorder
    			cout << "Baum in Levelorder:\n";
    			a.Levelorder( wurzel );
    			cout.put('\n');
    		}
    
    		if( menueeingabe == 3 )
    		{
    			int zahl;
    			cout << "Geben Sie Ihre gewuenschte Zahl ein: ";
    			cin >> zahl;
    			a.neues_element_einfuegen( zahl );
    		}
    
    		if( menueeingabe == 4 )
    		{
    			break;
    		}
    
    	} while( true );
    }
    


  • Habe meine Fehler korrigiert aber bekomme immer noch die Fehlermeldung mit den 4 nicht aufgelößten Externen. Hab auch den Code mal kopiert, das ich vllt etwas übersehen habe, aber gleiche Meldung.



  • Templates müssen in der Übersetzungseinheit, in der sie instanziiert werden, komplett bekannt sein. ➡ Pack die Definitionen in die Headerdatei und wirf die .cpp weg.



  • Auch smarte pointer sind hier nicht fehl am Platz.



  • Swordfish schrieb:

    Templates müssen in der Übersetzungseinheit, in der sie instanziiert werden, komplett bekannt sein. ➡ Pack die Definitionen in die Headerdatei und wirf die .cpp weg.

    Super danke jetzt funktioniert es:)
    Hast du oder jemand anderes vllt eine gute Seite oder ein Buch zu empfehlen wo
    so grundlegende Sachen Schritt für Schritt erklärt werden?
    Weil ich zb. wäre jetzt anhand des Fehlercodes "4 nicht aufgelößten Externen"
    nie darauf gekommen das es dadran liegt das man die Funktionsrümpfe nicht in der
    cpp.Datei ausprogrammieren darf bei templates.bzw sie inder headerdatei bekannt sein müssen.
    lg




Log in to reply