Как создать ссылку из bst в связанный список?
Всем привет!
Я хочу создать bst, который содержит объект (поле) с 2 параметрами (x и y), когда x-это параметр, на котором основан bst, а y-параметр, связанный с конкретным листом в дереве через связанный список.
Например, если у меня есть 3 объекта: 1 - (x=4, y=6), 2- (x=4, y=7), 3- (x=5, y=8).
Дерево будет содержать только значения x (4 и 5), а лист 4 будет иметь ссылку на связанный список с узлами 6 и 7. Лист со значением 5 будет иметь ссылку на другой связанный список только с одним узлом-8.
У меня есть свойства x и y в классе box, и дерево получает весь box как универсальный объект.
Я построил дерево и классы связанных списков, но не могу придумать способ соединить их оба. Идеи?
class Box : IComparable<Box> { public double X { get; set; } public double Y { get; set; } public int CompareTo(Box otherBox) { int result = this.X.CompareTo(otherBox.X); if (result == 0) { result = this.Y.CompareTo(otherBox.Y); } return result; } } class Tree<T> where T : IComparable<T> { Node root = null; public void Add(T newData) { if (root == null)//empty tree { root = new Node<T>(newData); return; } Node<T> tmp = root; Node<T> tmpParent = null; while (tmp != null) { tmpParent = tmp; if (newData.CompareTo(tmp.data) < 0) //go left { tmp = tmp.left; } else { tmp = tmp.right; } } Node<T> newNode = new Node<T>(newData); if (newData.CompareTo(tmpParent.data) < 0) //left child { tmpParent.left = newNode; } else { tmpParent.right = newNode; } } private class Node<T> { public T data; public Node<T> left; public Node<T> right; public Node(T data) { this.data = data; left = right = null; } } } public class MyLinkedList<T> { Node<T> start; Node<T> end; public void AddToStart(T dataToAdd) { Node<T> temp = new Node<T>(dataToAdd); //case if the list is empty if (start == null) { start = temp; } //case if list has only 1 item else if (end == null) { end = start; start = temp; start.next = end; end.prev = start; } //case when list has 2 or more items else { start.prev = temp; temp.next = start; start = temp; } } public void AddLast(T dataToAdd) { Node<T> temp = new Node<T>(dataToAdd); //case if the list is empty if (start == null) { start = temp; } //case if list has only 1 item else if (end == null) { start.next = temp; end = start.next; end.prev = start; } //case when list has 2 or more items else { end.next = temp; temp.prev = end; end = temp; } } private class Node<T> { public T data; public Node<T> next; public Node<T> prev; public Node(T newData) { data = newData; next = null; prev = null; } } } }
Что я уже пробовал:
Я знаю, что мне нужно добавить ссылку в класс дерева, но не знаю, как разделить значения x и y.
Graeme_Grant
Если вы используете только свойство X для вычисления позиции, то почему класс Box тестирует свойство Y в методе CompareTo?
George Swan
Я не совсем понимаю, чего вы добиваетесь. Основываясь на своем лучшем предположении, я бы предложил следующее. Сделайте свой связанный список общедоступным свойством класса Box. Чтобы добавить элемент, сначала выполните поиск по дереву. Если совпадение найдено, добавьте новый узел в связанный список найденного узла. Если совпадения нет, добавьте новый узел в дерево.