二元搜索樹插入C無遞歸

我是新來的頁面，我真的堅持在我的大學的作業重新創建一個函數，插入節點到樹沒有遞歸。我已經給了遞歸方法，我需要將其轉換爲迭代。這是給定的遞歸代碼：二元搜索樹插入C無遞歸

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; 
}

和我做了這一個：

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; 
}

它工作的第一要素，但它不保存其餘的元素。任何想法？在此先感謝

來源

2016-04-22 Ilias Mentz

對於非根情況，您的代碼永遠不會將'newnode'指針指定爲樹中已有節點的子節點。 –

@Roux，雖然他可能打算這樣做，但它不會解決他的問題，因爲'temp'只是一個局部變量。 –

prev的（不）使用表示意識到遞歸結果需要修補。正如其他人已經提出了一個解決方案，這裏是使用指針別名的「理想」解決方案。

TreeNode **current = &root; 
    while (*current) 
    { 
     if (newnode->entry < (*current)->entry) 
     { 
      current = &(*current)->left; 
     } 
     else 
     { 
      current = &(*current)->right; 
     } 
    } 
    *current = newnode; 
    newnode->left = newnode->right = NULL; 
    return root;

當前會在結尾處指向根節點或節點的左/右;爲空。

請注意，別名的這種用法在java等其他語言中不存在。 C.

&前綴運算符取其變量的地址的幾個優點之一。

來源

2016-04-22 14:03:50

A **（**在你的代碼的倒數第二行缺少 –

@GerardoZinno謝謝，更正 –

@JoopEggen這是工作完美非常感謝你的幫助！ –

這是迭代插入元素的代碼。由於要插入的新元素已經被創建/分配，所以只要元素被創建，就沒有必要不初始化結構的左/右字段。

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; 
    }

來源

2016-04-22 13:56:27

非常感謝你！ –

二元搜索樹插入C無遞歸

回答

相關問題