Что должен содержать класс дерева?

Question

Мой класс в настоящее время делает двоичные деревья как часть нашего блока структур данных. Я понимаю, что класс Node должен иметь в своем конструкторе 3 параметра (значение, левый узел, правый узел). В рамках требования мы должны иметь класс Tree. Какова цель древовидного класса? Это для управления всем набором узлов? Он просто содержит функции, необходимые для вставки, удаления и поиска определенных узлов?

Заранее спасибо.

Мой класс Node:

class Node { 
protected int data; 
protected leftNode; 
protected rightNode; 

Node (int data, Node leftNode, Node rightNode){ 
this.data = data; 
this.leftNode = leftNode; 
this.rightNode = rightNode; 
} 
} 

Answer 1

Предполагается, что, как вы подозреваете, немного испорчено. Тип Node, который вы определили, является прекрасным экземпляром двоичного дерева.

Джек упоминает, что вы хотите иметь тип Tree вокруг всего набора узлов, чтобы обеспечить такие операции, как getRoot, вставляет, удаляют и так далее. Это, конечно, не плохая идея, но это отнюдь не требование. Многие из этих операций могут идти по самому Node, и вам необязательно иметь все эти операции; например, есть аргументы как для, так и против наличия операции getRoot. Аргументом против него является то, что если у вас есть алгоритм, который в какой-то момент требует только поддерева, то объект Tree, который держится за корень Node, предотвращает сбор мусора Node s, который вам больше не нужен.

Но в более общем случае, реальный вопрос, который нужно задать здесь заключается в следующем: какие из вещей, которые вы имеете дело в интерфейс, и которые являются реализация? Потому что одно дело, если вы хотите разоблачить бинарные деревья как интерфейс для вызывающих, а другое - если вы хотите предоставить какую-то конечную карту в качестве интерфейса, а двоичное дерево - это просто деталь реализации. В первом случае клиент «знал бы», что дерево будет либо null, либо Node со значением и ветвями, и ему будет разрешено, например, рекурсировать структуру дерева; в последнем случае все, что клиент «знал», это то, что ваш класс поддерживает некоторые формы операций put, get и delete, но не может полагаться на то, что это хранится как дерево поиска. Во многих вариантах последнего случая вы действительно использовали бы тип Tree как передний конец, чтобы скрыть узлы от клиентов. (Например, встроенный класс Java java.util.TreeMap делает это.)

Таким образом, самый короткий ответ, действительно, это зависит.Несколько более длинный ответ зависит от того, что договор находится между реализацией бинарного дерева и его пользователями; какие вещи позволяют вызывающим абонентам допускать использование деревьев, какие детали бинарного дерева являются вещами, которые автор ожидает, чтобы их можно было изменить в будущем и т. д.

Answer 2

"Является ли это для управления весь набор узлов?"

Да.

«Он просто содержит функции, необходимые для вставки, удаления и поиска определенных узлов?»

В принципе, да. По этой причине он должен содержать по крайней мере ссылку на корневой узел.

Answer 3

Цель любой структуры данных - дать вам возможность удерживать коллекции связанных значений и манипулировать ими значимыми способами.

Дерево - это особый вид структуры данных. Это хороший выбор для данных, которые являются иерархическими: с естественными отношениями родитель-потомок. Двоичное дерево имеет, самое большее, два дочерних элемента для каждого родительского узла.

Еще одна особенность деревьев, заслуживающая особого упоминания, заключается в том, что она самоподобна: каждый узел в дереве сам по себе является корнем поддерева. Рекурсия использует этот факт.

Да, это хорошие методы для начала. Возможно, вам стоит взглянуть на интерфейс java.util.Map для других, которые могут быть полезны.

Answer 4

Да, предполагается, что функциональный интерфейс Дерева должен быть установлен на encapsulating всем поведением и алгоритмами, связанными с внутренней структурой.

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

В идеале класс должен быть параметрическим, так что вы будете иметь Tree<T>, и вы будете иметь возможность общие методы, например

T getRoot() 

В основном вы должны проецировать его так, что это позволит вам в

• вставки значения
• удалить значения
• поиск значений,
• посетить все дерево
• независимо

Answer 5

Как я это вижу, Tree класс должен содержать ссылку на корневой узел дерева, а также методы и атрибуты, которые работают на дереве в целом, а против методов, которые принадлежат каждому узлу, например getLeft(), getValue().

Например, я бы определил атрибут size в классе Tree, а методы, которые добавляют или удаляют узлы в дереве (которые также находятся в этом классе), будут нести ответственность за поддержание размера в актуальном состоянии ,