Дерево ADT - является ли узел предком/потомком самого себя?

Я начну с того, что в Stack Overflow есть еще один вопрос по этому поводу, но я не смог найти реального ответа на него, потому что все ответы, связанные с этим вопросом, отличались друг от друга, и это действительно смутило меня больше, чем я уже есть. . Мой вопрос заключается в том, что я говорю об абстрактном типе данных - дереве (обычное, а не двоичное дерево и в программировании на Java, на всякий случай, если это имеет значение).

1) является ли узел дерева предком/потомком самого себя?

Скажем, я искал определение предка, и в результате получились такие варианты, как:

«узел, достижимый повторным переходом от дочернего к родительскому»

«предок узла: он сам, его родитель или предок самого его родителя»

«узел U является предком узла V, только если: U = V или U является предком родителя V»

2) существует ли универсальное определение для "предка" или оба определения (включая сам узел или нет) верны?

3) если сам узел не считается предком самого себя, равно ли определение глубины узла количеству его предков?


java data-structures tree abstract-data-type
person The BigBoss    schedule 09.09.2015    source источник
comment
Кажется, вы уже ответили на свой первый вопрос, поэтому я не уверен, что вы ищете. Просто дополнительная проверка? Ваш ответ на (1) убедительно свидетельствует о том, что (2) в основном верно, хотя, вероятно, в мире найдется кто-то, кто не согласен (независимо от того, о чем мы говорим), так что вряд ли он будет полностью универсальным (но либо Кстати, обычно рекомендуется подтверждать определения вещей, если вам дали задание или что-то еще, чтобы убедиться, что вы находитесь на той же странице). (3) верно (плюс-минус один). В целом, это не кажется особенно ответным вопросом.   -  person Bernhard Barker    schedule 09.09.2015
comment
да, я ищу подтверждение, потому что я немного запутался в этом, поэтому я пытаюсь расширить свои знания и понять, хорошо ли я понял, и, кстати, спасибо за ответ :)   -  person The BigBoss    schedule 09.09.2015

Ответы (1)


arrow_upward
2
arrow_downward

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

Учитывая узел в дереве (т. е. узел контекста), спецификация определяет оси, т. е. набор узлов относительно узла контекста:

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

Поскольку иногда полезно работать с потомками или предками, включая узел контекста, он дополнительно определяет:

  • ось потомок или себя содержит узел контекста и потомков узла контекста

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

В этой модели есть ответ на ваш вопрос 1. Другие модели могут отличаться. Q2: нельзя ответить. Q3: просто зависит от того, как определяется глубина.

person wero    schedule 09.09.2015
comment
хорошо объясненный ответ, спасибо, просмотр всей проблемы как вопроса, связанного с моделью, определенно решил мои недоумения :) - person The BigBoss; 09.09.2015