4. Suchbaum - Fragen (class)

Suchbaum - Fragen (class)

  • ?

    Guten Abend, ersteinmal, ich lerne z.Z. programmieren, und ich will ein paar Dinge "ausprobieren" z.Z. sitze ich an einem Baumprogramm(Suchbaum).

    class tree_t {
    public:
    int value ; //Enthaelt den eigenen Wert
    tree_t * parent ;//zeigt auf das "Elternteil"
    tree_t * rechts ;//Zeigt auf den rechten "unter"-Baum
    tree_t * links ;//Zeigt auf den Linken "unter"-Baum
} Baum[MAX_KNOTEN];

    Mein Problem bei der Sache ist, wenn ich starte, woran sehe ich ob ein Knoten schon gesetzt ist oder nicht?
    Und wie lasse ich einen Knoten auf seinen Parent/Unterbaum zeigen?
    bzw, wie lese ich aus den gespeicherten Werten dann raus, welcher Knoten nun rechts/links oder parent ist? 😕
    lg- koen

    0
  • I

    Gehoert das nicht ins C++ Forum?

    Ich finde deinen Ansatz fuer die Implementierung etwas merkwuerig. Damit meine ich, dass du ein rohes Array von tree Objekte erstellen moechtest.

    Hier findest du einen guten Artikel darueber wie man einen Suchbaum implementiert.

    0
  • M

    icarus2 schrieb:

    Gehoert das nicht ins C++ Forum?

    Ja, dort könnte es hingehören.

    Ein leerer Knoten hat üblicherweise den Wert NULL.

    Die Implementation als class ist möglich, was allerdings das
    Array da soll ist zumindest fraglich.

    Wenn es unbedingt der OOP-Ansatz sein soll fehlt mindestens
    der Konstruktor um die Membervariablen zu initialisieren.
    Eigentlich sollten Membervariablen auch nicht public sein.

    Als Basis ist die bereits genannte URL OK.

    Hier ein erster Ansatz (verbesserungsbedürftig) [VS2010]

    #include <stdio.h>
#include <tchar.h>

class Tree { 
public: 
   Tree();
   Tree(int value);
   Tree *Tree_Insert(int value);
   // ...
// besser private:	
   Tree * m_parent;   //zeigt auf das "Elternteil" 
   Tree * m_right;    //Zeigt auf den rechten "unter"-Baum 
   Tree * m_left;	     //Zeigt auf den Linken "unter"-Baum 
   int m_value;       //Enthaelt den eigenen Wert 
};

Tree::Tree()
{
   m_parent = m_right =  m_left = NULL;
   m_value = 0;
}

Tree::Tree(int value)
{
   m_parent = m_right = m_left = NULL;
   m_value = value;
}

Tree *Tree::Tree_Insert(int value)
{
   class Tree *now = this;
   class Tree *parent;

   bool is_left_child = false; 
   while(now){ 
        parent = now; 
        if(value < now->m_value){ 
            is_left_child = true; 
            now = now->m_left; 
        }
        else if(now->m_value < value){ 
            is_left_child = false; 
            now = now->m_right; 
        }
        else 
            return false; // Das Element ist bereits im Baum 
    } 

   // Neues Blatt erzeugen
   class Tree *Blatt = new Tree(value);

   // Blatt einhaengen
   Blatt->m_parent = parent; 
   if(parent != 0) {
      if(is_left_child) 
         parent->m_left = Blatt; 
      else 
         parent->m_right = Blatt; 
      }

return Blatt;
}

int _tmain(int argc, _TCHAR* argv[])
{
	class Tree wurzel(15);

	wurzel.Tree_Insert(22);

	// ...

	return 0;
}
    0
Anmelden zum Antworten