Я должен написать шаблон для набора деревьев.Размер листа равен 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
Заранее спасибо, Келвин