Quelle est la différence entre la profondeur et la hauteur des arbres?
C'est une question simple 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. Qui est qui?
6 réponses
J'ai appris que la profondeur et la hauteur sont des propriétés d'un noeud :
Le profondeur d'un nœud est le nombre d'arêtes à partir du nœud de l'arbre du nœud racine.
Un nœud racine aura une profondeur de 0.Le hauteur d'un nœud est le nombre d'arêtes sur la plus long chemin à partir du nœud d'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 largeur) d'un arbre est le nombre de nœuds sur le plus long chemin entre deux nœuds feuilles. 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 traversant du nœud donné à la feuille la plus profonde possible.
Profondeur est calculée à partir de la traversée de la racine au nœud donné.....
Selon Cormen et coll. 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 le plus long Chemin simple descendant 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 de arbre. La profondeur d'un nœud et de la hauteur d'un nœud ne sont pas nécessairement égaux. Voir la Figure B. 6 de la 3e édition de Cormen et al. pour une illustration de ces concepts.
J'ai parfois vu des problèmes demander à compter les nœuds (sommets) au lieu des arêtes, alors demandez des éclaircissements si vous n'êtes pas sûr de compter les nœuds ou les arêtes lors d'un examen ou d'un entretien d'embauche.
Réponse Simple:
Profondeur:
1. Arbre: Nombre de bords/arc à partir du nœud racine à la feuille nœud de l'arbre est appelé comme la Profondeur de l'Arbre.
2. noeud: Nombre d'arêtes / arc du nœud racine à ce nœud est appelé comme la profondeur de ce nœud.
Une autre façon de comprendre ces concepts est la suivante: Profondeur: tracez une ligne horizontale à la position de la racine et traitez cette ligne comme du sol. Donc, la profondeur de la racine est 0, et tous ses enfants sont grandir 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 est la feuille de l'arbre et compte vers le haut.
Je voulais faire ce post parce que je suis un étudiant de premier cycle CS 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 poste ceci pour que tout le monde soit conscient que cet écart existe maintenant et n'entraînera pas de bogues dans tous les programmes! Grâce.
Du livre Opendsa Data Structures & Algos :
Si n1, n2,...,nk est une séquence de nœuds dans l'arbre de telles que n, je est le parent de n, je+1 pour 11 à nk. 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 les descendants de la racine de l'arbre, alors 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 de l' chemin de la racine de L'arbre à M. La hauteur D'un arbre est un de plus que la profondeur du nœud le plus profond de l'arbre. Tous les nœuds de profondeur d le niveau d dans 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 Un de ses enfants. Les nœuds B et D forment ensemble un sous-arbre. Le noeud B A deux enfants: son enfant gauche est l'arbre vide et son bon enfant est D. Les nœuds A, C et E sont les ancêtres des nœuds G. D, E et F composez le niveau 2 de l'arbre; le nœud A est au niveau 0. Les bords de l'Un pour C à E à G former un chemin de longueur 3. Nœuds D, G, H et I sont des feuilles. Les nœuds A, B, C, E et F sont des nœuds internes. Profondeur de I est 3. La hauteur de cet arbre est de 4.
