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)

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