Je suis un peu confus entre la logique de calcul de la hauteur de l'arbre binaire.
Je pense, le second est correct, car il donne la réponse correcte pour le code ci-dessous: - P>
Tree t4 = new Tree(4);
Tree t2 = new Tree(2);
Tree t1 = new Tree(1);
Tree t3 = new Tree(3);
Tree t5 = new Tree(5);
t4.left = t2;
t4.right = t5;
t2.left = t1;
t2.right = t3;
// Prints "Height : 2" for Code 2
// Prints "Height : 3" for Code 1
System.out.println("Height : " + findHeight(t4));
mise à jour: p>
Tout, j'ai un doute fondamental quant à ce qui est exactement la hauteur de l'arbre? P>
ou p>
3 Réponses :
Votre exemple est de hauteur 3 (T4 est une racine, T4.Left est T2, T2.Left est T1) si votre compréhension de la hauteur est (1 nœud racine est de hauteur 1, nœud racine avec un enfant ou deux est de hauteur 2, etc) donc code 1 est juste :))
Le second est vrai, mais pour de nombreuses situations, les développeurs vont avec le premier lors de la mise en œuvre de la hauteur. Alors la réponse est 3 :))
La différence réside dans si un arbre vide a la hauteur -1 ou 0.
Selon Wikipedia :
La hauteur d'un nœud est la longueur du chemin vers le bas le plus long vers une feuille de ce nœud. La hauteur de la racine est la hauteur de l'arbre. La profondeur d'un nœud est la longueur du chemin de sa racine (c'est-à-dire son chemin racine).
et
Le nœud racine a une profondeur zéro, les nœuds de feuilles ont une hauteur zéro et un arbre avec seulement un seul noeud (par conséquent, une racine et une feuille) a une profondeur et une hauteur zéro. Classiquement, un arbre vide (arbre sans nœuds, si tel est autorisé) a une profondeur et une hauteur -1.
Vous pourriez avoir raison - le second est d'accord sur cela.
Bien sûr, ce sont toutes des définitions - je ne serais pas trop étonnée pour voir une définition qui accepte la première version.
La longueur d'un chemin est le nombre de bords, donc je dirais 2.
Mais, selon le code 1, lequel de nombreux utilisateurs ont dit (y compris Jon Skeet) Stackoverflow.com/q/5763854/2546848 , cela aboutirait à une réponse incorrecte pour mon code ci-dessus .. N'est-ce pas?
Ces types de définitions peuvent varier beaucoup - même des livres en tant que CLRS et Knuth ont parfois des définitions différentes. En outre, Jon peut également être (rarement) également inexacte - c'est une définition la plupart des gens ont probablement oublié (j'ai définitivement fait).
Les deux approches sont-elles correctes à leur usage? Dépend du scénario?
Ne les mélangez pas, vous devriez avoir la plupart du temps bon - une formule pourrait être la plus laid avec une définition, bien sûr. Par exemple, le nombre maximum de nœuds est 2 ^ n-1 par la définition wiki, 2 ^ (n-1) - 1 par l'autre version.
Code 0 comptera la racine comme la hauteur 1 (la racine doit être 0). Ce qui signifie que tous les arbres suivants seront un trop nombreux
Mais il n'y a pas de question ..
C'est une définition complètement arbitraire. Voulez-vous que la hauteur soit le nombre de bords ou le nombre de nœuds? Tant que vous êtes cohérent, tout va finir.
Stackoverflow.com/Questtions/2209777/...
Merci Ziyao ... mon doute est clarifié par vos liens fournis.