Какое определение для высоты дерева?

Question

Кажется, я не могу найти однозначного ответа на этот вопрос, я пытаюсь сделать некоторые элементарные доказательства на кучах, но вот что меня немного сбивает:

Допустимо ли пустое дерево? Если да, то какова его высота?
Я думаю, это будет 0.

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

Answer 1

Высота дерева - это длина пути от корня этого дерева до его самого дальнего узла (то есть листового узла, самого дальнего от корня).

Дерево с единственным корневым узлом имеет высоту 0, а дерево с нулевыми узлами считается пустым. Пустое дерево имеет высоту -1. Пожалуйста, отметьте это .

Надеюсь, это поможет.

Answer 2

Думаю, вам стоит взглянуть на Словарь алгоритмов и структур данных на веб-сайте NIST. Там определение высоты говорит, что один узел имеет высоту 0.

Определение действительного дерева содержит пустую структуру. На сайте не упоминается высота такого дерева, но исходя из определения высоты, оно также должно быть 0.

Answer 3

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

Answer 4

Высота дерева - это длина самого длинного пути к конечному узлу в любом из его дочерних элементов.

Википедия говорит: высота пустого дерева равна -1 . Я не согласен. Пустое дерево - это буквально просто дерево, содержащее один конечный узел (нулевое или специальное значение, представляющее пустое дерево). Поскольку у узла нет дочерних элементов, длина его самого длинного пути должна быть пустой суммой = 0, а не -1. ​​

Аналогично, непустое дерево имеет двух дочерних элементов, поэтому по определению существует не менее путь> = 1 к конечному узлу.

Мы можем определить наше дерево следующим образом:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec height = function
    | Node(left, x, right) -> 1 + max (height left) (height right)
    | Nil -> 0

Answer 5

Если ваше дерево является рекурсивно определенной структурой данных, которая может быть либо пустой, либо узлом с левым и правым поддеревом (например, деревьями поиска или вашей кучей), то естественным определением является присвоение 0 пустому дереву и 1 + высота самого высокого поддерева непустого дерева.

Если ваше дерево является графом, то естественное определение - это самый длинный путь от корня до листа, поэтому дерево только для корня имеет глубину 0. Обычно в этом случае пустые деревья даже не рассматриваются.

Answer 6

фактически идеальный defn для высоты дерева - это d уровень листа d самого длинного пути от корня плюс 1.. корня s ноль .. так что пустой уровень дерева равен -1, чем согласно 2 определяет его -1 + 1 = 0..так НОЛЬ sd высота пустого дерева ... bt много книг, которые они дали -1 bt без объяснения с учетом

Answer 7

Согласно Википедии высота (под) дерева с одним узлом равна 0. Высота дерева без узлов будет равна -1. Но я думаю, что вам решать, как вы определяете высоту, и ваши доказательства должны работать с любым определением.