0

我试图实现二进制搜索树的代码。问题是下面的代码不起作用，但如果我将双指针传递给插入函数，如 insert(struct bst** node, data)，它就会起作用。我认为它也应该与传递单指针一起工作。谁能解释这里的错误是什么？

void insert(struct bst* node, int data )
{
    if (node == NULL)
    {
        printf("here with %d\n",data);
        node = (struct bst*)malloc(sizeof(struct bst));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    if(data < node->data)
    {
        insert(node->left,data);
    }
    else if(data > node->data)
    {
        insert(node->right,data);
    }
}
4

3 回答 3

1

如果要更改指针的值，则应传递指针的地址（as struct node **）。

使用您的代码：

node = (struct bst*)malloc(sizeof(struct bst));

node改变函数中的值insert，但不改变调用函数中的变量。

于 2013-11-15T02:11:15.150 回答
1

如果要更改传递给函数的指针的值，则应将其作为指向指针的指针传递。

void alloc_int(int** p)
{
  *p = malloc(sizeof(int));
}

int main()
{
  int* p = NULL;
  alloc_int(&p);
  *p = 10; // here memory for p is allocated so you can use it
  free(p);
  return 0;
}

在您的示例中也是如此。您必须传递指针的地址才能更改其值（指针的值是实际数据的地址）。

于 2013-11-15T02:14:20.977 回答
1

您需要能够修改将成为node. 当您进行递归调用insert(node->left,data)时，如果node（新节点的父节点）没有左子节点（left==null），则您正在调用insert(null,data). 然后第一条if语句将创建新节点并分配其数据，但无法将该节点挂接到树中。此外，由于insert不返回新节点，因此该节点将永远丢失。

解决此问题的快速方法是返回新节点：

struct bst *insert(struct bst* node, int data, struct bst* parent )
{ /// Note new return value
    if (node == NULL)
    {
        printf("here with %d\n",data);
        node = (struct bst*)malloc(sizeof(struct bst));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        return node; /// NEW - send it back to the parent
    }

    if(data < node->data)
    {
        node->left = insert(node->left,data); /// save the new child if there wasn't one
        return node; /// otherwise, send back the node so the tree doesn't change.
    }
    else //if(data > node->data) /// On equal keys, add to the right
    {
        node->right = insert(node->right,data);
        return node;
    }
}

（免责声明：代码尚未测试）

于 2013-11-15T02:14:52.693 回答