Высота дерева с одним узлом

Question

По словам Википедии,

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

Я не понимаю это - это нулевой или один (или оба)?

Answer 1

Это просто ассигнование, которое вы делаете для рекурсивного описания высоты бинарного дерева. Вы можете рассмотреть дерево, состоящее только узел с высотой 0 или с высотой 1.

Если вы действительно хотите думать об этом как-то, вы можете думать, что

• Это 0, если вы рассматриваете высоту как подсчет края (так что один узел не имеет никакого края, следовательно, 0)
• Это 1, если вы учитываете высоту в качестве подсчета узла (так что единый узел считается 1)

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

В примере, предусмотренном в Википедии:

Это дерево может иметь высоту 4 (узлы) или 3 (кромки). Это зависит, если вы считаете его по краям или узлам.

Answer 2

Одним из преимуществ использования подсчета узла, а не подсчета края, состоит в том, что он отличает пустой корпус (нулевые узлы и уровень узла) из минимального случая (один узел и уровень узла одного). В некоторых случаях пустое дерево не будет значимым, но в других случаях пустая попытка будет идеально законным.

Answer 3

Зависит от Конвенции. Отказ Здесь не «правильный» ответ. Я учил это 1. Но ноль так же правильно.

Answer 4

Я мое мнение, высота одного корневого узла должно быть 0. Это делает практический смысл, поскольку 2 ^ высота также обеспечивает количество узлов на этом уровне.

Answer 5

Предполагая, что вы вычисляете высоту рекурсивной способ в классе узла, я бы сделал это, чтобы вернуть высоту без высоты корня (код Java):

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height() + 1;
    if(right != null)
        rightHeight =+ right.height() + 1;
    return Math.max(leftHeight, rightHeight);
}

Если вы хотите включить высоту корня, то я бы сделал это:

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height();
    if(right != null)
        rightHeight =+ right.height();
    return Math.max(leftHeight, rightHeight) + 1;
}

Answer 6

Зависит от того, как вы хотите интерпретировать высоту дерева. В некоторых приложениях дерево с одним узлом интерпретируется как имеющая высоту, и другие считают его высотой нуля.