c++ - 基于 BST 的 set 实现

Question

计划目的

我正在尝试实现set ADT。到目前为止，我已经有了接口和一些函数，例如insert()、contains()。虽然看起来我的插入函数不起作用，因为每当我输出集合的内容时，它都会显示一个空集合。

为了实现插入，我使用了帮助函数，它会递归地在集合中查找值，如果它不存在，它将插入它并返回 true。

这是set.h中set类的接口：

#include <iostream>

class set {

    // Private type
    struct treenode {
       int value;
       treenode* left;
       treenode* right;

       treenode(int val)
          : value(val),
            left(nullptr),
            right(nullptr)
       { }
    };

    size_t set_size;
    treenode* root;

    // Recursive function that creates and returns an exact
    // copy of the tree structure rooted at original
    static treenode* copynodes(treenode* original);

    // Recursive function that deallocates all of the
    // nodes in the tree structure rooted at node
    static void deallocatenodes(treenode* node);

    // Recursive function called by print to output the
    // values using in-order traversal
    static void printhelper(std::ostream &out, treenode* node){
        if (node != nullptr) {
            if (node->left != nullptr) {
                printhelper(out, node->left);
                out << ", ";
            }
            out << node->value;
            if (node->right != nullptr) {
                out << ", ";
                printhelper(out, node->right);
            }
        }
    }

    static bool containshelper(int i, treenode *node);

    static bool inserthelper(int i, treenode *node);

public:

    // Default constructor
    set() : set_size(0), root(nullptr) { }

    // Copy constructor
    set(const set &s) : set_size(s.set_size), root(nullptr) 
    {
        root = copynodes(s.root);
    }

    // Initializer list constructor
    set(std::initializer_list<int> init) : set_size(0), root(nullptr) 
    {
        for (auto el : init) {
            insert(el);
        }
    }

    // Copy assignment
    set& operator=(const set &s) {
        if (&s != this) {
            deallocatenodes(root);
            root = copynodes(s.root);
            set_size = s.set_size;
        }
        return *this;
    }

    // Returns true if the value i is in the ordered set
    bool contains(int i) const;

    // If the value i is not in the set,
    // insert it and return true;
    bool insert(int i);

    // Remove everything from the set
    void clear();

    // Returns the number of items in the set
    size_t size() const;

    // Returns whether or not the set is currently empty
    bool empty() const;

    // Print out the contents of the set, in order from smallest to largest
    void print(std::ostream &out) const {
        out << "{";
        printhelper(out, root);
        out << "}";
    }

    // Destructor
    ~set() {
        deallocatenodes(root);
    }
};

inline std::ostream& operator<<(std::ostream &out, const set &s) {
    s.print(out);
    return out;
}

功能的实现

这是我在 set.cpp 中实现的：

#include "set.h"
#include <iostream>

set::treenode* set::copynodes(treenode *original) {
    
    if(original == nullptr) {
        return nullptr;
    }
    
    treenode *copiedTree = new treenode(original->value);
    
    copiedTree->left = copynodes(original->left);
    copiedTree->right = copynodes(original->right);
    
    return copiedTree;
}

void set::deallocatenodes(set::treenode *node) {
    
    if(node != nullptr) {
        deallocatenodes(node->left);
        deallocatenodes(node->right);
        delete node;
    }
    
}

bool set::containshelper(int i, set::treenode *node) {
    
    if (node == nullptr)
       return false;

    // i found
    else if (node->value == i)
       return true;

    // Recursively search for i
    else if (i < node->value)
       return (containshelper(i, node->left));
    
    else
       return (containshelper(i, node->right));
    
}

bool set::inserthelper(int i, set::treenode *node) {
    
    if(node == nullptr) {
        node = new treenode(i);
        return true;
    } else if(i == node->value) {
        return false;
    } else {
        if(i < node->value){
            return (inserthelper(i, node->left));
        } else if(i > node->value){
            return (inserthelper(i, node->right));
        }
        
        return false;
        
    }
    
}

bool set::contains(int i) const {
    
    return containshelper(i, root);
    
}

bool set::insert(int i) {
        
    if(inserthelper(i, root) == true) {
        set_size++;
        return true;
    } else {
        return false;
    }
    
}

void set::clear() {
    set_size = 0;
    deallocatenodes(root);
}

size_t set::size() const {
    return set_size;
}

bool set::empty() const {
    return (set_size == 0);
}

测试实施

测试文件 main.cpp 如下所示：

#include "set.h"
#include <iostream>

void output(const set& s) {
    std::cout << "SET OUTPUT: " << std::endl;
    std::cout << s.size() << " " << s.empty() << " " << s << std::endl;
    std::cout << "END OF OUTPUT." << std::endl;
}


int main() {

    set s1;
    output(s1);

    set s2 = {44, 22, 11, 33, 55};
    output(s2);

    set s3(s2);
    output(s3);

    for (int i = 99; i > 0; i = i - 11) {
         std::cout << i << " " << s2.insert(i) << " " << s2.contains(i) << "; ";
    }
    std::cout << std::endl;
    output(s2);

    for (int i = 15; i < 100; i = i + 5) {
         std::cout << i << " " << s2.insert(i) << " " << s2.contains(i) << "; ";
    }
    std::cout << std::endl;
    output(s2);

    output(s3);

    s1 = s2;
    output(s1);

    s1.clear();
    output(s1);
    output(s2);
    output(s3);

    s1.insert(123);
    s1.insert(234);
    s1.insert(98);
    output(s1);

    std::cout << "Done." << std::endl;
}

程序输出

当我编译并运行时，输出是：

SET OUTPUT: 
0 1 {}
END OF OUTPUT.
SET OUTPUT: 
5 0 {}
END OF OUTPUT.
SET OUTPUT: 
5 0 {}
END OF OUTPUT.
99 1 0; 88 1 0; 77 1 0; 66 1 0; 55 1 0; 44 1 0; 33 1 0; 22 1 0; 11 1 0; 
SET OUTPUT: 
14 0 {}
END OF OUTPUT.
15 1 0; 20 1 0; 25 1 0; 30 1 0; 35 1 0; 40 1 0; 45 1 0; 50 1 0; 55 1 0; 60 1 0; 65 1 0; 70 1 0; 75 1 0; 80 1 0; 85 1 0; 90 1 0; 95 1 0; 
SET OUTPUT: 
31 0 {}
END OF OUTPUT.
SET OUTPUT: 
5 0 {}
END OF OUTPUT.
SET OUTPUT: 
31 0 {}
END OF OUTPUT.
SET OUTPUT: 
0 1 {}
END OF OUTPUT.
SET OUTPUT: 
31 0 {}
END OF OUTPUT.
SET OUTPUT: 
5 0 {}
END OF OUTPUT.
SET OUTPUT: 
3 0 {}
END OF OUTPUT.
Done.
Program ended with exit code: 0

可以看出，集合没有元素，其中一些元素的大小不正确。例如，使用insert()函数在循环后设置 2 应该有 9 个元素，但它确实有 14 个元素，这意味着其中一些是重复的。

我试图在纸上使用 BST 可视化在集合上完成的操作，但找不到问题出在哪里。

标签： c++setbinary-search-tree

Answer 1

所以你有一个常见的初学者误解。在您的inserthelper功能中，您有（缩写）

bool set::inserthelper(int i, set::treenode *node) {

    ...    
        node = new treenode(i);
    ...
            return (inserthelper(i, node->left));
    ...
            return (inserthelper(i, node->right));
    
}

node = 更改node参数，但仅此而已。它不会更改传递给 的指针inserthelper。它不会改变node->left或node->right在递归调用中对inserthelper. 方法上没有变化root。insert原因是这是传递给函数的指针node的副本。更改它不会更改原始指针。

这与整数完全相同。如果你写了这段代码

int i = 10;
some_func(i);
cout << i << endl;

void some_func(int j)
{
   j = 11;
}

你会看到输出10不是11因为some_func不改变i变量。许多程序员都明白这一点，但是当涉及到指针时，他们会感到困惑，并认为指针的规则是不同的，但事实并非如此。正如 molbdnilo 所说，指针没有什么特别之处。

我想造成混淆的原因是当指针传递给函数时，指针被复制，但它指向的不是。初学者可能会理解这一点，但会感到困惑，并认为指针和它所指向的内容都不会被复制。但这是不正确的。通常，理解指针的关键是在脑海中清楚指针本身与指针所指向的内容之间的区别。

因此，您的代码有一个简单的修复方法。改成inserthelper这个

bool set::inserthelper(int i, set::treenode*& node) {

Using&会node产生引用，因此分配给node确实会改变原始数据。node现在是对原始变量的引用，而不是原始值的副本。