Wurzel eines Binärbaums ausgeben



  • Hallo. In der Aufgabe brauche ich eine Methode, was mir erlaubt den Wurzel eines Wertes in einem Knoten des Binärbaums zu bekommen.
    Diesen Wert kann in irgendwelchen Knoten im Binärbaum liegen, und muss mir den Wurzel geben können.
    Hier ist die Klasse BinTree. Sie sollte zwei Werte bekommen können, beide wären gleich. Int z ist für ein Zähler, was speichert, wieviele Kinderknoten es unten gäbe.

    class BinTree {
    public:
        struct Node {
            char value1;
            //doppelte Werte zulassen
            char value2;
            Node* top; // Zeiger auf Vorgaenger (optional)
            Node* left;
            Node* right;
            int z;
            explicit Node( char ch, char ch2, Node* t = nullptr )
                : value1{ch}, value2{ch2}, top{t}, left{nullptr}, right{nullptr} {}
        };
        //Standardkonstruktor:
        BinTree() : root{nullptr}, sz{0} {}
    template<class NodeT>
    static NodeT*search(NodeT*root, const char&value){
        NodeT*now = root;
        while(now){
            if(value < now->value)
                now = now->left;
            else if(now->value < value)
                now = now->right;
            else
                return now;
        }
        return 0;
    }
        //Wurzel des Baums liefern:
        Node* get_root(const char& val)
        {
    
            Node*now = search(root, val);
            return now->get_parent_ptr(now); //Das Problem liegt hier
        }
    private:
    Node** get_parent_ptr(Node* node){
            if(node->top == 0)
                return &root;
            else if(is_left_child(node))
                return &node->top->left;
            else
                return &node->top->right;
        }
    

    In Zeile 34 der Compiler sagt:
    error: no member named 'get_parent_ptr' in 'BinTree::Node'

    wie kann ich diese Linie richtig schreiben, damit ich diese Wurzel bekomme?



  • Was ich jetzt gemacht habe ist einfach
    in der Zeile 30 das zu schreiben:

    Node** get_root(const char& val)
        {
            Node*now = search(root, val);
            return get_parent_ptr(now);
        }
    

    Ob das funktioniert sehe ich gerade. Feedback ist willkommen.



  • Es gibt eine andere Methode die ich schreiben sollte. Sie sollte sagen, ob das Binärbaum einen bestimmten Wert irgendwo unten hat.

    bool BinTree::contains(const char&t)const
    {
       return search(root, t);
    }
    

    Die search Methode:

    template<class NodeT>
    static NodeT*search(NodeT*root, const char&value){
        NodeT*now = root;
        while(now){
            if(value < now->value)
                now = now->left;
            else if(now->value < value)
                now = now->right;
            else
                return now;
        }
        return 0;
    }
    

    Jetzt auf Zeile 3 vom ersten Code den Compiler sagt:

    Fehler: undefined reference to `BinTree::Node* BinTree::search<BinTree::Node>(BinTree::Node*, char const&)'
    

    Was kann ich schreiben oder wie kann ich BinTree::Node* richtig definieren?



  • Ich habe das so geändert aber bekomme den gleichen Fehler auf Zeile 3... Bitte Hilfe

    bool BinTree::contains(char& t)
    {
         Node* now= search(root, t);
         if (now!=0)return true;
         else return false;
    }
    


  • Ok ich habe es gelöst indem ich diese Methode nicht in der Cpp sondern in der .h Datei eingefügt habe. Warum das funktioniert? Keine Ahnung



  • Warum ist das ein Template?


Log in to reply