Calcula la altura de un árbol

Question

Estoy tratando de calcular la altura de un árbol. Estoy doint con el código escrito a continuación.

#include<iostream.h>

struct tree
{
    int data;
    struct tree * left;
    struct tree * right;
};

typedef struct tree tree;

class Tree
{
private:
    int n;
    int data;
    int l,r;
public:
    tree * Root;
    Tree(int x)
    {
        n=x;
        l=0;
        r=0;
        Root=NULL;
    }
    void create();
    int height(tree * Height);

};

void Tree::create()
{
    //Creting the tree structure
} 

int Tree::height(tree * Height)
{
    if(Height->left==NULL && Height->right==NULL)
    {return 0;
    }
    else
    {
        l=height(Height->left);
        r=height(Height->right);

        if (l>r)
        {l=l+1;
        return l;
        }
        else
        {
            r=r+1;
            return r;
        }
    }
}

int main()
{
    Tree A(10);//Initializing 10 node Tree object
    A.create();//Creating a 10 node tree

    cout<<"The height of tree"<<A.height(A.Root);*/

}

Me da resultado corret. Pero en algunos puestos (página buscado en Google) Se sugirió hacer un recorrido en orden posterior y el uso este método altura para calcular la altura. Cualquier razón específica?

Answer 1

Pero no es un recorrido en orden posterior exactamente lo que están haciendo? Suponiendo izquierda y derecha son tanto no nulo, primero hacer height(left), entonces height(right), y luego algún tipo de procesamiento en el nodo actual. Eso es transversal orden posterior en mi opinión.

Pero lo escribiría así:

int Tree::height(tree *node) {
    if (!node) return -1;

    return 1 + max(height(node->left), height(node->right));
}

Editar: dependiendo de cómo se defina la altura del árbol, el caso base (por un árbol vacío) debe ser 0 o -1

.

Answer 2

El código fallará en los árboles de los que al menos uno de los nodos tiene un solo hijo:

// code snippet (space condensed for brevity)
int Tree::height(tree * Height) {
    if(Height->left==NULL && Height->right==NULL) { return 0; }
    else {
        l=height(Height->left);
        r=height(Height->right);
//...

Si el árbol tiene dos nodos (la raíz y ya sea un niño izquierda o derecha) llamando al método de la raíz no cumpla la primera condición (al menos uno de los subárboles no está vacío) y se le llamará de forma recursiva en tanto en niños. Uno de ellos es nula, pero aún así será eliminar la referencia al puntero nulo para realizar la if.

Una solución correcta es la publicada por Hans aquí. En todo caso hay que elegir cuáles son sus invariantes método son: o se permiten llamadas donde el argumento es nulo y manejar que con gracia o de lo contrario se necesita el argumento sea no nulo y la garantía de que no se llama el método con punteros nulos .

El primer caso es más seguro si usted no controla todos los puntos de entrada (el método es público como en su código), ya que no se puede garantizar que el código externo no va a pasar punteros nulos. La segunda solución (cambios en la firma de referencia, y por lo que es un método miembro de la clase tree) podría estar más limpio (o no) si se puede controlar todos los puntos de entrada.

Answer 3

La altura del árbol no cambia con el recorrido. Se mantiene constante. Es la secuencia de los nodos que cambian dependiendo de la travesía.

Answer 4

Definiciones de Wikipedia .

  

Preorder (profundidad-primero):

     

  
1. Visita la raíz.
  
2. Traverse el subárbol izquierdo.
  
3. Traverse el subárbol derecho.
  

     

Inorder (simétrico):

     

  
1. Traverse el subárbol izquierdo.
  
2. Visita la raíz.
  
3. Traverse el subárbol derecho.
  

     

orden posterior:

     

  
1. Traverse el subárbol izquierdo.
  
2. Traverse el subárbol derecho.
  
3. Visita la raíz.
  

"visita" en las definiciones significa "calcular altura de nodo". Que en su caso es cero (izquierda y derecha son nulas) o 1 + altura combinada de los niños.

En su implementación, el orden de recorrido, no importa, que daría los mismos resultados. Realmente no puedo decirle nada más que eso sin un enlace a la fuente afirmando orden posterior es preferir.

Answer 5

Aquí está la respuesta:

int Help :: heightTree (node *nodeptr)
{
    if (!nodeptr)
        return 0;
    else
    {
        return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right));
    }
}