Подтвердить что ты не робот

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

Мне было интересно, сможет ли кто-нибудь помочь мне переработать этот метод, чтобы найти высоту двоичного дерева поиска. Пока что мой код выглядит так. Тем не менее, ответ, который я получаю, больше, чем фактическая высота на 1. Но когда я удаляю +1 из своих операторов return, это меньше фактической высоты на 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;
    }
}
4b9b3361

ОТВЕТЫ

Ответ 1

Проблема заключается в вашем базовом корпусе.

"Высота дерева - это длина пути от корня до самого глубокого node в дереве. Дерево с корнем (root) с только node (корень) имеет высоту нуля." - Wikipedia

Если нет node, вы хотите вернуть -1, а не 0. Это связано с тем, что вы добавляете 1 в конец.

Итак, если нет node, вы возвращаете -1, который отменяет +1.

int findHeight(TreeNode<T> aNode) {
    if (aNode == null) {
        return -1;
    }

    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

Ответ 2

Высота двоичного дерева поиска равна number of layers - 1.

См. диаграмму на http://en.wikipedia.org/wiki/Binary_tree

Ваша рекурсия хороша, поэтому просто вычтите ее на корневом уровне.

Также обратите внимание, что вы можете немного очистить функцию, обрабатывая нулевые узлы:

int findHeight(node) {
  if (node == null) return 0;
  return 1 + max(findHeight(node.left), findHeight(node.right));
}

Ответ 3

int getHeight(Node node) {
 if (node == null) return -1;

 return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

Ответ 4

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

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);

Ответ 5

class Solution{
    public static int getHeight(Node root) {
        int height = -1;

        if (root == null) {
            return height;
        } else {
            height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
        }

        return height;
    }

Ответ 6

Для таких людей, как я, которые любят однострочные решения:

public int getHeight(Node root) {
    return Math.max(root.left != null ? getHeight(root.left) : -1, 
                    root.right != null ? getHeight(root.right) : -1) 
                    + 1;
}

Ответ 7

Здесь кратко и, надеюсь, правильный способ выразить это:

  private int findHeight(TreeNode<T> aNode){
    if(aNode == null || (aNode.left == null && aNode.right == null))
      return 0;
    return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
  }

Если текущий node равен нулю, нет дерева. Если у обоих детей есть один слой, то есть высота 0. Это использует определение высоты (упомянутое Стивеном) как # слоев - 1

Ответ 8

Это не проверено, но довольно очевидно правильно:

private int findHeight(Treenode aNode) {
  if (aNode.left == null && aNode.right == null) {
    return 0; // was 1; apparently a node with no children has a height of 0.
  } else if (aNode.left == null) {
    return 1 + findHeight(aNode.right);
  } else if (aNode.right == null) {
    return 1 + findHeight(aNode.left);
  } else {
    return 1 + max(findHeight(aNode.left), findHeight(aNode.right));
  }
}

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

  • Если оба дерева слева и справа равны нулю, верните 1, поскольку по одному определению node имеет высоту 1.
  • Если либо левое, либо правое дерево (но не оба!) имеют значение null, верните высоту ненулевого дерева, плюс 1, чтобы учесть добавленную высоту текущего node.
  • Если ни одно дерево не имеет значения null, верните высоту более высокого поддерева, а затем плюс для текущего node.

Ответ 9

    public void HeightRecursive()
    {
        Console.WriteLine( HeightHelper(root) ); 
    }

    private int HeightHelper(TreeNode node)
    {
        if (node == null)
        {
            return -1;
        }
        else
        {
            return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode));           
        }
    }

Код С#. Включите эти два метода в свой класс BST. вам нужен два метода расчета высоты дерева. HeightHelper вычислит его, а HeightRecursive напечатает его в main().

Ответ 10

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

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

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

Ответ 11

public int height(){

    if(this.root== null) return 0;

    int leftDepth = nodeDepth(this.root.left, 1);
    int rightDepth = nodeDepth(this.root.right, 1);

    int height = leftDepth > rightDepth? leftDepth: rightDepth;

    return height;
}


private int nodeDepth(Node node, int startValue){

    int nodeDepth = 0;

    if(node.left == null && node.right == null) return startValue;
    else{
        startValue++;
        if(node.left!= null){
            nodeDepth = nodeDepth(node.left, startValue);
        }

        if(node.right!= null){
            nodeDepth = nodeDepth(node.right, startValue);
        }
    }

    return nodeDepth;
}

Ответ 12

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

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

Ответ 13

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

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

    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; }

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

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

Ответ 14

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;
}

Ответ 15

Вот решение в С#

    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);
    }

Ответ 16

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

static void findHeight (Node node, int count) {

    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);

}

Ответ 17

Вот решение в 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);
    }

Ответ 18

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

Ответ 19

//функция для нахождения высоты 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;
}

Ответ 20

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

HEIGHT определяется как количество узлов в самом длинном пути от корня node до листа node. Поэтому: дерево с корнем node имеет высоту 1, а не 0.

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

(Информация любезно предоставлена ​​структурами данных: абстракция и дизайн с использованием Java, второе издание, Эллиот Б. Коффман и Пол А. Т. Вольфганг). Книга, используемая в курсе "Структуры данных", которую я сейчас беру в Университет штата Колумб.

Ответ 21

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

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

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

Следующее - мое рубиновое решение. Большинство людей забыли о высоте пустого дерева или дерева одного узла в своей реализации.

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

Ответ 22

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));
}