Zitat Zitat von Whiz-zarD Beitrag anzeigen
Jeder Knoten stellt doch ein Wurzelknoten, für einen Teilbaum, dar. Der Rootknoten hat dann als Parent den NULL-Zeiger.
Demnach könntest du über die Parent Information nach oben iterieren, bis du den Root-Knoten erreicht hast, also bis ein Knoten den NULL-Zeiger als Parent hat.
Dann bräuchtest du nicht einmal diese Information speichern.
Ja, das ist mir bewusst.
Allerdings wird der Knoten, dessen Parent auf NULL zeigt, nicht unbedingt auch als Wurzelknoten des gesamten Baumes behandelt.
Wenn ich z.B. folgenden Baum vorliegen habe:

Code: 
      5 --> Wurzelknoten
     /
   4
  /
3
Durch eine Rechtsrotation möchte ich den Baum wieder korrigieren, also dass er wie folgt aussieht:

Code: 
    4 --> 4 ist dabei der neue Wurzelknoten
   / \
  3   5
Allerdings wird Knoten der '5' als Eintrag weiterhin als Wurzelknoten behandelt, obwohl der Parent von '5' auf die '4' zeigt und die '4' richtigerweise keinen Parent besitzt.
Wenn ich jetzt einen neuen Knoten mit den Wert '2' einfüge, sieht mein Baum so aus:

Code: 
    4 
   / \
  3   5
     /
    2
Die '2' müsste eigentlich links unter die '3'. Allerdings ist '5' weiterhin als root definiert, von daher würde dieser Knoten nie dort ankommen, wo er eigentlich hin sollte.

Hier ist auch mal der Rotationsalgorithmus:

Code: 
void rotateR(Tree y, Tree *root) {
    Tree x, z;
    x = y->left; z = y->parent;
    if(z==NULL) {(*root) = z;} //wenn y keinen parent hat, wird z als neue Wurzel definiert
    else if(z->left == y) {z->left = x;}
         else {z->right = x;}
    y->left = x->right; x->right = y; //Rechtsrotation
    x->parent = y->parent; y->parent = x;
    if(y->left != NULL) {y->left ->parent = y;}
}
Hierbei wird eine Rechtsrotation durchgeführt, wie in meinem Beispiel oben. Als Eingabe-Parameter Tree *root muss dabei auf die Wurzel des Gesamtbaums zeigen.