В чем разница между глубиной и высотой дерева?
Это простой вопрос из теории алгоритмов.
Разница между ними заключается в том, что в одном случае вы подсчитываете количество узлов, а в другом — количество ребер на кратчайшем пути между корнем и конкретным узлом.
Что есть что?
Совет: чтобы избежать путаницы между терминологиями: 1. Рост: представьте себе, что измеряете рост человека, мы делаем это от пальца до головы (от листа к корню). 2. Глубина: представьте себе, измеряя глубину моря, мы делаем это от поверхности земли до дна океана (от корня до листа).
Чтобы добавить к @Yesh отличную аналогию: для некоторого внутреннего узла в середине дерева его глубина — это количество уровней, на которых он находится ниже корневого узла, а высота — это уровень, на котором он находится выше самого нижнего дочернего узла.
Я узнал, что глубина и высота являются свойствами узла :
- Глубина узла является числом ребер от узла к корневому узлу дерева.
Корневой узел будет иметь глубину 0. - Высота узла есть число ребер на длинном пути от узла к листу.
Листовой узел будет иметь высоту 0.
- Высота дерева будет высота его корневого узла,
или , что эквивалентна, глубина самого глубокого узла. - Диаметр (или ширина ) дерева является количеством узлов на самом длинном пути между любыми двумя узлами листьев. Дерево ниже имеет диаметр 6 узлов.
+1 собирался добавить цитату с таким же содержанием отсюда: en.wikipedia.org/wiki/Tree_%28data_structure%29
Не могли бы вы привести источник для вашего утверждения, что диаметр дерева учитывает узлы, а не ребра? Это противоречит обычному определению диаметра графа (см., Например, en.wikipedia.org/wiki/Distance_(graph_theory) ), который запрашивает самый длинный путь.
@j_random_hacker Это вопрос определения, выберите наиболее полезный для вас. Чтобы перейти от количества вершин к числу ребер, просто вычтите 1. Я предпочитаю считать количество вершин, поскольку в результате получается граф с одним узлом шириной 1 и пустой граф шириной 0. mathworld. wolfram.com/GraphDiameter.html
высота и глубина дерева равна .
но высота и глубина узла не равны, потому что .
высота рассчитывается путем перемещения от заданного узла до максимально глубокого листа.
глубина рассчитывается от прохождения от корня до данного узла .
«высота вычисляется путем перемещения от листа к данному узлу», это не правильно, лист должен быть тем, который является самым глубоким среди всех листьев данного узла.
Согласно Cormen et al. Введение в алгоритмы (Приложение B.5.3), глубина узла X в дереве T определяется как длина простого пути (число ребер) от корневого узла T до X. Высота узла Y равна число ребер на самом длинном нисходящем простом пути от Y до листа. Высота дерева определяется как высота его корневого узла.
Обратите внимание, что простой путь — это путь без повторяющихся вершин.
Высота дерева равна максимальной глубине дерева . Глубина узла и высота узла не обязательно равны. См. Рисунок B.6 третьего издания Cormen et al. для иллюстрации этих концепций.
Иногда я сталкивался с проблемами, требующими, чтобы один считал узлы (вершины) вместо ребер, поэтому попросите разъяснений, если вы не уверены, что должны подсчитывать узлы или ребра во время экзамена или собеседования.
Есть ли разница в подсчете узлов и ребер. Кажется, оба дадут одинаковый результат. Поправь меня, если я ошибаюсь.
@jdhao как глубина корня может быть 2? Это либо 0 (если рассматриваются ребра), либо 1 (если учитываются узлы).
@ neowulf33, да, я ужасно неправ. Глубина корневого узла должна быть 0. Я удалю свой комментарий, чтобы не запутать людей.
Простой ответ:
Глубина:
1. Дерево : Количество ребер / дуги от корневого узла до листового узла дерева называется Глубиной дерева.
2. Узел : Количество ребер / дуги от корневого узла до этого узла называется Глубиной этого узла.
Другой способ понять эту концепцию заключается в следующем: Глубина: нарисуйте горизонтальную линию в корневой позиции и рассматривайте эту линию как землю. Таким образом, глубина корня равна 0, и все его дочерние элементы растут вниз, поэтому каждый уровень узлов имеет текущую глубину + 1.
Высота: та же горизонтальная линия, но на этот раз позиция земли — это внешние узлы, которые являются листом дерева и считаются вверх.
Я хотел сделать этот пост, потому что я студент бакалавриата CS и все больше и больше мы используем OpenDSA и другие учебники с открытым исходным кодом. Похоже, что из ответов с самым высоким рейтингом метод преподавания высоты и глубины менялся от поколения к поколению, и я публикую это, чтобы все знали, что это несоответствие существует и, надеюсь, не приведет к ошибкам в любом программа! Спасибо.
Если n 1 , n 2 , . n k — последовательность узлов в дереве, так что n i является родителем n i +1 для 1 От 1 до n к . Длина пути k − 1. Если существует путь от узла R к узлу M, то R является предком M, а M является потомком R. Таким образом, все узлы в дереве являются потомками корня дерева, в то время как корень является предком всех узлов. Глубина узла M в дереве — это длина пути от корня дерева до M. Высота дерева на один больше глубины самого глубокого узла в дереве.Все узлы глубины d находятся на уровне d в дереве. Корень — единственный узел на уровне 0, а его глубина равна 0.
Рисунок 7.2.1: Бинарное дерево. Узел А является корнем. Узлы B и C являются детьми A. Узлы B и D вместе образуют поддерево. Узел B имеет двух дочерних элементов: его левый дочерний элемент — пустое дерево, а его правый дочерний элемент — D. Узлы A, C и E являются предками G. Узлы D, E и F составляют уровень 2 дерева; узел A находится на уровне 0. Ребра от A до C, от E до G образуют путь длиной 3. Узлы D, G, H и I являются листьями. Узлы A, B, C, E и F являются внутренними узлами. Глубина I — 3. Высота этого дерева — 4.
Для чего это стоит, определение по этой ссылке было изменено на: «Глубина узла M в дереве — это длина пути от корня дерева до М. Высота дерева — это глубина самый глубокий узел в дереве. «
Источник