Je ne suis pas un étudiant CS, ce ne sont donc pas des devoirs. J'essaie d'apprendre ces choses moi-même, mais je veux m'assurer de ne pas développer de mauvaises habitudes en cours de route.
En gros, j'ai un arbre binaire classique et je veux calculer la hauteur (ou la profondeur) de l'arbre .
Ce que j'entends par hauteur est comme cette image:
La hauteur de cet arbre est de 3.
Voici le python que j'ai trouvé:
def height(node):
#highest one of these two will be returned
i_left = 0
i_right = 0
#if has left, increment and recursively move left
if node.hasleft():
i_left += height(node.left)
i_left += 1
#if has right, increment and recursively move right
if node.hasright():
i_right += height(node.right)
i_right += 1
#return the higher value
if i_right <= i_left:
return i_left
return i_right
Cette solution fonctionne, et je l'aime un peu parce qu'elle est simple et n'a pas beaucoup de des choses abstraites pour travailler votre tête. Cependant, je me demande si c'est ainsi que cela devrait être fait. Y a-t-il un moyen de l'améliorer ou existe-t-il un moyen plus accepté d'implémenter une fonction de hauteur?
3 Réponses :
Votre code n'ajoute que 1 à la hauteur des nœuds gauche ou droit s'il y a des nœuds enfants. Vous devez ajouter 1 pour le nœud actuel même s'il n'y a pas d'enfants. Cela ne devrait donc pas être dans les blocs if .
def height(node):
#if has left, recursively move left
if node.hasleft():
i_left = height(node.left)
else:
i_left = 0
#if has right, recursively move right
if node.hasright():
i_right = height(node.right)
else:
i_right = 0
#return the higher value, plus 1 for the current node.
return 1 + max(i_left, i_right)
Ne vous inquiétez pas, j'aurais dû clarifier, mais j'ai en fait l'intention de partir de 0. Max est cependant une excellente édition. Je suis confus cependant, où est-il incrémenté? Est-ce que je manque quelque chose?
Votre diagramme indique clairement qu'il commence à 1. Mon code s'incrémente dans l'instruction return avec 1 + .
@Barmar: Un "arbre" composé d'exactement un nœud (c'est-à-dire la "racine") a une hauteur de zéro, non?
Pas sur ta photo. Vous avez le numéro 1 à côté du nœud racine.
Peu importe, je l'ai parcouru plusieurs fois et je le vois maintenant. De plus, désolé pour les chiffres, je les ai écrits sur une image aléatoire et je ne pensais pas vraiment. Je ne voulais pas donner l'impression que vous ne savez pas ce que vous faites ou quoi que ce soit.
Si vous voulez qu'il commence à 0 , vous pouvez replacer l'ajout dans les blocs if . Écrivez simplement i_left = 1 + height (node.left) et similaire pour i_right .
Il est normal de définir la hauteur d'un arbre comme le nombre d'arêtes dans le chemin le plus long du nœud racine à une feuille; dans ce cas, un arbre avec un seul nœud (la racine) a une hauteur de zéro car il n'a pas d'arêtes. Le dictionnaire des algorithmes et des structures de données du NIST définit la hauteur de cette façon, par exemple: xlinux.nist. gov / dads / HTML / height.html
Votre algorithme global est la meilleure façon de le faire.
Vous n'avez aucun moyen de savoir quelle branche sera la plus longue, donc la seule façon de le faire serait de vérifier chaque chemin et de trouver le maximum. Votre structure récursive semble assez classique pour une structure arborescente!
L'idée clé de votre algorithme est sensée et correcte; vous devez effectuer des appels récursifs sur les sous-arbres gauche et droit, et ajouter 1.
En supposant que vos attributs node.left et node.right sont Aucun lorsqu'il n'y a pas respectivement de sous-arbre gauche ou droit, la fonction peut être simplifiée en effectuant une seule vérification pour voir si le nœud actuel existe, au lieu de deux vérifications pour voir si chacun de ses enfants existe. Cela signifie que l'entrée est parfois None , auquel cas la valeur de retour correcte est -1 de sorte que la hauteur d'un nœud feuille sera 0.
def height(node):
return -1 if node is None else 1 + max(height(node.left), height(node.right))
Ou si vous êtes fan de one-liners:
def height(node):
if node is None:
return -1
else:
i_left = height(node.left)
i_right = height(node.right)
return 1 + max(i_left, i_right)
Ceci suit la définition habituelle de la hauteur comme le nombre d'arêtes dans un chemin le plus long à partir de la racine, de sorte que la hauteur d'un arbre avec un nœud soit 0. Si vous définissez la hauteur comme nombre de nœuds dans ce chemin, de sorte que la hauteur d'un arbre à un nœud soit 1, puis changez simplement le cas de base en return 0 au lieu de return -1 . p>
Mon préféré est le one-liner.
Votre algorithme est faux. Sur un arbre avec un seul nœud, la hauteur est de 0.
La dernière partie peut être simplement
return max (i_right, i_left)Pouvez-vous partager le reste de la classe / du code?
Vous devez visiter chaque feuille de l'arbre et compter le nombre de niveaux nécessaires pour atteindre chacune d'elles - pas moyen de contourner cela. Ce que vous avez semble globalement OK, sauf pour une petite optimisation.
Désolé, j'aurais dû clarifier. Je suppose que plutôt que la hauteur, ce que je veux vraiment, c'est le niveau maximum. Par conséquent, les niveaux commencent à 0. Je pense que si jamais je veux l'afficher avec une liste 2D, cela facilitera les choses si c'est sous forme de tableau (du moins, je le pense lol)
@ JosephSible-ReinstateMonica Ce n'est pas faux; c'est une définition très normale de la hauteur. Voir par exemple le dictionnaire des algorithmes et des structures de données du NIST: xlinux.nist.gov/dads/HTML /height.html
@ kaya3 Si un arbre à nœud unique est considéré comme étant de hauteur 0, vous devez également considérer l'arbre de l'image comme étant de hauteur 2, mais il est indiqué comme étant de hauteur 3.