4. Knotenstruktur erstellen...

Knotenstruktur erstellen...

  • R

    Ich weis das ich nerve mit meinen binären Bäumen, aber ich habe das immer noch nicht so ganz durchdrungen.

    Ziel ist ein ganz simpler binärer Baum ( nich AVL, SearchTree, etc. )

    Ich will das mit nem struct lösen:

    struct Knoten
	{
		CString inhalt;	
		Knoten* p;		// Elternknoten
		Knoten* l;		// linker Kindknoten
		Knoten* r;		// rechter Kindknoten
	};

    So jetzt fang ich an meine Wurzel zu erstellen:

    CString temp = "Hallo";

Knoten* root = new Knoten();
	root->inhalt = temp;
	root->p = NULL;
	root->l = NULL;
	root->r = NULL;

    OK, hab ich auch geschnallt, Wurzel steht soweit!

    Was ich mir hier aber nicht erklären kann warum ich Knoten* root als root benenne! Muss ich mir dann für jeden Knoten den ich im Baum erstelle einen Namen ausdenken. Eigentlich sollte doch der Name in CString inhalt stehen.

    Jetzt versteh ich nicht wie ich einfach an die Wurzel links einen neuen Knoten anfüge. Ich muss ja den Zeiger l nutzen und dort einen Knoten erstellen, aber ich hab irgendwie nur noch Bäume und Wälder im Kopf, voll die Blockade, dabei hab ich irgendwie das Gefühl das mir nur ein simpler Teil zum Ganzen fehlt ( im Kopf bei mir mein ich jetzt ). 😕 😞

    0
  • C

    "root" (übersetzt "Wurzel") ist der Name des Wurzelknotens, an den du letzen Endes deinen gesamten Baum anhängen willst. Für weitere Knoten mußt du nicht jedes Mal eine neue Variable anlegen - da reicht es, vorübergehend eine Variable anzulegen, zu füllen und anschließend den Knoten an die richtige Stelle in den Baum einzufügen:

    Knoten* tmp = new Knoten();
Knoten* insert_pos = ... entscheide dich, wo der neue Knoten hingehört;
tmp->l = tmp->r = NULL;
tmp->p = insert_pos;
insert_pos->l = tmp;// hier hängen wir ans linke Ende an
tmp->inhalt = "Guten Abend";
//hier kannst du tmp und insert_pos entsorgen (oder recyceln) - an den Knoten kommst du später ran, indem du dich von der Wurzel durchhangelst
    0
  • R

    Was ist mit:

    CStoll schrieb:

    Knoten* insert_pos = ... entscheide dich, wo der neue Knoten hingehört;

    gemeint?
    Links von der Wurzel soll er hin!

    Meinst du:

    Knoten* insert_pos = root;
    0
  • C

    Ja, für den Anfang reicht 'insert_pos=root;' - aber wenn der Baum größer wird, ist diese Position ja vergeben und dur mußt dich von oben durchhangeln bis zur gewünschten Zielposition.

    0
  • R

    Ja, danke, das hat mich schon ein bisschen weitergebracht!

    Ein Problem habe ich jedoch noch, ich möchte nicht jedesmal zu der Position durchhangeln wo ich einen Knoten einfügen will sondern gleich dort bleiben wo ich den letzten Knoten angefügt habe und dort weitermachen.

    Also an den linken Knoten von der Wurzel aus gesehen mit dem Inhalt "Guten Abend" soll jetzt wieder einfach links einer dran.

    Dachte mir das müsste ja ganz einfach sein:

    //Wurzel
Knoten* root = new Knoten();
root->inhalt = "Wurzel";
root->p = NULL;
root->l = NULL;
root->r = NULL;			

// linker Ast
Knoten* insert_pos = root;
Knoten* tmp = new Knoten();
tmp->l = NULL;
tmp->r = NULL;
tmp->p = insert_pos;
insert_pos->l = tmp;		
tmp->inhalt = "Guten Abend"; 

// nächster linker Ast
Knoten* insert_pos = tmp;       //überschreibst einfach insert_pos mit dem
Knoten* tmp = new Knoten();     //letzten + tmp wieder neuen Knoten erstellen...
tmp->l = NULL;
tmp->r = NULL;
tmp->p = insert_pos;
insert_pos->l = tmp;
tmp->inhalt = "Guten Morgen";            // und der Rest wie gehabt

    Jetzt bringt er mir Fehler mit Mehrfachinitialisierung/Neudefinition für insert_pos und tmp. Bei näherem betrachten ist das ja auch klar. Du hattest schon angesprochen das die entsorgt werden müssen. Mit dem delete-Operator denke ich mal. Wie und wo setze ich den denn am besten ein?
    Oder hab ich schon wieder einen Denkfehler und das geht soo gar nicht!?

    0
  • C

    Die Variablen kannst du entsorgen (aus dem Scope fallen lassen) oder recyclen (wiederverwenden) - die Daten dahinter benötigst du noch, wenn du dir nicht den Baum absägen willst. Und zum Wiederverwenden kannst du den existierenden Variablen einfach neue Werte zuweisen:

    //Wurzel
Knoten* root = new Knoten();
root->inhalt = "Wurzel";
root->p = NULL;
root->l = NULL;
root->r = NULL;            

// linker Ast
Knoten* insert_pos = root;
Knoten* tmp = new Knoten();
tmp->l = NULL;
tmp->r = NULL;
tmp->p = insert_pos;
insert_pos->l = tmp;        
tmp->inhalt = "Guten Abend"; 

// nächster linker Ast
/*Knoten* */insert_pos = tmp;       //überschreibst einfach insert_pos mit dem letzten
/*Knoten* */tmp = new Knoten();     //wieder neuen Knoten erstellen...
tmp->l = NULL;
tmp->r = NULL;
tmp->p = insert_pos;
insert_pos->l = tmp;
tmp->inhalt = "Guten Morgen";
    0
  • R

    Ja, stimmt ist klar. Ich denke immer viel zu kompliziert. Und absägen ist gar nicht gut, hast recht! Vielen Dank für die Geduld!

    Wollte nochmal fragen wie ich den Debugger am besten handhabe um zu kontrollieren ob die Knoten mit den jeweiligen Inhalten an der richtigen Stelle im Baum stehen?

    0
Anmelden zum Antworten