Дерево на C#

  • Автор темы kan141290
  • Дата начала
K

kan141290

Гость
#1
Здравствуйте! Помогите пожалуйста с задачей.
Разработать обобщенный класс Tree<T> и сопутствующие классы, описывающие дерево с произвольным числом потомков в каждом узле:
1. Node<T>
o методы:
void Add(Node<T> node); //добавление узла
void Add(T value); //добавление узла по значению
int Remove(Node<T> node) – возвращает количество удаленных элементов;
int Remove(T node) – возвращает количество удаленных элементов;
void Clear(); //Очистка дерева
void SortNodes(CompareDelegate<T>); //Сортировка узлов
o свойства
int ChildCount; //Количество потомков (сделано)
Node<T> Parent; (сделано)
Tree<T> Tree; (сделано)
bool isEmpty; //Проверка, есть ли в дереве элементы
2. Tree<T>: Node<T>
o методы
ForEach(WalkType type, ActionDelegate<Node<T>>);
ForEach(WalkType type, ActionDelegate<T>);
3. WalkType = (PreOrder, InOrder, PostOrder, BreadthFirst) – (методы обхода: сверху вниз, слева направо, снизу вверх, в ширину);
4. TreeException – класс, описывающий исключения, которые могут происходить в ходе работы c деревом.
Эти методы и свойства обязательно должны быть.
Пока сделал следующее:
Структура узла дерева:

Код:
public T value; //значение
public List<Node<T>> children; //список потомков
public Node<T> parent; //родительский элемент
Пока интересует только добавление элемента в дерево (метод Add). С остальным всё понятно.
 
K

kan141290

Гость
#2
Это понятно. Но никак не получается найти узел, к которому присоединить элемент.
Я собирался делать так, чтобы дерево было отсортировано. Чем меньше элемент, тем левее он находится. Проблема в том, что используется обобщённый тип и не удаётся отсортировать элементы. С использованием делегатов ничего не получается.
Пример кода:
C++:
public void Add(Node<T> node, Node<T> tree)
{
List<Node<T>> temp = new List<Node<T>>();
for (int i = 0; i < maxChildCount; i++)
{
if (tree.children[i]!=null)
if (tree.children[i].children.Count == 0)
temp.Add(node.children[i]); 
else
Add(node,tree.children[i]);
}
//После этого список temp должен содержать все крайние элементы.
//Среди них я хотел бы выбрать наиболее близкий по значению и к нему добавить новый, но
//никак не получается сравнить их между собой			
}
 
K

kan141290

Гость
#3
Сначала нужно определить, к какому ноду его присоединить.
 
K

kan141290

Гость
#4
Структура, которую я написал в начале дана по заданию.
Возможно немножко неправильно понял задание.
Я понял так: должно быть дерево с произвольным количеством потомков (>2) и несколькими уровнями. В него можно добавлять элементы и удалять из него. Но по какому принципу добавлять? В двоичных деревьях используется сортировка: меньший элемент добавлялся в левое поддерево, а больший в правое. Здесь я пытаюсь сделать примерно тоже самое.