BST - 遞歸插入

我已經爲BST編寫了一個遞歸插入算法。但是，算法中存在一個錯誤。如果有人可以請給我一個指針，它將不勝感激。在最初的通話中請不要說y = NULL。BST - 遞歸插入

void insert_recursive(Node **root, Node *z, Node *y) { 
    // z is the pointer to the node being inserted, and y keeps track of z's parent 
    Node *x = *root; 

    if (x != NULL) { 
     y = x; 
     if (z->val < x->val) 
      insert_recursive(&(x->left), z, y); 
     else 
      insert_recursive(&(x->right), z, y); 
    } 
    else { 
     if (y == NULL) 
      { *r = z; printf("inserting root, %d\n", z->val); } 
     else if (z->val < x->val) 
      { y->left = z; printf("inserting left of %d, item %d\n", y->val, z->val); } 
     else 
      { y->right = z; printf("inserting right of %d, item %d\n", y->val, z->val); } 
    } 
}

來源

2012-05-06 yukon

哪一系列'insert'命令最能證明錯誤？ – sarnold

只有第一個節點作爲根插入;該函數然後不傳播。謝謝... – yukon

for循環中的調用是.. recursive_insert（＆root，z，NULL），其中z是指向正在插入的節點的指針 – yukon

它可能不是唯一的問題，但你行

else if (z->val < x->val)

的if (x != NULL)的else子句中出現。換句話說，x在這裏保證爲NULL。

來源

2012-05-06 02:41:55

謝謝！是的，我的壞。它應該是'y-> val'不''x-> val'。我會接受你的回答。 – yukon

BST - 遞歸插入

回答

相關問題