使用模板的C++ treeset实现

Question

我必须为树集编写一个模板.叶子的大小为0.当调用create_empty_set()时,它应该生成一个叶子,当你添加T数据时,叶子应该成为一个分支,它的值应该放在左边或右边.不允许重复.我在这里发布老师的指示:

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<T> 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);
}

这是另一个考验

    /*
    Add a method size() to your hierarchy. For now, Branch's implementation of this method
    can return a dummy value.
*/


TEST_CASE("Size of an empty TreeSet<int> is zero")
{
    const auto t = create_empty_set<int>();

    CHECK(t->size() == 0);
}

TEST_CASE("Size of an empty TreeSet<bool> is zero")
{
    const auto t = create_empty_set<bool>();

    CHECK(t->size() == 0);
}

TEST_CASE("Size of an empty TreeSet<char> is zero")
{
    const auto t = create_empty_set<char>();

    CHECK(t->size() == 0);
}

TEST_CASE("TreeSet is a polymorphic type (i.e., it contains at least one virtual member)")
{
    const auto t = create_empty_set<int>();
    CHECK(is_leaf(*t));
}

这是给定的util.h标头

   #ifndef UTIL_H
#define UTIL_H

struct Foo
{
    bool operator <(const Foo& foo) const
    {
        return false;
    }
};

struct Bar
{
    int x;

    bool operator <(const Bar& bar) const
    {
        return x < bar.x;
    }
};

template<typename T, typename U>
bool has_dynamic_type(const U& x)
{
    return dynamic_cast<const T*>(&x) != nullptr;
}

template<typename T>
bool is_leaf(const TreeSet<T>& x)
{
    return has_dynamic_type<Leaf<T>>(x);
}

template<typename T>
bool is_branch(const TreeSet<T>& x)
{
    return has_dynamic_type<Branch<T>>(x);
}

#endif

在此先感谢,Kelvijn

Answer 1

你的问题非常广泛。有几点我想指出。首先，由于您的树节点是模板类，为了对树进行排序，您应该能够对类型进行比较和排序。您可以比较整数，您可以比较字符串（您必须定义一个函数来比较它们或使用 strcmp），但您不能真正比较布尔值。除非您想将 false 放在左侧，将 true 放在右侧。此外，当您创建“Foo”树（其中 Foo 是某个类）时，您需要为该类定义一个比较器。也许重载所有或部分运算符 == < > >= <=

无论如何，对树进行排序也意味着保持其平衡的操作。我建议您从维基百科https://en.wikipedia.org/wiki/Tree_sort开始并搜索其他问题和答案。

另一件重要的事情：在您的代码中，我将 TreeSet 重命名为 TreeNode。这就是事实，你写的。TreeSet 是 TreeNode 的集合。只需将其声明为指向树的根节点的指针即可。而《枝叶》确实不配成为儿童班。这根本没有意义。只需创建一个成员函数（为了清楚起见，我将其称为 TreeSet TreeNode）

bool TreeNode::isLeaf(){
    return !this.right && !this.left;
}

如果返回 true 则该节点是叶子，否则它是分支（或根）...

当调用 create_empty_set() 时，它应该生成一个叶子，当您添加 T 数据时，叶子应该成为一个分支，并且它的值应该放在左侧或右侧。

一些清晰度。请正确区分 TreeSet 和 TreeNode。然后，要 create_empty_set 首先调用构造函数（ new TreeNode ）（这已经创建了一个空节点），接下来，您需要将其放入树中：遍历 TreeSet （我提醒您，这是一个指向您的树（最顶层的节点）通过节点的所有指针，直到找到所需的空位置并将其放置在您喜欢的位置。例如，如果要向 TreeSet 添加唯一值，请按某种顺序遍历树（例如https://en.wikipedia.org/wiki/Depth-first_search以 3 个顺序之一）并检查数据是否已经存在：如果存在，则停在那里，否则将其添加到正确的节点。