Skip to main content

Як пов'язані висота і глибина дерева?

Структури данихJunior~1 хв читання
Запропонувати правку

Висота і глибина дерева - це взаємопов'язані, але протилежно спрямовані характеристики.

Глибина (depth)

Вимірюється вниз від кореня. Показує, наскільки далеко конкретний вузол перебуває від кореня.

javascript
глибина(вузол) = кількість ребер від кореня до цього вузла

Висота (height)

Вимірюється вгору від листка. Показує, скільки ребер від вузла до найглибшого листка.

javascript
висота(вузол) = довжина найдовшого шляху від цього вузла до листка

Зв'язок

  • Глибина кореня = 0, висота дерева = висота кореня.
  • Глибина найглибшого вузла = висота дерева.

Приклад

javascript
A / \ B C / \ D E
  • Глибина A = 0, B = 1, D = 2
  • Висота дерева = 2 Максимальна глибина дерева = її висота.

Підсумок

Глибина - шлях вниз до вузла, висота - шлях вгору від вузла. Максимальна глибина = висота всього дерева.

Коротка відповідь

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Запропонувати правку