Хобрук: Ваш путь к мастерству в программировании

Каков диаметр дерева, у которого нет хотя бы двух листьев?

Диаметр дерева T является наибольшей из следующих величин:

  1. диаметр левого поддерева T
  2. диаметр правого поддерева T
  3. самый длинный путь между листьями, который проходит через корень T (это можно вычислить по высоте поддеревьев T)

Источник: https://www2.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html

Однако он не говорит, каков диаметр дерева, у которого нет хотя бы двух листьев, например, дерева с одним корнем, или 1 -> 2? Это 0, неопределенное значение, бесконечность или отрицательная бесконечность?

algorithm data-structures binary-tree
27.03.2021

  • Насколько я знаю, это должно быть 0 для корневого дерева и 1 для 1->2 27.03.2021
  • @AbhinavMathur Можете ли вы привести источник? То, что вы говорите, не может быть получено из определения, которое я опубликовал. 27.03.2021
  • У меня нет формального источника, просто использую 3-й пункт определения 27.03.2021
  • Самый длинный простой путь (для деревьев можно предположить, что это простые пути) — это число от 0 до n-1 для дерева или графа с n узлами. Таким образом, исходя из описания, которое вы даете, дерево с одним или двумя узлами явно имеет самый длинный путь между листьями 0. Источник не нужен, его право в определении, как уже упоминалось. 28.03.2021

Ответы:


1

Лучшее определение диаметра — это просто длина самого длинного пути. Корневое дерево имеет диаметр 0, а путь по двум вершинам имеет диаметр 1. Приведенные правила излишне сложны, но это потому, что они также позволяют вычислить диаметр. Кроме того, обратите внимание, что в теоретико-графовом смысле, если в корне отсутствуют все или все его дочерние элементы, кроме одного, то он сам является листом, и поэтому вы можете видеть, что третье предложение фактически покрывает проблемные случаи.

27.03.2021
  • Корень, в котором отсутствует один дочерний элемент, ни в коем случае не является листом. 27.03.2021
  • @AbhijitSarkar За исключением. В теории графов, откуда берется идея диаметра, деревья не имеют привилегированного корня. Любой узел только с одной ссылкой на остальную часть дерева является листом. Это немного отличается от принятого в компьютерных науках, потому что мы используем деревья по-другому. 27.03.2021
  • Я вижу, что лист — это вершина без дочерних элементов, что не подтверждает ваше утверждение, равно как и дерево только с одной вершиной (следовательно, и корень, и лист) не имеет глубины и высоты. ноль. Корень, в котором отсутствует один потомок, по-прежнему имеет другое поддерево и, следовательно, не является листом ни по одному из приведенных выше определений. Если на этой странице есть что-то еще, пожалуйста, цитируйте вместо публикации общей ссылки. 27.03.2021
  • @AbhijitSarkar Я установил ссылку для автоматической прокрутки к соответствующему предложению, но, возможно, ваш браузер не поддерживает это. Я просто процитирую. Точно так же внешняя вершина (или внешняя вершина, терминальная вершина или лист) — это вершина степени 1. Это определение также должно включать вершины степени 0, но это особый случай, применимый только к одному дереву. Кроме того, вы немного упускаете суть. Определение в вопросе плохое, вы можете заставить его работать, растянув значение листа из версии CS до версии теории графов, а фундаментальным является диаметр = длина самого длинного пути. 27.03.2021
  • Я вижу это утверждение сейчас, но, учитывая противоречивые утверждения, сделанные на этой странице, я не совсем убежден. Как вы указали, они удобно опустили случай дерева с одним узлом, а лист - это вершина без дочерних элементов противоречит внешняя вершина (или внешняя вершина, конечная вершина или лист) вершина степени 1. Я проголосовал за то, что вы попытались, и теперь собираюсь заглянуть в какой-нибудь учебник. 27.03.2021
  • @AbhijitSarkar, если у корня есть только один дочерний элемент, его также можно считать листом, если края ненаправлены. 27.03.2021

    • 2

    Основываясь на данном определении, он должен быть равен 0 как в случае, когда в дереве есть один или два узла. Путь имеет длину от 0 до n-1 для дерева из n узлов. Диаметр бесконечности или отрицательной бесконечности, а также неопределенность не имеют логического смысла, и 3-е определение всегда дает числовой ответ. Возможно, требуется лучшее определение, но на самом деле это зависит от задачи, зачем определять диаметр в первую очередь. Очевидно, что это рекурсивное определение, поэтому в любом случае ему потребуется базовый случай. Левое или правое поддерево в конечном итоге будет деревом с 1 или 2 узлами. Но логически определение в том виде, в котором оно построено, кажется неточным и не особенно полезным, за исключением правильно сбалансированных бинарных деревьев с нечетным числом узлов, узлы которых содержат только два листа.

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

    28.03.2021
    Новые материалы
    Расистский и сексистский робот, обученный в Интернете
    Его ИИ основан на предвзятых данных, которые создают предрассудки. Он словно переходит из одного эпизода в другой из серии Черное зеркало , а вместо этого представляет собой хронику..
    Управление состоянием в микрофронтендах
    Стратегии бесперебойного сотрудничества Микро-фронтенды — это быстро растущая тенденция в сфере фронтенда, гарантирующая, что удовольствие не ограничивается исключительно бэкэнд-системами..
    Декларативное и функциональное программирование в стиле LINQ с использованием JavaScript с использованием каррирования и генератора ...
    LINQ - одна из лучших функций C #, которая обеспечивает элегантный способ написания кода декларативного и функционального стиля, который легко читать и понимать. Благодаря таким функциям ES6,..
    Структуры данных в C ++ - Часть 1
    Реализация общих структур данных в C ++ C ++ - это расширение языка программирования C, которое поддерживает создание классов, поэтому оно известно как C с классами . Он используется для..
    Как я опубликовал свое первое приложение в App Store в 13 лет
    Как все началось Все началось три года назад летом после моего четвертого класса в начальной школе. Для меня, четвертого класса, лето кажется бесконечным, пока оно не закончится, и мой отец..
    Что в лицо
    Очерк о возвращении физиогномики и о том, почему мы должны это приветствовать. История начинается со странной науки. Р. Тора Бьорнсдоттир, Николас О. Рул. Видимость социального класса по..
    Почему шаблоны проектирования и почему нет?
    Сложность — мать всех проблем в программировании. Программное обеспечение должно быть разработано с точки зрения того, кто его поддерживает, а не того, кто его пишет, потому что программное..