Hauteur d'un arbre avec un seul nœud

Question

Selon Wikipedia,

  

La hauteur d'un arbre est la longueur du chemin de la racine à la   le plus profond nœud dans l'arborescence. A (racines) arbre avec un seul noeud (le   root) a une hauteur de zéro (ou un).

Je ne l'obtenir - est-il zéro ou un (ou les deux)

Answer 1

Il juste un assuption que vous faites pour la description récursive de la hauteur d'un arbre binaire. Vous pouvez envisager un arbre composé de seulement un nœud soit avec 0 hauteur ou 1 hauteur.

Si vous voulez vraiment y penser, vous pouvez en quelque sorte penser que

• il est 0 si l'on considère la hauteur comme nombre de fronts (de sorte qu'un seul nœud n'a pas de bord, donc 0)
• il est 1 si l'on considère la hauteur comme nombre de nœuds (de sorte qu'un seul nombre de nœuds que 1)

Ceci est juste pour décrire à quel point la hauteur du plus petit arbre a, puis dans tous les cas, chaque fois que vous ajoutez un nœud descendant vous ajouterez aussi un avantage connexe de sorte qu'il augmentera en conséquence.

Dans l'exemple fourni dans wikipedia:

Cet arbre peut avoir une hauteur (4 nœuds) ou 3 (bords). Cela dépend si vous comptez par les bords ou par des nœuds.

Answer 2

Un avantage d'utiliser un nombre de noeuds au lieu d'un comptage de bord est que ce qui distingue le cas vide (zéro noeuds, et le niveau de nœud) du boîtier minimal (un noeud, et un niveau de noeud d'un seul). Dans certains cas, un arbre vide ne sera pas significatif, mais dans d'autres cas, un essai vide sera tout à fait légitime.

Answer 3

Dépend convention . Il n'y a pas une « bonne » réponse ici. On m'a appris qu'il est 1. Mais nul est tout aussi correct.

Answer 4

Je mon avis, la hauteur d'un nœud racine doit être 0. Il est logique pratique que 2 ^ hauteur vous fournit également le nombre de nœuds à ce niveau.

Answer 5

En supposant que vous calculez la hauteur d'une manière récurrente dans la classe de nœud que je ferais cela pour revenir à la hauteur sans inclure la hauteur de la racine (code Java):

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height() + 1;
    if(right != null)
        rightHeight =+ right.height() + 1;
    return Math.max(leftHeight, rightHeight);
}

si vous voulez inclure la hauteur de la racine, je ferais ceci:

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height();
    if(right != null)
        rightHeight =+ right.height();
    return Math.max(leftHeight, rightHeight) + 1;
}

Answer 6

dépend comment vous voulez interpréter la hauteur d'un arbre. dans certaines applications, un arbre avec un nœud est interprété comme ayant une hauteur d'un et d'autres considèrent comme ayant une hauteur de zéro.