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

C'est une simple question d'algorithmes de la théorie.

La différence entre eux est que, dans un cas vous compter le nombre de nœuds et dans d'autres nombre d'arêtes sur le plus court chemin entre la racine et le nœud de béton.

Qui est qui?

  • Astuce: pour éviter la confusion entre les terminologies: 1. Hauteur: Imaginez la mesure de la taille d'une personne, nous le faisons à partir des pieds à la tête (de la feuille à la racine). 2. Profondeur: Imaginez la mesure de la profondeur de la mer, nous le faisons à partir de la surface de la terre à l'océan de lit (de la racine à la feuille).
  • C'est une grande analogie.
InformationsquelleAutor Gabriel Ščerbák | 2010-04-08
  1. 542

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

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

    • La hauteur d'un nœud est le nombre d'arêtes sur le plus long chemin à partir du nœud d'une feuille.
      Un nœud feuille auront 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 du plus profond de son nœud.

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

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

    • +1 était sur le point d'ajouter citation avec le même contenu à partir d'ici: en.wikipedia.org/wiki/Tree_%28data_structure%29
    • hmm, je pensais que la terminologie n'est pas ambigu, cependant merci pour le lien.
    • est que les moyens height == profondeur max
    • Oui, le hauteur de l'arbre est toujours égale à la profondeur de la plus profonde nœud.
    • Très bien expliqué concernant la hauteur et la profondeur des arbres Binaires.
    • "Notez que la profondeur n'a pas de sens pour un arbre" - Pourquoi n'est-ce pas la profondeur utile?
    • Pourriez-vous nous citer une source pour votre réclamation que le diamètre d'un arbre en compte des nœuds au lieu de bords? Cela entre en conflit avec la définition usuelle du diamètre d'un graphe (voir par exemple en.wikipedia.org/wiki/Distance_(graph_theory)) qui demande le plus long chemin.
    • C'est une question de définition, de choisir celui qui est le plus utile pour vous. Pour obtenir à partir du nombre de sommets pour le nombre d'arêtes, juste soustraire 1. Je préfère compter le nombre de sommets, que ce résultats dans un graphique avec un seul nœud ayant la largeur 1, et un graphique vide ayant la largeur de 0. mathworld.wolfram.com/GraphDiameter.html

    InformationsquelleAutor Daniel A.A. Pelsmaeker
  2. 35

    la hauteur et la profondeur de l'arbre est égale...

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

    la hauteur est calculée par la traversée du nœud donné le plus possible de la feuille.

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

    • "la hauteur est calculée par la traversée de la feuille vers le nœud" il n'est pas correct , la feuille doit être celle qui est la plus profonde parmi toutes les feuilles du nœud donné.
    InformationsquelleAutor Praveen_Shukla
  3. 14

    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) à partir du nœud racine de T à X. La hauteur d'un nœud Y est le nombre d'arêtes sur le plus longue à la baisse simple chemin de Y à une feuille. La hauteur d'un arbre est définie comme la hauteur de son nœud racine.

    Note qu'un simple chemin est un chemin sans répéter les sommets.

    La hauteur d'un arbre est égale à la profondeur maximale d'un 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 3ème Édition du Cormen et coll. pour une illustration de ces concepts.

    J'ai parfois vu des problèmes demandant de compter les nœuds (sommets) au lieu de bords, donc à demander des précisions si vous n'êtes pas sûr que vous devriez compter les noeuds ou les bords de cours d'un examen ou d'un entretien d'embauche.

    • Il est tout de differnce dans le comptage des nœuds et des arêtes. Semble être les deux donnent le même résultat. Corrigez-moi si je me trompe.
    • comment la profondeur de la racine de 2? C'est soit 0 (si les bords sont pris en compte) ou 1 (si les nœuds sont considérés).
    • oui, je suis terriblement mal. La profondeur du nœud racine doit être de 0. Je vais supprimer mon commentaire afin de ne pas embrouiller les gens.
    InformationsquelleAutor glacier
  4. 3

    Réponse Simple:

    Profondeur:

    1. Arbre: Nombre d'arêtes/arc à partir du nœud racine à la feuille nœud de l'arbre est appelé comme la Profondeur de l'Arbre.

    2. Nœud: Nombre d'arêtes/arc à partir du nœud racine à ce nœud est appelé comme la Profondeur de ce nœud.

    InformationsquelleAutor Akshay Sahu
  5. 0

    Une autre façon de comprendre le concept est le suivant:
    Profondeur: Tracez une ligne horizontale à la racine de la position et de traiter cette ligne de sol. De sorte que la profondeur de la racine est 0, et tous ses enfants grandissent à la baisse de sorte que chaque niveau de nœuds de la profondeur courante + 1.

    Hauteur: Même ligne horizontale, mais cette fois, le sol est en position externe des noeuds, ce qui est la feuille de l'arbre et de compter vers le haut.

    InformationsquelleAutor Wilson Zhang
  6. 0

    Je voulais faire ce post car je suis le premier cycle CS d'étudiants et de plus en plus, nous utilisons OpenDSA et d'autres open source manuels scolaires. Il semble qu'à partir de la top rated réponse que la façon dont la hauteur et la profondeur de l'enseignement a changé d'une génération à la suivante, et je vais poster ce si tout le monde est conscient que cet écart existe maintenant et espérons-le, ne cause pas de bugs dans les programmes! Merci.

    De la OpenDSA Structures de Données & Algos livre:

    Si n1, n2,...,nk est une séquence de nœuds dans l'arbre de telles
    que ni est le parent de ni+1 pour 1<=i<k, alors cette séquence
    est appelé un chemin de n1 nk. La longueur du chemin est k−1.
    Si il y a un chemin d'accès du nœud R 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 de l'arbre est la longueur de la
    chemin d'accès à partir de la racine de l'arbre à M. La hauteur d'un arbre est un plus
    que la profondeur de la plus profonde nœud dans 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 de 0.

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

    Figure 7.2.1: Un arbre binaire. Un nœud est la racine. Les nœuds B et C sont
    Un de ses enfants. Les nœuds B et D, ensemble, forment un sous-arbre. Le nœud B a
    deux enfants: Sa gauche l'enfant est l'arbre vide et de son droit à l'enfant est
    D. les Nœuds A, C, et E sont les ancêtres de G. Nœuds D, E et F
    faire jusqu'au niveau 2 de l'arbre; Un nœud est au niveau 0. Les bords de l'Un
    de C à E de 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 je est 3. La hauteur de cet arbre est de 4.

    InformationsquelleAutor ashtree