C++ BinärBaum<Template> Einfügen Probleme

O

ocsme

Top Contributor
Hallo zusammen,

leider bekomme ich mein Problem eigenständig nicht gelöst =(
Was ich versuche ist einen BinärBaum in C++ als Template Klasse zu schreiben.

Nun habe ich wie folgt begonnen:
C++: 
#include <memory>
#include <iostream>

using namespace std;

template<class T>
class BinTree {
private:
    class Node {
        T value;
        shared_ptr<Node> left;
        shared_ptr<Node> right;
    public:
        Node(T value, shared_ptr<Node> left = nullptr, shared_ptr<Node> right =
                nullptr) :
                value(value), left(left), right(right) {}
        shared_ptr<Node>& getLeft() {return left;}
        shared_ptr<Node>& getRight() {return right;}
        T getValue() const {return value;}
        void setLeft(shared_ptr<Node> &left) {this->left = left;}
        void setRight(shared_ptr<Node> &right) {this->right = right;}
        void setValue(T value) {this->value = value;}
    };
    shared_ptr<Node> root;
    void copy(shared_ptr<Node> &other);
    void recCopy(shared_ptr<Node> &other);
    shared_ptr<Node>& recEinfuegen(shared_ptr<Node> &other, T value);
    void recPrint(shared_ptr<Node> other);
public:
    BinTree();
    virtual ~BinTree() = default;
    BinTree(const BinTree &other);
    BinTree(BinTree &&other);
    BinTree& operator=(const BinTree &other);
    BinTree& operator=(BinTree &&other);
    void einfuegen(T value);
    void ausgabe();
};

template<class T>
void BinTree<T>::einfuegen(T value) {
    if (root == nullptr)
        root = shared_ptr<Node> { new Node { value } };
    else
        recEinfuegen(root, value);
}

template<class T>
shared_ptr<BinTree::Node>& BinTree<T>::recEinfuegen(shared_ptr<Node> &other,
        T value) {
    if (other == nullptr)
        other = shared_ptr<Node> { new Node { value } };
    else if (other->getValue() >= value)
        other->setLeft(recEinfuegen(other->getLeft, value));
    else
        other->setRight(recEinfuegen(other->getRight, value));
    return other;
}

template<class T>
void BinTree<T>::copy(shared_ptr<Node> &other) {...}

template<class T>
void BinTree<T>::recCopy(shared_ptr<Node> &other) {...}

template<class T>
BinTree<T>::BinTree() :    root(nullptr) { }

template<class T>
BinTree<T>::BinTree(const BinTree &other):root(nullptr) {...}

template<class T>
BinTree<T>::BinTree(BinTree &&other):root(other->root) {}

template<class T>
BinTree<T>& BinTree<T>::operator =(const BinTree &other) {...}

template<class T>
BinTree<T>& BinTree<T>::operator =(BinTree &&other) {...}

template<class T>
void BinTree<T>::ausgabe() { ... }

template<class T>
void BinTree<T>::recPrint(shared_ptr<Node> other) {...}

Das Problem ist bei recEinfuegen und er zeigt mir folgendes:
Code: 
../BinTreeNode.h:133:25: error: template argument 1 is invalid
 shared_ptr<BinTree::Node>& BinTree<T>::recEinfuegen(shared_ptr<Node> &other,
                         ^
../BinTreeNode.h:133:28: error: prototype for ‘int& BinTree<T>::recEinfuegen(std::shared_ptr<BinTree<T>::Node>&, T)’ does not match any in class ‘BinTree<T>’
 shared_ptr<BinTree::Node>& BinTree<T>::recEinfuegen(shared_ptr<Node> &other,
                            ^~~~~~~~~~
../BinTreeNode.h:50:20: error: candidate is: std::shared_ptr<BinTree<T>::Node>& BinTree<T>::recEinfuegen(std::shared_ptr<BinTree<T>::Node>&, T)
  shared_ptr<Node>& recEinfuegen(shared_ptr<Node> &other, T value);
                    ^~~~~~~~~~~~

Hat er ein Problem Node in der Klasse BinTree aufzulösen? BinTree<T>::Node funktioniert auch nicht =(
Weiß vielleicht jemand weiter?
 
K

kneitzel

Gast
Was mir auffällt: Du versuchst recEinfuegen der Klasse BinTree zu implementieren. Aber recEinfuegen ist doch in der SubKlasse Node.

Also BinTree<T>::Node::recEinfuegen wäre der anzugebene "Name" der Funktion im Source File....
Ebenso recAusgeben wenn ich es richtig gesehen habe ...

Aber ich habe das jetzt nur kurz überflogen, also evtl. habe ich ja auch etwas übersehen ...
 
O

ocsme

Top Contributor
Super das hat mein erstes Problem gelöst =)
Nun meckert er an den Methoden getLeft() & getRight() in Node rum.
invalid use of non-static member function ‘std::shared_ptr<BinTree<T>::Node>& BinTree<T>::Node::getRight() [with T = int]’

Was ich nicht verstehe ist, ich hab vorher eine Queue mit shared_ptr und als Template Programmiert. Das ging ohne Probleme. Wieso klappt das nun bei dem Bäumchen nicht :-(
 
K

kneitzel

Gast
An welcher Stelle kommt das jetzt genau und wie sieht die Header Datei komplett aus? Ist immer einfacher, wenn man das selbst in einer IDE öffnet als hier im Forum zu schauen.
 
O

ocsme

Top Contributor
Ich stell die ganze Header Datei mal rein =)
C++: 
#include <memory>
#include <iostream>

using namespace std;

template<class T>
class BinTree {
private:
    class Node {
        T value;
        shared_ptr<Node> left; //Node *left;
        shared_ptr<Node> right;
    public:
        Node(T value, shared_ptr<Node> left = nullptr, shared_ptr<Node> right =
                nullptr) :
                value(value), left(left), right(right) {

        }

        shared_ptr<Node>& getLeft() {
            return left;
        }

        shared_ptr<Node>& getRight() {
            return right;
        }

        T getValue() const {
            return value;
        }

        void setLeft(shared_ptr<Node> &left) {
            this->left = left;
        }

        void setRight(shared_ptr<Node> &right) {
            this->right = right;
        }

        void setValue(T value) {
            this->value = value;
        }
    };
    shared_ptr<Node> root;
    void copy(shared_ptr<Node> &other);
    void recCopy(shared_ptr<Node> &other);
    shared_ptr<Node>& recEinfuegen(shared_ptr<Node> &other, T value);
    void recPrint(shared_ptr<Node> other);
public:
    BinTree();
    virtual ~BinTree() = default;
    BinTree(const BinTree &other);
    BinTree(BinTree &&other);
    BinTree& operator=(const BinTree &other);
    BinTree& operator=(BinTree &&other);
    void einfuegen(T value);
    void ausgabe();
};

template<class T>
void BinTree<T>::copy(shared_ptr<Node> &other) {
    root = nullptr;
    if (other != nullptr) {
        root = shared_ptr<Node>(new Node { other->getValue() });
        recCopy(other->getLeft());
        recCopy(other->getRight());
    }
}

template<class T>
void BinTree<T>::recCopy(shared_ptr<Node> &other) {
    if (other != nullptr) {
        einfuegen(other->getValue());
        recCopy(other->getLeft());
        recCopy(other->getRight());
    }
}

template<class T>
BinTree<T>::BinTree() :
        root(nullptr) {

}

template<class T>
BinTree<T>::BinTree(const BinTree &other) :
        root(nullptr) {
    copy(other->root);
}

template<class T>
BinTree<T>::BinTree(BinTree &&other) :
        root(other->root) {
}

template<class T>
BinTree<T>& BinTree<T>::operator =(const BinTree &other) {
    if (this != other) {
        root = nullptr;
        copy(other->root);
    }
    return *this;
}

template<class T>
BinTree<T>& BinTree<T>::operator =(BinTree &&other) {
    root = other.root;
    return *this;
}

template<class T>
void BinTree<T>::einfuegen(T value) {
    if (root == nullptr)
        root = shared_ptr<Node> { new Node { value } };
    else
        recEinfuegen(root, value);
}

template<class T>
void BinTree<T>::recPrint(shared_ptr<Node> other) {
    if (other != nullptr) {
        recPrint(other->getLeft());
        cout << other->getValue() << " ";
        recPrint(other->getRight());
    } else
        cout << "Baum ist leer!" << endl;
}

template<class T>
shared_ptr<typename BinTree<T>::Node>& BinTree<T>::recEinfuegen(shared_ptr<Node> &other,
        T value) {
    if (other == nullptr)
        other = shared_ptr<Node> { new Node { value } };
    else if (other->getValue() >= value)
        other->setLeft(recEinfuegen(other->getLeft, value));
    else
        other->setRight(recEinfuegen(other->getRight, value));
    return other;
}

template<class T>
void BinTree<T>::ausgabe() {
    recPrint(root);
}
 
K

kneitzel

Gast
getLeft / getRight sind Funktionen, daher möchtest Du diese doch bestimmt aufrufen:
C++: 
template<class T>
shared_ptr<typename BinTree<T>::Node>& BinTree<T>::recEinfuegen(shared_ptr<Node> &other,
                                                                T value) {
    if (other == nullptr)
        other = shared_ptr<Node> { new Node { value } };
    else if (other->getValue() >= value)
        other->setLeft(recEinfuegen(other->getLeft(), value));
    else
        other->setRight(recEinfuegen(other->getRight(), value));
    return other;
}

Es fehlten bei Dir die ()!
 
O

ocsme

Top Contributor
Oh ja ich bin heute irgendwie total verstrahlt =(

Jetzt kommt kein Fehler mehr und es geht.

Vielen Lieben Dank für die Hilfe.
Jetzt kommen noch ein paar Fragen. Mir ist gestern bei der Queue Aufgefallen das man diese nicht mit unique_ptr schreiben kann. Wieso, ganz einfach ich habe ja ein Start und Ende Zeiger in meiner Queue und Anfangs zeigen beide dieser Zeiger auf das selbe Objekt. Das sollte ja nur mit shared_ptr funktionieren. Deswegen hatte ich diese benutzt.

Des weiteren verstehe ich gerade nicht mehr wieso ich bei getLeft() und getRight() in der Node Klasse eine Referenz zurück gebe =(
Man könnte den shared_ptr<Node> left; ja so umschreiben Node *left; (klar dann hätte ich kein Shared_ptr mehr und müsste meine Daten selbst löschen etc!). Wieso schreibe ich bei getLeft() nun aber & getLeft().


____

Beim Kopieren habe ich noch ein Problem :-D
Da das Objekt const ist, kann ich die Methode copy nicht aufrufen.
Hab nun einen 2ten Pointer erstellt und schon gehts =D
C++: 
template<class T>
BinTree<T>::BinTree(const BinTree &other) :
        root(nullptr) {
    shared_ptr<Node> tmp = other.root;
    if (other.root != nullptr)
        copy(tmp);
}
 
Zuletzt bearbeitet:
K

kneitzel

Gast
Dazu stecke in nicht mehr tief genug in C++ drin muss ich ehrlich sagen.

Aber paar Punkte sind wichtig:
a) Wenn Du keine Referenz zurück gibst, dann bedeutet das, dass eine Kopie erstellt würde. (Was dann teilweise optimiert wird und so ... Also wenn Du eine Funktion hast, die eine Instanz erzeugt und diese dann zurück gibt. Streng genommen bedeutet dies dann, dass Du den Copy Konstruktor anwirfst. Compiler, die ich aktuell so kenne, optimieren hier aber, so dass dies nicht der Fall ist. ==> Du könntest auf die Referenz verzichten und es würde auch funktionieren (So Du nichts unsinniges machst mit der Referenz. :) )

b) Zeiger - Ja, den guten alten Zeiger-Wahnsinn. Das war damals mal der Weg überhaupt. Du hast dann einen Zeiger zurück gegeben. Und halt neue Instanzen mit new erzeugt. Und musstest dann aufpassen, wann und wo du diese Instanz löschen musstest aus dem Speicher. Dieses manuelle Speicher-Management will man aber nicht mehr nutzen. (Wie Du ja auch schon erkannt hast. Daher nutze keine Zeiger sondern Referenzen und die shared_ptr und so ...

Das sind so die Punkte, die mir diesbezüglich dazu einfallen. Aber da müsste ich im Detail halt selbst wieder tiefer einsteigen. C++ habe ich zuletzt um 2002/2003 zuletzt aktiv genutzt (Aber da dann mit > 10 Jahre Erfahrung. Borlands Wechsel zu C++ mit Turbo C++ 1.0 habe ich aktiv mit gemacht ... :) ). Dann bin ich auf .Net 1.0 und C# gewechselt. Mein aktuelles Projekt hat zwar auch eine riesige C++ Basis, aber die ist vor ca 10-15 Jahren entstanden - also mit "altem Speichermanagement" und vorletztes Jahr hatte ich nur ein kleines Tool in c++ geschrieben um wieder etwas rein zu kommen (Übernahme Daten aus ClearCase nach git ... war schon lustig :) ) Das einfach nur einmal um deutlich zu machen, dass ich hier kein C++ Experte bin...
 
O

ocsme

Top Contributor
Vielen Lieben Dank :)
Es geht ja jetzt. Wieso weiß ich zwar nicht so recht =D Denn so gesehen hätte, ich in meiner Zuweisung noch den selben Fehler wie im CopyKonstruktor :-D
Doch es geht erst mal. Da muss ich auch weiterhin am Ball bleiben. Es wird ja langsam besser 🙃
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M JavaScript wieder API Probleme? Dringend..? Andere Programmiersprachen 1
M JavaScript API Probleme? Dringend! Andere Programmiersprachen 3
B Probleme bei Unity Andere Programmiersprachen 2
Z char* als Rückgabewerte Probleme Andere Programmiersprachen 3
D Probleme mit Einrichtung von Umgebung(en)? Andere Programmiersprachen 5

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben