c - 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)

出现在 的else子句中if (x != NULL)。换句话说，这里保证 x 为 NULL。