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

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

int height(Node* root) {
        if(root==NULL) return -1;
        return max(height(root->left),height(root->right))+1;
}

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

Answer 2

Указанное выше определение высоты неверно. Это определение глубины.

"Глубина узла M в дереве - это длина пути от корня дерева до M . Высота дерева на один больше, чем глубина самого глубокого узла в дереве. Все узлы глубины d находятся на уровне d в дереве. Корень - единственный узел на уровне 0, а его глубина равна 0. «

Цитирование : "Практическое введение в структуры данных и анализ алгоритмов" Выпуск 3.2 (версия Java) Клиффорд А. Шаффер Кафедра компьютерных наук Virginia Tech Блэксберг, Вирджиния 24061

Answer 3

// функция для определения высоты BST

int height(Node* root) {
    if(root == NULL){
        return -1;
    }

    int sum=0;
    int rheight = height(root->right);
    int lheight = height(root->left);

    if(lheight>rheight){
        sum = lheight +1;
    }
    if(rheight > lheight){
        sum = rheight + 1;
    }

    return sum;
}

Answer 4

Вот решение на Java немного длинное, но работает ..

public static int getHeight (Node root){
    int lheight = 0, rheight = 0;
    if(root==null) {
        return 0;
    }
    else {
        if(root.left != null) {
            lheight = 1 + getHeight(root.left);
            System.out.println("lheight" + " " + lheight);
        }
        if (root.right != null) {
            rheight = 1+ getHeight(root.right);
            System.out.println("rheight" + " " + rheight);
        }
        if(root != null && root.left == null && root.right == null) {
            lheight += 1; 
            rheight += 1;
        }

    }
    return Math.max(lheight, rheight);
    }

Answer 5

 int getHeight(Node* root)
 {
   if(root == NULL) return -1;
   else             return max(getHeight(root->left), getHeight(root->right)) + 1;
 }

Answer 6

Установить tempHeight в качестве статической переменной (изначально 0).

static void findHeight (узел узла, число int) {

    if (node == null) {
        return;
    }
    if ((node.right == null) && (node.left == null)) {
        if (tempHeight < count) {
            tempHeight = count;

        }

    }

    findHeight(node.left, ++count);
    count--; //reduce the height while traversing to a different branch
    findHeight(node.right, ++count);

}

Answer 7

Полагаю, этот вопрос может означать две разные вещи ...

1. Высота - это количество узлов в самой длинной ветви : -

   int calcHeight(node* root){ if(root==NULL) return 0; int l=calcHeight(root->left); int r=calcHeight(root->right); if(l>r) return l+1; else return r+1; }

2. Высота - это общее количество узлов в самом дереве :

   int calcSize(node* root){ if(root==NULL) return 0; return(calcSize(root->left)+1+calcSize(root->right)); }

Answer 8

Вот решение на C #

    private static int heightOfTree(Node root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = 1 + heightOfTree(root.left);
        int right = 1 + heightOfTree(root.right);

        return Math.Max(left, right);
    }

Answer 9

public int getHeight(Node node)
{
    if(node == null)
        return 0;

    int left_val = getHeight(node.left);
    int right_val = getHeight(node.right);
    if(left_val > right_val)
        return left_val+1;
    else
        return right_val+1;
}

Answer 10

int maxDepth(BinaryTreeNode root) {
    if(root == null || (root.left == null && root.right == null)) {
       return 0;
    }

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}