C++模板TreeSet实现求助：分支叶子结构有序集合开发

嘿，我来帮你梳理下这个TreeSet的实现思路，你现在的代码已经搭好了基础框架，接下来可以按以下步骤一步步完善，解决当前的困惑：

我的需求与现状 #

我需要实现一个基于模板的TreeSet，要求包含TreeSet（对应老师要求的SortedTree）基类、Branch和Leaf子类：

• 叶子节点的size固定为0，create_empty_set()需返回叶子节点；
• 添加T类型数据时，叶子要转为分支，元素按有序规则存储（分支值大于左子树所有值、小于右子树所有值）；
• 不允许存储重复元素；
• 添加操作需返回新的TreeSet，原树保持不变。

目前我已经写了基础代码，但不知道如何推进，恳请指引方向。

老师的要求 #

So, you'll need three classes: a supertype SortedTree and two subtypes named Branch and Leaf. LinkedList nodes carried little integers with them. For our set, we want to do something better: we wish the set to be able to contain any kind of values. The way to accomplish this is to make use of templates: a TreeSet contains values of type T.

Where do the set's elements reside exactly? Each Branch node contains exactly one T, while the leaves contain nothing: they merely serve as "plugs" to fill the holes in the tree.

We don't want the T-values to be stored arbitrarily: there'd be no point in using a tree. We want the values to be sorted. As mentioned above, each branch refers to two nodes (its child nodes) and has its own value. A branch's value must be larger than all values stored in its left children but less than all values stored in its right children.

For example (leaves are not shown):

[BRANCH 8]
|
+---------------+ +-------------------+
|               | |                   |
[BRANCH 4]    [BRANCH 11]
|               | |                   |
+-----+ +----+  +-----+ +------+
|     | |    |  |     | |      |
[BRANCH 1] [BRANCH 7] [BRANCH 9] [BRANCH 15]

Take the root node, i.e., the branch carrying 8. All values in its left node (1, 4, 7) are less than 8 and the values in the right children (9, 11, 15) are all greater than 8. The same rule is applicable on each branch in the tree.

Note that no duplicates are allowed: a set cannot contain the same value twice.

树结构示例 #

[BRANCH] --> [BRANCH] --> [BRANCH] --> [LEAF]
      |             |             |
      |             |             +-----> [LEAF]
      |             |
      |             +-----> [BRANCH] --> [LEAF]
      |                           |
      |                           +-----> [LEAF]
      |
      +------> [BRANCH] --> [LEAF]
                |
                +-----> [BRANCH] --> [LEAF]
                          |
                          +-----> [LEAF]

我已完成的代码 #

#ifndef TREE_SET_H
#define TREE_SET_H
#include <memory>

template<typename T>
class TreeSet {
public:
    TreeSet();
    virtual int size();
    std::shared_ptr<TreeSet<T>> add(T data);
private:
    int _size;
    T value;
    std::shared_ptr<TreeSet<T>> left;
    std::shared_ptr<TreeSet<T>> right;
};

template<typename T>
class Leaf : public TreeSet<T> {
public:
    Leaf();
private:
};

template<typename T>
class Branch : public TreeSet<T> {
public:
    Branch();
private:
};

template <typename T>
TreeSet<T>::TreeSet():_size(0) { }

template<typename T>
Leaf<T>::Leaf() : TreeSet() { }

template<typename T>
Branch<T>::Branch() : TreeSet() { }

template <typename T>
std::shared_ptr<TreeSet<T>> create_empty_set() {
    //return std::make_shared<TreeSet<T>>();
    return std::make_shared<Leaf<T>>();
}

template<typename T>
int TreeSet<T>::size() {
    return _size;
}

template<typename T>
std::shared_ptr<TreeSet<T>> TreeSet<T>::add(T data) {
    return std::shared_ptr<TreeSet<T>>();
}
#endif

测试用例 #

#include "Catch.h"
#include "tree-set.h"
#include "util.h"

/* Add a method named "add" to the hierarchy. The method must take a value to be added to the set and return a new TreeSet that contains the element. The original tree must remain unchanged. Also update Branch's size(). */

TEST_CASE("Adding element to TreeSet<int> yields new TreeSet<int>") {
    const auto t1 = create_empty_set<int>();
    std::shared_ptr<TreeSet<int>> t2 = t1->add(5);
}

TEST_CASE("Adding element to TreeSet<bool> yields new TreeSet<bool>") {
    auto t1 = create_empty_set<bool>();
    std::shared_ptr<TreeSet<bool>> t2 = t1->add(true);
}

TEST_CASE("Adding single element increments size from 0 to 1") {
    auto t1 = create_empty_set<bool>();
    auto t2 = t1->add(true);
    CHECK(t2->size() == 1);
}

TEST_CASE("Adding leaves the original TreeSet unchanged") {
    auto t1 = create_empty_set<char>();
    auto t2 = t1->add('a');
    CHECK(t1->size() == 0);
}

TEST_CASE("Adding multiple elements increases size by 1 at each time") {
    auto t = create_empty_set<int>();
    CHECK(t->size() == 0);
    t = t->add(0);
    CHECK(t->size() == 1);
    t = t->add(1);
    CHECK(t->size() == 2);
    t = t->add(2);
    CHECK(t->size() == 3);
    t = t->add(3);
    CHECK(t->size() == 4);
}

TEST_CASE("Adding an element already in the set does not increment size") {
    auto t = create_empty_set<int>();
    CHECK(t->size() == 0);
    t = t->add(0);
    CHECK(t->size() == 1);
    t = t->add(0);
    CHECK(t->size() == 1);
    t = t->add(78);
    CHECK(t->size() == 2);
    t = t->add(78);
    CHECK(t->size() == 2);
}

核心改进步骤指引 #

1. 重构基类为抽象类 #

现在的TreeSet基类混合了Leaf和Branch的成员变量，这不符合多态设计。我们应该把它改成抽象基类，只定义纯虚方法，让子类去实现：

template<typename T>
class TreeSet {
public:
    // 虚析构函数：避免删除子类对象时内存泄漏
    virtual ~TreeSet() = default;
    // size方法：返回节点的元素总数，const修饰表示不修改对象
    virtual int size() const = 0;
    // add方法：添加元素并返回新的树，原树保持不变
    virtual std::shared_ptr<TreeSet<T>> add(const T& data) const = 0;
};

2. 完善Leaf类的实现 #

Leaf是没有元素的空节点，size固定为0，add方法需要创建一个新的Branch节点（把自己转成带元素的分支）：

template<typename T>
class Leaf : public TreeSet<T> {
public:
    int size() const override {
        return 0;
    }

    std::shared_ptr<TreeSet<T>> add(const T& data) const override {
        // 创建新分支：值为data，左右子节点都是空Leaf
        return std::make_shared<Branch<T>>(data,
            std::make_shared<Leaf<T>>(),
            std::make_shared<Leaf<T>>());
    }
};

3. 实现Branch类的核心逻辑 #

Branch需要存储元素值、左右子树，并且维护正确的size。核心是实现add方法，遵循有序规则且不允许重复：

template<typename T>
class Branch : public TreeSet<T> {
private:
    T value;
    std::shared_ptr<TreeSet<T>> left;
    std::shared_ptr<TreeSet<T>> right;
    int _size; // 缓存size，避免每次递归计算，提升效率

public:
    // 构造函数：初始化值、左右子树，计算总size
    Branch(const T& val, std::shared_ptr<TreeSet<T>> l, std::shared_ptr<TreeSet<T>> r)
        : value(val), left(std::move(l)), right(std::move(r)),
          _size(1 + left->size() + right->size()) {}

    int size() const override {
        return _size;
    }

    std::shared_ptr<TreeSet<T>> add(const T& data) const override {
        if (data == value) {
            // 元素已存在，返回当前分支的拷贝（原树不变）
            return std::make_shared<Branch<T>>(*this);
        } else if (data < value) {
            // 插入左子树：递归调用左子树的add，生成新的左分支
            auto new_left = left->add(data);
            return std::make_shared<Branch<T>>(value, new_left, right);
        } else {
            // 插入右子树：递归调用右子树的add，生成新的右分支
            auto new_right = right->add(data);
            return std::make_shared<Branch<T>>(value, left, new_right);
        }
    }
};

4. 修正辅助函数与构造函数 #

删除原来基类的构造函数（因为现在是抽象类），create_empty_set保持不变即可：

template <typename T>
std::shared_ptr<TreeSet<T>> create_empty_set() {
    return std::make_shared<Leaf<T>>();
}

5. 关键注意点 #

• 确保T类型支持<和==比较运算符，如果要存储自定义类型，需要重载这两个运算符；
• 所有add方法都是const的，这保证了原树不会被修改，完全符合测试用例中"原树保持不变"的要求；
• 使用std::move转移子树的所有权，避免不必要的拷贝，提升性能。

按照这个思路修改后，你的代码应该能通过所有测试用例，完美实现老师要求的功能~

内容的提问来源于stack exchange，提问作者Kelvijn