二叉搜索树忘记我添加的每个节点

Question

我的问题看似简单，却找不到解决办法。我有一个二叉树，这是我的添加函数：

void collection::addToTree(vendor *& item)
{
    Node * curr = root;
    while (curr)
    {
        if (strcmp(item->getName(), root->item->getName()) < 0)
            curr = curr->left;
        else
            curr = curr->right;
    }
    curr = new Node(item);
}

这是我的 Node 构造函数：

collection::Node::Node(vendor *& item) : left(nullptr), right(nullptr)
{
    this->item = item;
}

但是，树总是空的，无论我尝试向其中添加什么或多少项目。我能想到的唯一对你们有帮助的另一段代码是我的 struct 我的树：

struct Node
{
    Node();
    Node(vendor *& item);
    vendor * item;
    Node *left, *right;
};
Node * root;

vendor 的所有子变量都有值（正如我在调试器中看到的那样）。我希望我能给你们更多的细节，但这就是我所知道的关于错误的全部信息。非常感谢任何反馈。

Answer 1

在 add 函数中，您只 curr 指向新项目，但这不会改变之前的 left/right 指针，这可能就是您我们的目标是。

Answer 2

你需要直接修改left/right指针，像这样：

void collection::addToTree(vendor *& item)
{
    Node * curr = root;
    while (curr)
    {
        if (strcmp(item->getName(), curr->item->getName()) < 0)
        {
            if (!curr->left)
            {
                curr->left = new Node(item);
                return;
            }
            curr = curr->left;
        }
        else
        {
            if (!curr->right)
            {
                curr->right = new Node(item);
                return;
            }
            curr = curr->right;
        }
    }
    root = new Node(item);
}

另外，请确保你这样做 Node * root = nullptr，因为不初始化它会导致它包含任意值。

请注意，我还将 if (strcmp(item->getName(), root->item->getName()) < 0) 更改为 if (strcmp(item->getName(), curr->item->getName()) < 0)，因为分支依赖于 curr，而不是 root。

Answer 3

我认为这里的问题是您的 curr 变量应声明为 Node **curr 并接收根地址，以便更改在 addToTree 函数之外可见.

void collection::addToTree(vendor *& item)
{
    Node ** curr = &root;
    while (*curr)
    {
        if (strcmp(item->getName(), (*curr)->item->getName()) < 0)
            (*curr) = (*curr)->left;
        else
            (*curr) = (*curr)->right;
    }
    *curr = new Node(item);
}

二叉搜索树忘记我添加的每个节点

Binary Search Tree Forgetting Every Node I Add

c++

binary-search-tree