binary tree - recursivo - Encontrar la altura en el árbol de búsqueda binario

imprimir arbol binario java

Question

Me preguntaba si alguien podría ayudarme a volver a trabajar este método para encontrar la altura de un árbol de búsqueda binario. Hasta ahora, mi código se ve así. Sin embargo, la respuesta que obtengo es mayor que la altura real en 1. Pero cuando elimino el +1 de mis declaraciones de devolución, es menor que la altura real en 1. Todavía estoy tratando de envolver mi cabeza con recursión estos BST. Cualquier ayuda sería muy apreciada.

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

// función para encontrar la altura de 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 2

Aquí hay una forma concisa y con suerte correcta de expresarlo:

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

Si el nodo actual es nulo, no hay árbol. Si ambos hijos lo son, hay una sola capa, lo que significa 0 altura. Esto usa la definición de altura (mencionada por Stephen) como número de capas - 1

Answer 3

Aquí hay una solución en C #

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

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

        return Math.Max(left, right);
    }

Answer 4

Aquí hay una solución en Java un poco larga pero funciona ...

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

El problema radica en su caso base.

"La altura de un árbol es la longitud de la ruta desde la raíz hasta el nodo más profundo del árbol. Un árbol (con raíz) con solo un nodo (la raíz) tiene una altura de cero". - Wikipedia

Si no hay ningún nodo, desea devolver -1 no 0. Esto se debe a que está agregando 1 al final.

Entonces, si no hay un nodo, devuelve -1 que cancela el +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 6

En mi opinión, su código se beneficiaría si se simplificara un poco. En lugar de intentar finalizar la recursión cuando un puntero secundario es nulo, solo finalícelo cuando el puntero actual sea ​​nulo. Eso hace que el código sea mucho más sencillo de escribir. En el pseudocódigo se ve algo así:

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

Answer 7

Establecer un tempHeight como una variable estática (inicialmente 0).

estático void findHeight (nodo nodo, cuenta 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 8

Esto no se ha probado, pero es bastante correcto:

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

A menudo, simplificar su código es más fácil que averiguar por qué está desactivado en uno. Este código es fácil de entender: los cuatro casos posibles se manejan claramente de una manera obviamente correcta:

• Si los árboles izquierdo y derecho son nulos, devuelva 1, ya que un solo nodo por definición tiene una altura de 1.
• Si los árboles de la izquierda o de la derecha (¡pero no ambos!) Son nulos, devuelva la altura del árbol no nulo, más 1 para tener en cuenta la altura agregada del nodo actual.
• Si ninguno de los árboles es nulo, devuelva la altura del subárbol más alto, de nuevo más uno para el nodo actual.

Answer 9

La altura de un árbol de búsqueda binario es igual al number of layers - 1 .

Vea el diagrama en Wikipedia

Tu recursión es buena, así que solo resta una en el nivel raíz.

También tenga en cuenta que puede limpiar la función un poco manejando nodos nulos:

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

Answer 10

La definición dada arriba de la altura es incorrecta. Esa es la definición de la profundidad.

"La profundidad de un nodo M en un árbol es la longitud de la ruta desde la raíz del árbol hasta M. La altura de un árbol es una más que la profundidad del nodo más profundo del árbol. Todos los nodos de profundidad d son en el nivel d en el árbol. La raíz es el único nodo en el nivel 0, y su profundidad es 0. "

Cita : "Una introducción práctica a las estructuras de datos y el análisis de algoritmos" Edición 3.2 (Versión de Java) Clifford A. Shaffer Departamento de Ciencias de la Computación Virginia Tech Blacksburg, VA 24061

Answer 11

Para cualquiera que lea esto !!!!

HEIGHT se define como el número de nodos en la ruta más larga desde el nodo raíz a un nodo de hoja. Por lo tanto: un árbol con solo un nodo raíz tiene una altura de 1 y no 0.

El NIVEL de un nodo dado es la distancia desde la raíz más 1. Por lo tanto: la raíz está en el nivel 1, sus nodos secundarios están en el nivel 2 y así sucesivamente.

(Información cortesía de Data Structures: Abstraction and Design Using Java, 2ª edición, de Elliot B. Koffman y Paul AT Wolfgang) - Libro utilizado en el curso sobre estructuras de datos que actualmente tomo en la Columbus State University.

Answer 12

Para gente como yo a la que le gustan las soluciones de una línea:

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

Answer 13

Supongo que esta pregunta podría significar dos cosas diferentes ...

1. Altura es el número de nodos en la rama más larga :

   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. Altura es el número total de nodos en el propio árbol :

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

Answer 14

    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ódigo C #. Incluye estos dos métodos en tu clase BST. Necesitas dos métodos para calcular la altura del árbol. HeightHelper lo calcula, y HeightRecursive lo imprime en main ().

Answer 15

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

Answer 16

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 17

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

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

Answer 18

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

Tome la altura máxima desde el subárbol izquierdo y derecho y agregue 1 al mismo. Esto también maneja el caso base (la altura del Árbol con 1 nodo es 0).

Answer 19

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 20

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