C ++ Treeset реализация с шаблонами

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

6

Решение

Ваш вопрос очень обширный. Есть несколько вещей, на которые я хотел бы обратить внимание.
Во-первых, поскольку узлы дерева являются классом шаблона, для сортировки дерева вы должны иметь возможность сравнивать и сортировать тип. Вы можете сравнивать целые, вы можете сравнивать строки (вы должны определить функцию для их сравнения или использовать strcmp), но вы не можете реально сравнивать логические значения, например. Если, возможно, вы не хотите ставить ложных слева и истинно вправо. Также, когда вы создаете дерево «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 (), он должен создать лист, когда вы
добавить данные Т лист должен стать ветвью и его значение должно быть указано
слева или справа.

Некоторая ясность. Пожалуйста, сделайте правильное различие между TreeSet и TreeNode. Затем для create_empty_set сначала вызовите конструктор (новый TreeNode) (это уже создает пустой узел), а затем вам нужно поместить его в дерево: запустить через TreeSet (который, я напомню, указатель, указывающий на корень ваше дерево, самый верхний узел) через все указатели узлов, пока вы не найдете нужное пустое место и разместите его там, где вам нравится. Например, если вы добавляете уникальное значение в TreeSet, обходите дерево в некотором порядке (https://en.wikipedia.org/wiki/Depth-first_search например, в одном из 3-х заказов) и проверьте, существуют ли уже данные: если это так, остановитесь на этом, иначе добавьте их в соответствующий узел.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]