Лучшая практика: знание дочерним узлом своего родителя

Question

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

Моя текущая проблема довольно проста и понятна.У меня есть дерево информации, и я хотел получить «полное имя» листового узла (в этом случае это будет имя каждого узла в дереве до листового узла, разделенного точкой).Я могу сделать это, либо добавив метод «getFullName» к конечным узлам, который пересекает дерево до корня и добавляет имя каждого родителя и возвращает конечный результат, но для этого требуется, чтобы конечные узлы знали тип класса своего родителя (leafи не-лист не тот же класс).Или я могу добавить вспомогательную функцию где-нибудь еще, которая делает в основном то же самое, но знает о различных типах классов.

Я попытался искать, но вопрос слишком широк, чтобы получить какие-либо полезные хиты в Google.

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

Answer 1

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

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

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

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

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

Теперь, если вы создавали древовидную структуру данных общего назначения, такую ​​как TreeNode в Java, вы, вероятно, создали бы интерфейс и позволили бы людям реализовывать вещи по своему усмотрению, обеспечивая подходящую общую реализацию (DefaultMutableTreeNode), которая имеет все ссылки. - родитель, ребенок и родной брат.

Answer 2

Я не вижу проблем с тем, чтобы класс дочернего узла "знал" о своих родителях. Родители могут реализовать интерфейс, если вы беспокоитесь о расширяемости.

Другая альтернатива состоит в том, чтобы родительские классы обновляли поле «имя» всех дочерних узлов в их поддереве ... может иметь смысл, если вы создаете большое дерево, а затем просто запрашиваете его (поиск в постоянном времени). Опять же, интерфейсы могут помочь, если вы беспокоитесь о слишком сильной связи.

Answer 3

По крайней мере, каждый узел должен знать, что он родительский. Листовые и не конечные узлы имеют разные классы, но это означает, что каждый родительский класс принадлежит к одному и тому же классу. Используйте это, чтобы пройти вверх по дереву и построить имя (в обратном порядке) по мере продвижения.

Answer 4

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

string getFullName() {
    myFullName = myParent.getFullName() + myLocalName;
    return myFullName;
}

(это псевдокод; я предполагаю, что если myParent - ноль, то myParent.getFullName() - пустая строка, вы можете изменить все в соответствии с вашим конкретным языком)

Рекурсия заканчивается, когда нет родителя. Единственное, что должен знать узел - это его собственное имя и кто его родитель.