Я не могу найти окончательного ответа для этого, я пытаюсь сделать некоторые элементарные доказательства на кучах, но вот что меня немного отбросило:
Является ли пустое дерево действительным? Если да, то какова его высота?
Я бы подумал, что это будет 0.
Какова высота дерева с одним node?
Я бы подумал, что это будет 1, но я видел определения, где это 0 (и если это так, то я не знаю, как объяснить пустое дерево).
Я думаю, вы должны взглянуть на Словарь алгоритмов и структур данных на веб-сайте NIST. Там определение height говорит, что один node - это высота 0.
определение действительного дерева включает пустую структуру. Сайт не упоминает высоту такого дерева, но на основании определения высоты он также должен быть 0.
Высота дерева - это длина пути от корня этого дерева до его самого дальнего node (т.е. листа node, наиболее удаленного от корня).
Дерево с только root node имеет высоту 0, а дерево с нулевыми узлами будет считаться пустым. Пустое дерево имеет высоту -1. Пожалуйста, проверьте этот.
Надеюсь, это поможет.
Я видел, что он использовался в обоих направлениях (считая одиночный node как 0 или 1), но большинство источников определяли бы дерево с корнем только как дерево высоты 0 и не рассматривали бы 0- node дерево действительное.
Если ваше дерево является рекурсивно определенной структурой данных, которая может быть пустой или node с левым и правым поддеревом (например, деревья поиска или ваша куча), то естественным определением является присвоение 0 пустой дерево и 1 + высота верхнего поддерева на непустое дерево.
Если ваше дерево является графиком, тогда естественное определение является самым длинным путем от корня до листа, поэтому дерево с корнем только имеет глубину 0. Обычно вы даже не рассматриваете пустые деревья.
Высота дерева - это длина самого длинного пути к терминалу node в любом из его дочерних элементов.
Википедия говорит высота пустого дерева -1. Я не согласен. Пустым деревом является буквально только дерево, содержащее один терминал node (нулевое или специальное значение, представляющее пустое дерево). Поскольку у node нет детей, длина его самого длинного пути должна быть пустая сумма= 0, а не -1.
Аналогично, непустое дерево имеет два дочерних элемента, поэтому по определению существует хотя бы путь >= 1 к терминалу node.
Мы можем определить наше дерево следующим образом:
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
В соответствии с Wikipedia высота (под) дерева с одним единственным node равна 0. Высота дерево без узлов должно быть -1. Но я думаю, что это зависит от вас, как вы определяете высоту, и ваши доказательства должны работать с любым определением.
actully совершенный defn для высоты дерева d уровень листа d длинного пути от корня плюс 1..accordin 2 это defn fa tree s empty, это не будет havin любого уровня nv cant, считая, что он имеет нуль, уровень coz из корня s нуль..so пустой уровень дерева -1, чем accordin 2 defn его -1 + 1 = 0..so ZERO sd высота пустого дерева... bt n много книг, которые они дали -1 bt нет объяснения s