Кажется, я не могу найти однозначного ответа на этот вопрос, я пытаюсь сделать некоторые элементарные доказательства в кучах, но вот что меня немного сбивает с толку:
Действительно ли пустое дерево? Если да, то какова его высота?
Я думаю, что это будет 0.
Какова высота дерева с одним узлом?
Я думаю, что это будет 1, но я видел определения, где она равна 0 (и если это так, то я не знать, как учитывать пустое дерево).
Я думаю, вам следует взглянуть на Словарь алгоритмов и структур данных на сайте НИСТ. В определении высоты говорится, что один узел имеет высоту 0.
определение допустимого дерева включает пустую структуру. На сайте не указана высота такого дерева, но исходя из определения высоты, она тоже должна быть равна 0.
Высота дерева — это длина пути от корня этого дерева до его самого дальнего узла (т. е. самого дальнего от корня листового узла).
Дерево с одним корневым узлом имеет высоту 0, а дерево с нулевыми узлами будет считаться пустым. Пустое дерево имеет высоту -1. Пожалуйста, проверьте это.
Надеюсь, это поможет.
Я видел, как он использовался в обоих случаях (считая один узел как 0 или 1), но большинство источников определяли бы дерево только для корня как дерево высоты 0 и не считали бы дерево с 0 узлами действительным.
Если ваше дерево представляет собой рекурсивно определенную структуру данных, которая может быть либо пустой, либо узлом с левым и правым поддеревом (например, деревьями поиска или вашей кучей), то естественным определением является присвоение 0 пустому дереву и 1 + высоту самого высокого поддерева в непустое дерево.
Если ваше дерево представляет собой граф, то естественным определением является самый длинный путь от корня к листу, поэтому дерево, состоящее только из корней, имеет глубину 0. Обычно в этом случае вы даже не рассматриваете пустые деревья.
Высота дерева — это длина самого длинного пути к конечному узлу в любом из его дочерних элементов.
Википедия говорит, что высота пустого дерева равна -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
Согласно Википедии, высота (под)дерева с одним единственным узел равен 0. Высота дерева без узлов будет равна -1. Но я думаю, что вам решать, как вы определяете высоту, и ваши доказательства должны работать с любым определением.
на самом деле идеальным определением высоты дерева является d уровень листа d самого длинного пути от корня плюс 1..согласно 2 это определение дерева пусто, оно не имеет никакого уровня и не может считать, что оно имеет нулевой уровень, потому что уровень корня s ноль .. таким образом, уровень пустого дерева равен -1, чем в соответствии с определением 2, его -1 + 1 = 0 .. поэтому НОЛЬ sd высота пустого дерева ... но много книг, которые они дали -1, но никаких объяснений не дано
