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 - 递归插入

回答

相关问题