c++中的BST，添加节点时returntrue或false

Question

我现在正在学习 C++。

我想将 BST 中的 add 函数的 return 类型设置为 bool，如果树中已经存在相同的项目，则 return 为真，并且 return false 当它被添加到树中时。

这是代码，关于如何实现这个目标有什么建议吗？

节点中的代码class(.h文件):

node* insert(string content, node* t)
{
    if(t == NULL)
    {
        t = new node;
        t->data = content;
        t->left = t->right = NULL;
    }
    else if(content < t->data)
        t->left = insert(content, t->left);
    else if(content > t->data)
        t->right = insert(content, t->right);
    return t;
}

.cpp 文件中的代码：

BST :: BST() {
    root = NULL;
}

void BST :: add(string content) {
    root = insert(content, root);
}

有什么建议吗？此代码也引用自 BST Implementation in C++

Answer 1

最简单的方法是进行搜索以识别要插入的父节点。我可以给你看元组，但现在只用一个输出参数来指示“值已经在树中”的条件是否是一个输出参数会更容易。

node* makeNode(const string& content)
{
    node* n = new node();        
    n->left = pNode->right = nullptr;
    n->data = content;
    return n;
}

node* BST::findLeafNode(const string& content, node* n, bool* alreadyExists)
{
    *alreadyExists= false;

    if (n == nullptr)
    {
       return nullptr; // this should only happen when root == nullptr
    }

    if (content == n->data)
    {
        *alreadyExists = true; // exact match
        return n;
    }

    if (content < n->data)
    {
        return (n->left ? findLeafNode(content, n->left) : n;
    }
    else
    {
        return (n->right ? findLeafNode(content, n->right) : n;
    }

}

bool BST::add(const string& content)
{
    bool alreadyExists = false;
    node* parent = findLeafNode(content, root, &alreadyExists);
    if (same)
    {
       return false;
    }
    node* n = makeNode(content);

    if (parent == nullptr)
    {
        root = n;
    }
    else
    {
        if (content < n->data)
        {
           n->left = n;
        }
        else
        {
           n->right = n;
        }
     }
     return true;
}

c++中的BST，添加节点时returntrue或false

BST in c++, return true or false when adding node

c++

binary-search-tree

data-structures