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

Ответ 1

Я узнал, что глубина и высота - это свойства node:

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

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

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

• высота дерева будет высотой его корня node,
  или, что то же самое, глубины его самого глубокого node.

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

Из Структуры данных OpenDSA и книга Algos:

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

Рисунок 7.2.1: Двоичное дерево. node A - корень. Узлы B и C являются Дети. Узлы B и D вместе образуют поддерево. node B имеет два ребенка: его левый ребенок - это пустое дерево, а его правильный ребенок D. Узлы A, C и E являются предками G. Узлы D, E и F составляют уровень 2 дерева; node A находится на уровне 0. Ребра из A от C до E до G образуют путь длины 3. Узлы D, G, H и я это листья. Узлы A, B, C, E и F являются внутренними узлами. Глубина я - 3. Высота этого дерева равна 4.