Encontrando altura en Árbol de búsqueda binaria

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 recibo es más grande que la altura real en 1. Pero cuando elimino el +1 de mis declaraciones de devolución, es menos que la altura real en 1. Todavía estoy tratando de ajustar mi cabeza a la recursión con 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

El problema radica en su funda 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 (rooteado) con solo un nodo (la raíz) tiene una altura de cero." - Wikipedia

Si no hay un nodo, quiere devolver -1 no 0. Esto se debe a que está agregando 1 al final.

Entonces, si no hay un nodo, devuelve -1 que anula 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 2

Aquí está una manera concisa y es de esperar 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 están, hay una sola capa, lo que significa 0 altura. Esto usa la definición de altura (mencionada por Stephen) como # de capas - 1

Answer 3

IMO, su código se beneficiaría de ser simplificado 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 lote más fácil de escribir. En pseudo-código que se ve algo como esto:

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

Answer 4

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

Ver el diagrama de la http://en.wikipedia.org/wiki/Binary_tree

su recursividad es bueno, por lo que sólo resta uno en el nivel raíz.

También tenga en cuenta, se puede limpiar la función un poco por el manejo de los nodos nulos:

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

Answer 5

Esto no se ha probado, pero bastante obvio correcta:

 
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 la simplificación de su código es más fácil que averiguar por qué está apagado por uno. Este código es fácil de entender: los cuatro casos posibles están claramente manejados de una manera obviamente correcta:

• Si tanto los árboles izquierdo y derecho son nulos, devuelve 1, ya que un solo nodo, por definición, tiene una altura de 1
• Si los árboles izquierdo o derecho (pero no ambos) son nulos, devuelve 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 6

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, & HeightRecursive imprímelo en main().

Answer 7

La definición dada anteriormente 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 del camino desde la raíz del árbol para M. La altura de un árbol es uno más que la profundidad del nodo más profundo en el Todos los nodos de profundidad d están 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 la Estructura de Datos y Análisis Algoritmo" Edition 3.2 (Java Version) Clifford A. Shaffer Departamento de Informática Virginia Tech Blacksburg, VA 24061

Answer 8

Para cualquier persona otra cosa que dice esto !!!!

ALTURA se define como la cantidad de nodos en la ruta más larga desde el nodo raíz a un nodo 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 son en el nivel 2 y así sucesivamente.

(Información cortesía de Data Structures: Abstraction and Design Using Java, 2nd Edition, por Elliot B. Koffman & Paul A. Wolfgang) - Libro utilizado en el curso de Data Structures que estoy cursando actualmente en Columbus State University.

Answer 9

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

1. La 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 la número total de nodos en el árbol sí mismo:

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

Answer 10

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 11

Aquí es 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 12

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

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

Answer 13

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

estática findHeight vacío (nodo Nodo, 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); 

} 

Answer 14

Aquí es una solución en Java un poco largo, 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 15

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 16

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

Answer 17

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

Answer 18

Para personas como yo a quienes les 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 19

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