BST - 再帰的挿入

Question

BSTの再帰的挿入アルゴリズムを記述しました。ただし、アルゴリズムにバグがあります。もし誰かが私に指示を与えることができれば、それは非常に感謝されます。最初の呼び出しではy = NULLにしてください。

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

Answer 1

それは唯一の問題ではないかもしれないが、あなたのライン

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

はif (x != NULL)のelse句で起こります。言い換えれば、ここでxはNULLであることが保証されています。