Calculer la hauteur d'un arbre

Question

Je suis en train de calculer la hauteur d'un arbre. Je doint avec le code écrit ci-dessous.

#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);*/

}

Il me donne le résultat Corret. Mais dans certains messages (page googlé) Il a été suggéré de faire un traversal Postorder et l'utilisation cette méthode de hauteur pour calculer la hauteur. Une raison particulière?

Answer 1

Mais est pas un traversal postorder précisément ce que vous faites? Si l'on suppose gauche et à droite sont à la fois non nulle, vous devez d'abord faire height(left), puis height(right), puis un certain traitement dans le nœud actuel. C'est postorder traversal selon moi.

Mais je voudrais écrire comme ceci:

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

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

Edit: selon la façon dont vous définissez doit être 0 ou -1 la hauteur des arbres, le cas de base (pour un arbre vide)

.

Answer 2

Le code échouera dans les arbres où au moins l'un des noeuds a un seul enfant:

// 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 l'arbre a deux nœuds (la racine et soit un enfant à gauche ou à droite) appelant la méthode à la racine ne remplissent pas la première condition (au moins l'un des sous-arbres est non vide) et il appellera récursive sur les enfants. L'un d'eux est nul, mais il déréférence le pointeur NULL pour effectuer la if.

Une solution correcte est celle affichée par Hans ici. En tout cas, vous devez choisir ce que vos invariants de méthode sont: soit vous permettent des appels où l'argument est nul et vous manipulez que grâce ou bien vous avez besoin que l'argument soit non nul et la garantie que vous ne l'appelez pas la méthode avec des pointeurs nuls .

Le premier cas est plus sûr si vous ne contrôlez pas tous les points d'entrée (la méthode est publique comme dans votre code) puisque vous ne pouvez pas garantir que le code externe ne passera pas des pointeurs nuls. La deuxième solution (changement de la signature à la référence, et ce qui en fait une méthode membre de la classe tree) pourrait être plus propre (ou non) si vous pouvez contrôler tous les points d'entrée.

Answer 3

La hauteur de l'arbre ne change pas avec le traversal. Il reste constant. Il est la séquence des noeuds qui changent en fonction de la traversée.

Answer 4

Définitions de wikipedia .

  

Preorder (-première profondeur):

     

  
1. Consultez la racine.
  
2. Traverse le sous-arbre gauche.
  
3. Traverse le sous-arbre droit.
  

     

Inorder (symétrique):

     

  
1. Traverse le sous-arbre gauche.
  
2. Consultez la racine.
  
3. Traverse le sous-arbre droit.
  

     

Postorder:

     

  
1. Traverse le sous-arbre gauche.
  
2. Traverse le sous-arbre droit.
  
3. Consultez la racine.
  

« séjour » dans les définitions signifie « calculer la hauteur de noeud ». Ce qui dans votre cas est soit nul (à la fois à gauche et à droite sont nulles) ou 1 + hauteur combinée des enfants.

Dans votre implémentation, l'ordre traversal n'a pas d'importance, cela donnerait les mêmes résultats. Cant vraiment vous dire quoi que ce soit plus que cela sans un lien vers la source indiquant postorder est à préférer.

Answer 5

Voici la réponse:

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