-1

我知道这可能看起来很简单，但在过去的几个小时里我一直在摸不着头脑，试图弄清楚为什么无论我做什么，thisNode 总是为 NULL。因为这是空的，这意味着实际上没有任何东西最终被添加到树中。有没有人有任何想法？啊啊啊

struct node *tra(struct node * start, Type input) 
{
    struct node * thisNode = start;

    if (thisNode == NULL)
        return thisNode;
    else 
    {
        Type current = thisNode -> el;

        if (strcmp(input, current) > 0)
            return tra(thisNode -> right, input);
        else if (strcmp(input, current) < 0)
            return tra(thisNode -> left, input);
        else
        return thisNode;
    }
}

Ta insert(Type input, Ta ta) 
{
    if ((find(input, ta)) == FALSE) 
    {
        struct node *newEl = tra(ta -> head, input);
        newEl = (struct node*)malloc(sizeof(struct node));
        newEl -> el = input;
        newEl -> left = NULL;
        newEl -> right = NULL;
    }

    return ta;
}

Boolean find(Type input, Ta ta) 
{
    if (tra(ta -> head, input) == NULL)
        return FALSE;
    else
        return TRUE;
}
4

2 回答 2

1

这是问题所在：

        struct node *newEl = tra(ta -> head, input);
        newEl = (struct node*)malloc(sizeof(struct node));

您分配了新节点，但是指针 newEl 丢失了。您的函数 tra 应该返回一个指向该指针的指针，以让插入函数修改您附加新创建节点的节点。

于 2013-02-17T22:49:58.353 回答
0

问题如下：

当 BST 中没有任何内容时，这会触发tra：

if (thisNode == NULL)
    return thisNode;

那么newEl == NULL在insert.

然后你malloc为指针分配newEl一个指向分配内存的新值。但是您返回的原始指针仍然具有值NULL（因为给指针的副本一个新值不会改变原始指针）。

处理此问题的选项：

  • 返回指向指针 ( struct node **) 的指针（我认为您还需要将指向指针的指针作为参数传递给insert函数）。
  • 更改您的签到tra以查看下一个元素（以及适当的更改）。对于链接列表，它看起来像：if (thisNode->next == NULL) return thisNode;并且insert您将使用newEl->next. 虽然对于链表来说通常是一个不错的选择，但对于 BST 来说这需要付出更多的努力，因为您需要返回左节点或右节点是NULL，或者在insert.
    • 注意 - 您必须使用其中一个newEl->left或newEl->rightin insert。
  • 通过引用返回 - 这可能是最简单的选择。更改tra为 returnstruct node *&并将newEl声明更改为struct node *&newEl = ...，这可能就是全部。
于 2013-02-17T22:53:37.820 回答