Binäre Suchbaumeinfügung C ohne Rekursion

Question

Ich bin neu auf der Seite und ich bin wirklich fest an den Hausaufgaben meiner Universität, um eine Funktion neu zu erstellen, die Knoten in den Baum ohne Rekursion einfügt. Mir wurde die Rekursive Methode gegeben und ich muss sie in Iterativ konvertieren. Dies ist der gegebene rekursive Code:

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode) 
{ 
    if (!root) 
    { 
     root = newnode; 
     root->left = root->right=NULL; 
    } 
    else if (newnode->entry < root->entry) 
    { 
     root->left = InsertTree(root->left, newnode); 
    } 
    else 
    { 
     root->right = InsertTree(root->right, newnode); 
    } 
    return root; 
} 

und ich machte diese:

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode) 
{ 
    if (!root) 
    { 
     root = newnode; 
     root->left = root->right=NULL; 
    } 
    else 
    { 
     TreeNode * temp = root, *prev = NULL; 

     while(temp) 
     { 
     if (temp->entry < newnode->entry) 
      temp = temp->right; 
     else 
      temp = temp->left; 
     } 
     newnode; 
     temp->left = temp->right = NULL; 
    } 
    return root; 
} 

es für die ersten Elemente funktioniert, aber es speichert nicht die übrigen Elemente. Irgendwelche Ideen? Vielen Dank im Voraus

Answer 1

Die (un) Nutzung von prev zeigt das Bewusstsein, dass die rekursive Ergebnisse müssen ausgebessert werden. Da bereits eine Lösung von anderen gegeben ist, hier die "ideale" Lösung, die Pointer-Aliase verwendet.

Strom wird am Endpunkt auf root oder links/rechts von einem Knoten; Null sein.

Beachten Sie, dass diese Verwendung von Aliasen in einigen anderen Sprachen wie Java nicht existiert. Einer der sehr wenigen Vorteile von C.

Der & Präfix-Operator nimmt die Adresse der Variablen.

Answer 2

Dies ist der Code, um ein Element iterativ einzufügen. Da das neue einzufügende Element bereits erstellt/zugewiesen wurde, ist es nicht sinnvoll, das linke/rechte Feld der Struktur zu initialisieren, sobald das Element erstellt wurde.

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode){ 

     //assuming newnode->left/right already == NULL 
     if(root==NULL){ 
      root = newnode; 
     } 
     else { 
      TreeNode * prev = NULL; 
      TreeNode * curr = root; 
      while(curr != NULL){ 
       prev = curr; 
       if(curr -> entry < newnode -> entry) curr = curr -> right; 
       else curr = curr -> left; 
      } 
      if (prev -> entry < newnode -> entry) prev -> right = newnode; 
      else prev -> left = newnode; 

     } 
     return root; 
    }