Поиск высоты в бинарном дереве поиска

Question

Мне было интересно, может ли кто-нибудь помочь мне переработать этот метод, чтобы найти высоту бинарного дерева поиска.Пока мой код выглядит так.Тем не менее, ответ, который я получаю, больше, чем фактическая высота на 1. Но когда я удаляю +1 из моих операторов возврата, это меньше, чем фактическая высота на 1. Я все еще пытаюсь обернуть голову рекурсиейэти BST.Любая помощь будет высоко ценится.

public int findHeight(){
    if(this.isEmpty()){
        return 0;
    }
    else{
        TreeNode<T> node = root;
        return findHeight(node);
    }
}
private int findHeight(TreeNode<T> aNode){
    int heightLeft = 0;
    int heightRight = 0;
    if(aNode.left!=null)
        heightLeft = findHeight(aNode.left);
    if(aNode.right!=null)
        heightRight = findHeight(aNode.right);
    if(heightLeft > heightRight){
        return heightLeft+1;
    }
    else{
        return heightRight+1;
    }
}

Answer 1

введите описание изображения здесь

Согласно «Введение в алгоритмы» Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л. Ривеста и Клиффорда Стейна, следующее определениевысоты дерева:

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

Ниже приведено мое решение для ruby.Большинство людей забыли о высоте пустого дерева или дерева одного узла в своей реализации.

def height(node, current_height)
  return current_height if node.nil? || (node.left.nil? && node.right.nil?)
  return [height(node.left, current_height + 1), height(node.right, current_height + 1)].max if node.left && node.right
  return height(node.left, current_height + 1) if node.left
  return height(node.right, current_height + 1)
end

Answer 2

Для всех, кто читает это !!!!

ВЫСОТА определяется как количество узлов в самом длинном пути от корневого узла до конечного узла.Поэтому: дерево только с корневым узлом имеет высоту 1, а не 0.

УРОВЕНЬ данного узла - это расстояние от корня плюс 1. Поэтому: корень находится на уровне 1, его дочерний элементузлы находятся на уровне 2 и т. д.

(информация предоставлена ​​структурами данных: абстракция и проектирование с использованием Java, 2-е издание, Эллиот Б. Коффман и Пол А. Ф. Вольфганг) - книга, используемая в курсе по структурам данныхв настоящее время принимает в Колумбийском государственном университете.