Как создать двоичное дерево с двумя значениями int?

Question

Я пытаюсь создать двоичное дерево, которое содержит два значения типа int и одно строковое значение, отсортированные в лексикографическом выражении, но я не уверен, что делать.Я создал список массивов, который уже отсортирован, но двоичное дерево должно быть основано на ссылках, а не отсортировано, и я думаю о сортировке списка при его создании.Может кто-нибудь помочь с этим?Любая краткая идея будет оценена.

Answer 1

Двоичное дерево - это рекурсивная вещь.Создайте класс с именем BinaryTree (надеюсь, вы находитесь на C ++, .NET или JAVA), который имеет две ссылки на два других BinaryTree (по умолчанию null).Затем создайте рекурсивную функцию вставки.

Я не знаю, чего вы пытаетесь достичь, но при построении двоичного дерева массивы обычно нигде не найти.

Answer 2

Сначала вы должны создать класс для хранения ваших данных и реализовать Comparable или использовать Comparator.

public class Data { // Implement Comparable...
    private String s;
    private int n1;
    private int n2;

    // Implement constructors, getters, setters based on what you need...

    // Implement compareTo (+ equals + hashCode) unless your going with Comparator
}

Затем используйте Collection, который реализует SortedSet для хранения ваших данных, TreeSet является хорошим выбором. Объекты в SortedSet хранятся по ссылке, поэтому, если вы измените набор значений в локальной переменной, он также будет изменен в коллекции.

Редактировать : Если я правильно понял ваш вопрос о списках ссылок, в Java возможно следующее.

List<Data> dataList = // Create list and add data into it.
Data data = dataList.get(4);
data.setS(103); // Modifies S in the local data-object and in dataList because they are reference based.

Answer 3

Похоже, у вас уже есть структура данных для хранения ваших двух значений типа int и строки (поскольку они отсортированы в списке массивов). Вы можете включить эту структуру данных в «узел дерева». Узел обычно имеет указатель ссылки на родительский узел (если он не является корневым узлом) и 2 дочерних узла.

Поскольку вы хотите, чтобы дерево было отсортировано, то на самом деле вам нужна специальная форма двоичного дерева, называемая кучей. Ссылка на страницу википедии Binary Heap ниже содержит алгоритм, чтобы показать, как сортировать двоичную кучу.

http://en.wikipedia.org/wiki/Binary_heap

Вот более общая информация о кучах и деревьях.

http://en.wikipedia.org/wiki/Binary_tree

http://en.wikipedia.org/wiki/Heap_(data_structure)

РЕДАКТИРОВАТЬ: Вам не нужно использовать буквенную древовидную структуру для хранения ваших данных в виде дерева. Вполне приемлемо построить дерево с использованием массива. Вместо использования ссылочных указателей (родительский и 1 или 2 дочерних узла) вы можете вычислить индекс в массиве. Каждый набор детей считается «строкой» в дереве. Корневой элемент находится в нулевой строке. Это двое детей на первом ряду. Дети корня дети на втором ряду, и так далее.

Используя этот шаблон, можно найти дочерние элементы любого узла, используя массив [2 * n + 1] и массив [2 * n + 2], где n - строка родительского узла. Родитель любого узла можно найти с помощью массива [floor ((n-1) / 2)].