BinaryTreeNode - wie funktioniert das?

hype_

Hallo,

vielleicht könnt ihr mir weiterhelfen.

Ich habe folgende Klasse:

class BinaryTreeNode{

   private:
     int content; // Data
     BinaryTreeNode *l_next; // left successor
     BinaryTreeNode *r_next; // right successor

   public:

     BinaryTreeNode(int content){
        this->content = content;
        l_next = TNULL;
        r_next = TNULL;
     }// end constructor
     // ggf. weitere Konstruktoren

     int countNodes(){
        return countNodes(this);
     }// end countNodes()

     int treeHeight(){
        return treeHeight(this);
     }// end treeHeight()

     // weitere Methoden

};// end of class BinaryTreeNode

Nun sollen für diese Klasse z.B. rekursive private Methoden codiert werden.
Zum Beispiel um die Anzahl der Nodes zu berechnen oder die Baumhöhe.
Zusätzlich eine Funktion um neue Nodes aufzunehmen.

Ich verstehe nur Bahnhof, kann man hier jemand einen Denkanstoß geben?

Grüße

//Edit: CodeTags

Blue-Tiger

hype_ schrieb:

Nun sollen für diese Klasse z.B. rekursive private Methoden codiert werden.
Zum Beispiel um die Anzahl der Nodes zu berechnen oder die Baumhöhe.
Zusätzlich eine Funktion um neue Nodes aufzunehmen.

Ich verstehe nur Bahnhof, kann man hier jemand einen Denkanstoß geben?

Grüße

Traversier den Baum rekursiv und zaehl dabei mit, wieviel Nodes du besuchst bzw. wie tief du schon abgestiegen bist

hype_

Okay, von der Theorie her klar, aber wie soll der Code dafür aussehen?
Das blicke ich nicht.

Gibt es da irgendwo im Netz eine gute Anleitung mit Beispielen?

hype_ schrieb:

Gibt es da irgendwo im Netz eine gute Anleitung mit Beispielen?

Du verlangst aber jetzt nicht dass wir dir das Googlen abnehmen, nöch?
google.de weiß das nämlich sicher!

hype_ schrieb:

Okay, von der Theorie her klar, aber wie soll der Code dafür aussehen?

Nur nicht verwirren lassen. Die Anzahl der Knoten in einem Baum ist Eins plus die Anzahl der Knoten im rechten Ast plus die Anzahl der Knoten im linken Ast.

Die Tiefe eines Baumes ohne Äste ist Eins. Die Tiefe eines Baumes mit Ästen ist Eins plus die Tiefe des tiefsten Astes.

hype_ schrieb:

Zusätzlich eine Funktion um neue Nodes aufzunehmen.

Das ist leicht, einfach zwei Knoten hernehmen und die Zeiger so umbiegen, dass der neue Knoten in der Mitte ist. Der Knackpunkt ist wahrscheinlich die Frage, wo denn der neue Knoten hin soll.

hype_

Okay, zuerst mal die insertNode.

BinaryTreeNode * insertNode(BinaryTreeNode *Blatt, int content)
{
    if (Blatt==0) 
    { 
        Blatt = new BinaryTreeNode(0);
        Blatt->l_next = Blatt->r_next = 0;
        Blatt->content = content;
        return Blatt; 
    }
    if (content < Blatt->content)
    { 
        Blatt->l_next = insertNode(Blatt->l_next, content);
    }
    else if (content > Blatt->content)
    { 
        Blatt->r_next = insertNode(Blatt->r_next, content);
    }
    return Blatt;
}

int treeHeight(BinaryTreeNode *Blatt)
{
    int zaehler = 0;
    zaehler++;
    if (Blatt==0) return zaehler;
    treeHeight(Blatt->l_next);

}

Im Main:

BinaryTreeNode *root = new BinaryTreeNode(0);
root->insertNode(root, 1);

cout << root->treeHeight(root);

Da kommt nun 4078912 raus, stimmt irgendwie nicht

//Edit: CodeTags

hype_

Hab es nun so gelöst:

int treeHeight(BinaryTreeNode *n)
	{
		if(n == NULL)
			return 0;
		else 
		{
			int hl = treeHeight(n->l_next);
			int hr = treeHeight(n->r_next);
			return (hl > hr?  hl:  hr) + 1;
		}
	}

	   int countNodes(BinaryTreeNode *n)
	{
		if(n == NULL)
			return 0;
		else 
		{
			int hl = treeHeight(n->l_next);
			int hr = treeHeight(n->r_next);
			return (hl + hr + 1);
		}
	}

int countNodes(BinaryTreeNode *n)
    {
        if(n == NULL)
            return 0;
        else
        {
            int hl = treeHeight(n->l_next);
            int hr = treeHeight(n->r_next);
            return (hl + hr + 1);
        }
    }

Du meinst wahrscheinlich countNodes statt treeHeight:

int countNodes(BinaryTreeNode *n)
{
    return n ? 1 + countNodes(n->l_next) + countNodes(n->r_next) : 0;
}

Schade eigentlich, dass man mit Rekursionen in C++ vorsichtig sein muss.