Problem mit Binärem Baum (Klassendesign)



  • Hallo,

    in meinem Code baue ich einen Baum auf bestehend aus den folgenden Klassen:

    struct node
    {
    	double weight;
    };
    
    struct internal_node
    	: public node
    {
    	node *left;
    	node *right;
    };
    
    struct value_node
    	: public node
    {
    	char value;
    };
    

    EIne internal_node kann also nochmal eine internal_node "beinhalten", oder eine value_node. Die value_nodes befinden sich logischerweise ganz unten im Baum.

    Wie kann ich jetzt von dem ersten Knoten dem Baum bis zu den jeweiligen value_nodes folgen? Ich weiß ja nicht, um was es sich handelt. Möglichkeit wäre ein bool in der struct node + dynamic_cast aber das ist ja fürn Arsch.

    Mein Design ist also kaputt, hat jemand eine Idee wie ich das lösen kann?

    Grüße



  • ich würde nur eine node haben nämlich die die intern benutzt wird. Dann castest du nicht. Und der user kriegt einen iterator der die node versteckt, aber nur ein pointer auf eine node ist und die aktuelle position designiert.
    die letzten Knoten haben halt bei left und right null pointer verweise und du gehst halt solang rein bis du zwei null pointer triffst dann bist du am Ende. du bist am Anfang wenn der parent, welchen du auch einbauen solltest, null pointer ist.



  • Falls Du nicht auf die Ableitung verzichten möchtest, so gäbe es die Möglichkeit zwei virtuelle Methoden hinzuzufügen:

    struct node
    {
        virtual node* get_left() const = 0;
        virtual node* get_right() const = 0;
        double weight;
    };
    
    struct internal_node
        : public node
    {
        virtual node* get_left() const override
        {
            return left;
        }
        virtual node* get_right() const override
        {
            return right;
        }
        node *left;
        node *right;
    };
    
    struct value_node
        : public node
    {
        virtual node* get_left() const override
        {
            return nullptr;
        }
        virtual node* get_right() const override
        {
            return nullptr;
        }
        char value;
    };
    


  • .. weil es eine weitere Möglichkeit ist, und weil ich das schon immer mal ausprobieren wollte:
    Hier mal eine Lösung mit Visitor-Pattern

    #include <iostream>
    #include <string>
    #include <cassert>
    #include <stdexcept>
    
    struct internal_node;
    struct value_node;
    
    class Visitor
    {
    public:
        virtual void visit( internal_node& nd ) = 0;
        virtual void visit( value_node& nd ) = 0;
    };
    
    // --  Baumstruktur
    struct node
    {
        virtual void accept( Visitor& v ) = 0;
        double weight;
    };
    
    struct internal_node
        : public node
    {
        virtual void accept( Visitor& v ) override
        {
            v.visit( *this );
        }
        node *left;
        node *right;
    };
    
    struct value_node
        : public node
    {
        virtual void accept( Visitor& v ) override
        {
            v.visit( *this );
        }
        char value;
    };
    
    // --  konkrete Visitor
    class TraverseAndPrint : public Visitor
    {
    public:
        TraverseAndPrint( const char* path )
            : m_path( path )
            , m_pos( begin(m_path) )
        {}
        virtual void visit( internal_node& nd ) override
        {
            if( m_pos == end( m_path ) )
                throw std::invalid_argument( "'path' passt nicht zum Baum" );
            node* next = *m_pos == 'r' ? nd.right : nd.left;
            assert( next );
            ++m_pos;
            next->accept( *this );
        }
        virtual void visit( value_node& nd ) override
        {
            assert( m_pos == end( m_path ) );
            std::cout << "Value = '" << nd.value << "'" << std::endl;
        }
    
    private:
        std::string m_path;
        std::string::const_iterator m_pos;
    };
    
    int main()
    {
        value_node blatt_rl;
        blatt_rl.value = 'X';
        internal_node unter;
        unter.left = &blatt_rl;
        internal_node root;
        root.right = &unter;
    
        TraverseAndPrint v( "rl" );
        root.accept( v );
    }
    

    Der Vorteil dieser Lösung besteht darin, dass man außer TraverseAndPrint auch andere Visitor-Typen mit neuer Funktionalität erzeugen kann, ohne an der Baumstruktur irgendetwas ändern zu müssen.

    Gruß
    Werner


Log in to reply