Quelle est la différence entre la profondeur et la hauteur de l'arbre?

Question

Ceci est une simple question de la théorie des algorithmes.
La différence entre eux est que dans un cas on compte nombre de noeuds et dans d'autres nombre d'arêtes sur le chemin le plus court entre la racine et le noeud de béton.
Ce qui est qui?

Answer 1

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

• 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.

• hauteur d'un nœud est le nombre d'arêtes sur la chemin le plus long à partir du nœud à une feuille.
  Un nœud feuille aura un hauteur de 0.

Propriétés de arbre :

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

• diamètre (ou largeur ) d'un arbre étant le nombre de nœuds sur le plus long chemin entre deux noeuds de feuille . L'arbre ci-dessous présente un diamètre de 6 noeuds.

Answer 2

hauteur et la profondeur d'un arbre est égal ...

mais la hauteur et la profondeur d'un nœud est pas égal parce que ...

la hauteur est calculée en traversant depuis le noeud donné vers le plus profond possible feuille.

profondeur est calculée à partir de la traversée de la racine au noeud donné .....

Answer 3

Selon Cormen et al. Introduction aux algorithmes (annexe B.5.3), la profondeur d'un noeud X à un arbre T est défini comme étant la longueur du trajet simple (nombre d'arêtes) à partir du noeud racine de T à X. La hauteur d'un noeud Y est le nombre d'arêtes sur la plus long simple chemin vers le bas de Y à une feuille. La hauteur d'un arbre est défini comme étant la hauteur de son noeud de racine.

Notez qu'un simple chemin est un chemin sans sommets de répétition.

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

Je l'ai parfois vu des problèmes demander un à compter noeuds (sommets) au lieu des bords, donc demander des éclaircissements si vous n'êtes pas sûr que vous devez compter les nœuds ou les bords lors d'un examen ou une entrevue d'emploi.

Answer 4

Réponse simple:
Profondeur:      
1. Arbre : Nombre d'arêtes / arc à partir du nœud racine au nœud feuille de l'arbre est appelé comme la profondeur de l'arbre.     
2. Node . Nombre d'arêtes / arc dans le noeud racine de ce noeud est appelé lorsque la profondeur de ce noeud

Answer 5

Une autre façon de comprendre les concept est comme suit: Profondeur: Tracer une ligne horizontale à la position de la racine et de traiter cette ligne comme la terre. Ainsi, la profondeur de la racine est 0, et tous ses enfants sont croître vers le bas de sorte que chaque niveau de noeuds a la profondeur actuelle + 1.

Hauteur:. Ligne horizontale même, mais cette fois la position du sol est des noeuds externes, qui est la feuille d'arbre et compter vers le haut

Answer 6

Je voulais faire ce poste parce que je suis un étudiant de premier cycle étudiant CS et de plus en plus nous utilisons OpenDSA et d'autres manuels open source. Il semble que la partie supérieure de réponse nominale qui est enseigné la hauteur et la profondeur de manière a changé d'une génération à l'autre, et je poste ce que tout le monde est au courant que cet écart existe maintenant et nous espérons ne causera pas des bugs dans une programmes! Merci.

De la OpenDSA Structures de données et Algos livre :

  

Si n ₁ , n ₂ , ..., n _k est une suite de noeuds dans l'arborescence telle   que n _i est le parent de n _i 1 pour 1 <= i 1 à n _k . La longueur du trajet est k-1.   S'il existe un chemin à partir du noeud R vers le noeud M, alors R est un ancêtre de   M, et M est un descendant de R. Ainsi, tous les nœuds de l'arborescence sont   descendants de la racine de l'arbre, tandis que la racine est l'ancêtre de   tous les nœuds. La profondeur d'un noeud dans l'arborescence M est la longueur de la   chemin de la racine de l'arbre à M. La hauteur d'un arbre est une plus   que la profondeur du plus profond nœud dans l'arborescence. Tous les noeuds de la profondeur d   sont au niveau d dans l'arbre. La racine est le seul noeud au niveau 0, et   sa profondeur est de 0.

     

     

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