Quelle est la différence entre la profondeur et la hauteur des arbres?

Il s'agit d'une simple question issue de la théorie des algorithmes.
La différence entre eux est que dans un cas, vous comptez le nombre de nœuds et dans un autre nombre d'arêtes sur le chemin le plus court entre la racine et le nœud concret.
Lequel est lequel?

J'ai appris que la profondeur et la hauteur sont des propriétés d'un nœud :

• La profondeur d'un nœud est le nombre d'arêtes du nœud au nœud racine de l'arbre.
  Un nœud racine aura une profondeur de 0.

• La hauteur d'un nœud est le nombre d'arêtes sur le chemin le plus long entre le nœud et une feuille.
  Un nœud feuille aura une hauteur de 0.

Propriétés d'un arbre :

• La hauteur d'un arbre serait la hauteur de son nœud racine,
  ou de manière équivalente, la profondeur de son nœud le plus profond.

• Le diamètre (ou la largeur ) d'un arbre est le nombre de nœuds sur le chemin le plus long entre deux nœuds foliaires. L'arbre ci-dessous a un diamètre de 6 nœuds.

la hauteur et la profondeur d'un arbre sont égales ...

mais la hauteur et la profondeur d'un nœud ne sont pas égales car ...

la hauteur est calculée en passant du nœud donné à la feuille la plus profonde possible.

la profondeur est calculée à partir de la traversée de la racine au nœud donné .....

Selon Cormen et al. Introduction aux algorithmes (annexe B.5.3), la profondeur d'un nœud X dans un arbre T est définie comme la longueur du chemin simple (nombre d'arêtes) du nœud racine de T à X. La hauteur d'un nœud Y est le nombre d'arêtes sur le chemin simple descendant le plus long de Y à une feuille. La hauteur d'un arbre est définie comme la hauteur de son nœud racine.

Notez qu'un chemin simple est un chemin sans sommets répétés.

La hauteur d'un arbre est égale à la profondeur maximale d'un arbre . La profondeur d'un nœud et la hauteur d'un nœud ne sont pas nécessairement égales. Voir la figure B.6 de la 3e édition de Cormen et al. pour une illustration de ces concepts.

J'ai parfois rencontré des problèmes pour demander à quelqu'un de compter les nœuds (sommets) au lieu des bords, alors demandez des éclaircissements si vous n'êtes pas sûr de devoir compter les nœuds ou les bords lors d'un examen ou d'un entretien d'embauche.

Réponse simple:
Profondeur:
1. Arbre : Le nombre d'arêtes / arc du nœud racine au nœud feuille de l'arbre est appelé profondeur de l'arbre.
2. Nœud : le nombre d'arêtes / arc du nœud racine à ce nœud est appelé Profondeur de ce nœud.

Une autre façon de comprendre ces concepts est la suivante: Profondeur: tracez une ligne horizontale à la position racine et traitez cette ligne comme un sol. La profondeur de la racine est donc de 0, et tous ses enfants croissent vers le bas, de sorte que chaque niveau de nœuds a la profondeur actuelle + 1.

Hauteur: Même ligne horizontale mais cette fois la position au sol est des nœuds externes, qui sont la feuille d'arbre et comptent vers le haut.

Je voulais faire ce post parce que je suis un étudiant CS de premier cycle et de plus en plus nous utilisons OpenDSA et d'autres manuels open source. Il semble que d'après la réponse la mieux notée, la façon dont la hauteur et la profondeur sont enseignées a changé d'une génération à l'autre, et je publie ceci pour que tout le monde soit conscient que cet écart existe maintenant et, espérons-le, ne causera aucun bogue programmes! Merci.

Extrait du livre OpenDSA Data Structures & Algos :

Si n ₁ , n ₂ , ..., n _k est une séquence de nœuds dans l'arbre telle que n _i est le parent de n _i +1 pour 1 <= i <k, alors cette séquence est appelée un chemin à partir de n ₁ à n _k . La longueur du chemin est k − 1. S'il y a un chemin du nœud R au nœud M, alors R est un ancêtre de M, et M est un descendant de R. Ainsi, tous les nœuds de l'arbre sont des descendants de la racine de l'arbre, tandis que la racine est l'ancêtre de tous les nœuds. La profondeur d'un nœud M dans l'arbre est la longueur du chemin de la racine de l'arbre à M. La hauteur d'un arbre est supérieure à la profondeur du nœud le plus profond de l'arbre.Tous les nœuds de profondeur d sont au niveau d de l'arbre. La racine est le seul nœud au niveau 0 et sa profondeur est 0.

Figure 7.2.1: Un arbre binaire. Le nœud A est la racine. Les nœuds B et C sont les enfants d'A. Les nœuds B et D forment ensemble un sous-arbre. Le nœud B a deux enfants: son enfant gauche est l'arbre vide et son enfant droit est D. Les nœuds A, C et E sont les ancêtres de G. Les nœuds D, E et F constituent le niveau 2 de l'arbre; le nœud A est au niveau 0. Les bords de A à C à E à G forment un chemin de longueur 3. Les nœuds D, G, H et I sont des feuilles. Les nœuds A, B, C, E et F sont des nœuds internes. La profondeur de I est de 3. La hauteur de cet arbre est de 4.