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

Question

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

Answer 1

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

• глубина узла - это число ребер от узла до корневого узла дерева.
  Глубина корневого узла равна 0.

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

Если n ₁ , n ₂ , ..., n _k - последовательность узлов в дереве, такая что n _i является родителем n _i + 1 для 1 <= i <k, то эта последовательность называется путем от n <sub>1 до n _k . Длина пути k − 1. Если существует путь от узла R к узлу M, то R является предком M, а M является потомком R. Таким образом, все узлы в дереве потомки корня дерева, в то время как корень является предком все узлы. Глубина узла M в дереве равна длине путь от корня дерева до м. Высота дерева еще один чем глубина самого глубокого узла в дереве. Все узлы глубины d находятся на уровне d в дереве. Корень - единственный узел на уровне 0, и его глубина равна 0.

Рисунок 7.2.1: Бинарное дерево. Узел А является корнем. Узлы B и C являются А дети. Узлы 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 являются внутренними узлами. Глубина из меня 3. Высота этого дерева 4.

Answer 6

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

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