Member 13324136 Ответов: 1

Как создать ссылку из 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. Чтобы добавить элемент, сначала выполните поиск по дереву. Если совпадение найдено, добавьте новый узел в связанный список найденного узла. Если совпадения нет, добавьте новый узел в дерево.

1 Ответов

Рейтинг:
2

Member 13324136

Первый ответ:

Идея состоит в том, что когда я сравниваю 2 коробки, я начну со сравнения значений X, и если они одинаковы, я буду сравнивать значения Y.
Таким образом, я узнаю, больше ли новая коробка, чем предыдущая, или нет.

Второй ответ:
Итак, вы хотите сказать, что вместо свойства Y в классе box я заменю его связанным списком, содержащим значения Y, связанные с X?
Это интересно.

Я попробую это сделать.

Но разве нет способа добавить ссылку из самого дерева в связанный список?
Я бы настоятельно предпочел сохранить класс box как можно более чистым и выполнять большую часть соединений между классами bst и linked list.