В чем разница между глубиной и высотой дерева?

Это простой вопрос из теории алгоритмов.
Разница между ними заключается в том, что в одном случае вы подсчитываете количество узлов, а в другом - количество ребер на кратчайшем пути между корнем и конкретным узлом.
Что есть что?

Я узнал, что глубина и высота являются свойствами узла :

• Глубина узла является числом ребер от узла к корневому узлу дерева.
  Корневой узел будет иметь глубину 0.

• Высота узла есть число ребер на длинном пути от узла к листу.
  Листовой узел будет иметь высоту 0.

Свойства дерева :

• Высота дерева будет высота его корневого узла,
  или , что эквивалентна, глубина самого глубокого узла.

• Диаметр (или ширина ) дерева является количеством узлов на самом длинном пути между любыми двумя узлами листьев. Дерево ниже имеет диаметр 6 узлов.

высота и глубина дерева равна ...

но высота и глубина узла не равны, потому что ...

высота рассчитывается путем перемещения от заданного узла до максимально глубокого листа.

глубина рассчитывается от прохождения от корня до данного узла .....

Согласно Cormen et al. Введение в алгоритмы (Приложение B.5.3), глубина узла X в дереве T определяется как длина простого пути (число ребер) от корневого узла T до X. Высота узла Y равна число ребер на самом длинном нисходящем простом пути от Y до листа. Высота дерева определяется как высота его корневого узла.

Обратите внимание, что простой путь - это путь без повторяющихся вершин.

Высота дерева равна максимальной глубине дерева . Глубина узла и высота узла не обязательно равны. См. Рисунок B.6 третьего издания Cormen et al. для иллюстрации этих концепций.

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

Простой ответ:
Глубина:
1. Дерево : Количество ребер / дуги от корневого узла до листового узла дерева называется Глубиной дерева.
2. Узел : Количество ребер / дуги от корневого узла до этого узла называется Глубиной этого узла.

Другой способ понять эту концепцию заключается в следующем: Глубина: нарисуйте горизонтальную линию в корневой позиции и рассматривайте эту линию как землю. Таким образом, глубина корня равна 0, и все его дочерние элементы растут вниз, поэтому каждый уровень узлов имеет текущую глубину + 1.

Высота: та же горизонтальная линия, но на этот раз позиция земли - это внешние узлы, которые являются листом дерева и считаются вверх.

Я хотел сделать этот пост, потому что я студент бакалавриата CS и все больше и больше мы используем OpenDSA и другие учебники с открытым исходным кодом. Похоже, что из ответов с самым высоким рейтингом метод преподавания высоты и глубины менялся от поколения к поколению, и я публикую это, чтобы все знали, что это несоответствие существует и, надеюсь, не приведет к ошибкам в любом программа! Спасибо.

Из книги «Структуры данных и алгоритмы OpenDSA» :

Если n ₁ , n ₂ , ..., n _k - последовательность узлов в дереве, так что n _i является родителем n _i +1 для 1 <= i <k, то эта последовательность называется путем от n _{От 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.