Неоднозначность с видом сверху двоичного дерева

Question

Что именно представляет собой вид сверху бинарного дерева?

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

Например, это то, что используется для демонстрации вид сверху на geeksforgeeks :

       1
    /     \
   2       3
  /  \    / \
 4    5  6   7

Они go говорят о том, что вид сверху 4 2 1 3 7. Проблема здесь в том, что они оставляют много спекуляций на что не вид сверху. Следовательно, это становится неоднозначным для реализации в коде.

Stackoverflow примеры пока не лучше. Hackerrank * Пример 1015 * еще хуже.

Так что я надеюсь, что кто-то прямо скажет мне, что такое вид сверху, потому что я пытался выяснить в течение 2 дней. Например, каков вид сверху этого дерева:

      1
       \
        14
       /  \
      3    15
     / \
    2   7
       /  \
      4     13
     / \   /
    5   6 10
         /  \
        8    11
         \    \
          9    12

И если я могу быть смелым, чтобы спросить, почему это важно?

Answer 1

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

Нахождение вида сверху представляет собой комбинацию двух обходов, а именно -> Уровень Порядок обхода и Вертикальный обход (есть и другие способы, но этот самый базовый c).

Чтобы визуализировать это, начните рисовать вертикальные линии в дереве, во втором примере 6 вертикальных линий будут нарисованы, покрывая узлы, 1-й -> 2,5 || 2-й -> 1,3,4 || 3-й -> 14,7,6,8 || 4-й -> 15,13,10,9 || 5 -> 11 || 6-й -> 12. Теперь пройдитесь по лидерам этих вертикальных линий, и это даст вид сверху на дерево 2-> 1-> 14-> 15-> 11-> 12.

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

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

Answer 2

Я не знаю, какое у вас техническое или математическое определение, но из ссылок следует, что вид сверху на дерево выглядит следующим образом:

Представьте, что ваше дерево расположено на поверхности стол. Посмотрите с конца стола root вдоль его длины. Предположим, что значения узлов записаны на небольших деревянных блоках, а связи между ними представлены деревянными блоками, достаточно высокими, чтобы скрыть какие-либо узлы за ними, какие узлы вы можете увидеть, когда опускаете голову до высоты стола? В первом примере 5 и 6 неясны, тогда как 2, 3, 4 и 7 простираются наружу влево или вправо так, что они все еще видны.

Однако, как показывает ваш второй пример, это неоднозначно относительно того, расширяются ли узлы 2, 5, 11, 12, 13 достаточно далеко наружу, чтобы быть видимыми.

Кажется, что это плохо определенная концепция, что, вероятно, означает, что о ней не стоит беспокоиться.