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

Question

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

Answer 1

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

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

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

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

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

• То диаметр (или ширина) дерева это количество узлы на самом длинном пути между любыми двумя листовыми узлами. Дерево ниже имеет диаметр 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

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

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

Answer 6

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

Из Операционные структуры данных и книга ALGOS:

Если Н.₁, Н.₂..., н_k. это последовательность узлов в дереве такая, что n_я Родитель N_я+1 для 1 <= я₁ к Н._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, и я есть листья. Узлы A, B, C, E и F являются внутренними узлами. Глубина I - 3. Высота этого дерева 4.