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

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

Проблема в вашем базовом случае.

«Высота дерева - это длина пути от корня до самого глубокого узла дерева. Дерево (с корневым доступом), имеющее только узел (корень), имеет высоту ноль» - Википедия

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

Так что, если нет узла, вы возвращаете -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;
    }
}

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

Answer 3

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

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

Answer 4

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

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

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

Answer 6

Для таких как я, которым нравятся решения с одной линией:

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

Answer 7

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

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, поскольку один узел по определению имеетвысота 1.
• Если левые или правые деревья (но не оба!) равны нулю, вернуть высоту ненулевого дерева плюс 1, чтобы учесть добавленную высоту текущего узла.
• Если ни одно дерево не является нулевым, вернуть высоту более высокого поддерева, снова плюс единицу для текущего узла.

Answer 8

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

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

Answer 9

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

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

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

Answer 10

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