Quelle est la définition de la hauteur d'un arbre?

Je n'arrive pas à trouver une réponse définitive pour cela, je suis en train de faire quelques élémentaire des preuves sur des tas, mais voici ce qu'en me jetant un peu:

Est un arbre vide est-il valide? Si oui, quelle est sa hauteur?
Je pense que ce serait 0.

Quelle est la hauteur d'un arbre avec un seul nœud?
Je pense que ce serait 1 mais j'ai vu des définitions où elle est de 0 (et si c'est le cas, alors je ne sais pas comment faire pour le compte d'un arbre vide).

OriginalL'auteur Brad | 2010-02-05

  1. 9

    Je pense que vous devriez jeter un coup d'oeil à la Dictionnaire des Algorithmes et Structures de Données au NIST site web. Il y définition de la hauteur dit un seul nœud est de hauteur 0.

    La définition d'un arbre valide comporte une structure vide. Le site ne mentionne pas la hauteur d'un tel arbre, mais en se fondant sur la définition de la hauteur, il convient également de 0.

    Merci, c'est agréable d'avoir une source fiable pour citer à cet effet (ne pense pas qu'un professeur ou d'un examen par les pairs doit considérer Wikipédia une source acceptable). Leurs définitions semblent un peu contradictoires, cependant, ils définissent un arbre comme "vide (pas de nœuds), ou une racine et zéro ou plusieurs sous-arbres". Mais leur définition de la hauteur est définie dans les termes du nœud racine.
    Je suis d'accord. Je pense que vous devriez certainement lui un email (de sorte que vous pouvez obtenir cité sur cette page pour mettre en place cette distinction). Mais compte tenu de la définition implique que le nombre maximum d'arêtes à partir de la racine à une feuille, nous avons à dire qu'un arbre vide a la hauteur de 0.
    Je pense que, à défaut d'une source de référence à citer, je vais dire qu'un arbre vide est un indéfini hauteur. De cette façon, le nombre de nœuds d'un arbre binaire complet de hauteur h est comprise entre 2^h et 2^(h+1)-1. Et si vous retournez-la à résoudre pour h basé sur n, en fin de prise de log2(0)=undefined lorsque l'arbre est vide. Il en fait une belle définition et une jolie preuve au moins.
    La hauteur d'un arbre vide n'est pas défini. La hauteur d'un arbre est la hauteur de la note racine de l'arbre (ce qui est un plus le maximum de la hauteur de ses enfants, ou zéro si elle n'a pas d'enfants). Un arbre vide n'a pas de nœud racine, et donc ne peut pas être dit d'avoir une hauteur.
    En fait le nouveau définition dit que la hauteur d'un arbre vide n'est pas défini.

    OriginalL'auteur nlucaroni

  2. 17

    Hauteur d'un arbre est la longueur du chemin de la racine de l'arbre à sa plus éloigné nœud (i.e. nœud feuille la plus éloignée de la racine).

    Un arbre avec un seul nœud racine a hauteur de 0 et un arbre avec des nœuds de zéro serait considéré comme vide. Un arbre vide a la hauteur de -1. Veuillez vérifier cette.

    J'espère que cette aide.

    Je crois que c'est une question de convention utilisée dans la mise en œuvre. Comme toutes positives valeurs de hauteur et la hauteur de la valeur zéro sont représentées lorsque vous avez un ou plusieurs nœuds dans l'arbre, vous devriez avoir quelque chose pour représenter un arbre vide. Si la convention a -1. Vous pouvez avoir comme n'importe quelle autre valeur négative. C'est une question de mise en œuvre la réelle abstraction de la structure de données - l'arbre ne couvre pas ces choses.
    La convention de l'arbre vide ayant la hauteur -1 a en fait un usage pratique dans AVL arbres qu'il en simplifie le calcul du solde facteur et quand pour faire pivoter les enfants. Cette œuvre montre dans la pratique: users.cis.fiu.edu/~weiss/dsaajava/code/structures de données/...

    OriginalL'auteur Arnkrishn

  3. 5

    J'ai vu qu'il est utilisé dans les deux sens (en comptant un seul nœud 0 ou 1), mais la majorité des sources de définir une racine uniquement de l'arbre comme un arbre de taille 0, et de ne plus considérer un 0-nœud de l'arbre valide.

    OriginalL'auteur Max Shawabkeh

  4. 2

    Si votre arbre est définie de manière récursive structure de données qui peut être soit vide ou d'un nœud avec un gauche et à droite de la sous-arborescence (par exemple les arbres de recherche, ou votre tas), puis la définition naturelle consiste à attribuer à 0 pour l'arbre vide et 1 + la hauteur de la plus grande sous-arbre d'un arbre non vide.

    Si votre arbre est un graphe puis la définition naturelle est le plus long chemin de la racine à une feuille, donc une racine arbre seul a profondeur 0. Normalement, vous ne serait même pas envisager de vide arbres dans ce cas.

    Je tiens à souligner que (a) vous avez évidemment raison, et (b) le NIST et de nombreuses autres personnes ne voient pas les choses (y)notre chemin. Je crois que ce malheureux état de fait est principalement dû à l'CLR, qui souffre de la peur "des nuls".

    OriginalL'auteur starblue

  5. 1

    La hauteur d'un arbre est la longueur du plus long chemin d'accès à un terminal de nœud dans l'un de ses enfants.

    Wikipédia dit la hauteur d'un arbre vide est -1. Je suis en désaccord. Un arbre vide est littéralement juste un arbre contenant un nœud terminal (un nul ou une valeur spéciale, ce qui représente un arbre vide). Depuis que le nœud n'a pas d'enfants, la longueur du plus long chemin doit être le vide somme = 0, pas de -1.

    De même, un non-vide de l'arbre a deux enfants, donc par définition, il n'est au moins un chemin d'accès >= 1 à un nœud terminal.

    Nous pouvons définir notre arbre comme suit:

    type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec height = function
    | Node(left, x, right) -> 1 + max (height left) (height right)
    | Nil -> 0
    "Un arbre vide est littéralement juste un arbre contenant un nœud terminal." Nope, même vide que ça...
    +1, en raison de Caml

    OriginalL'auteur Juliet

  6. 0

    Selon Wikipedia, la hauteur d'un (sous-)arbre avec un seul nœud est de 0. La hauteur d'un arbre à n nœuds seraient -1. Mais je pense que c'est à vous, comment vous définissez la hauteur et de vos épreuves de travailler avec définition.

    OriginalL'auteur MartinStettner

  7. -3

    actully un parfait défn pour la hauteur de l'arbre est d au niveau de la feuille de d plus long chemin de la racine plus 1..accordin 2 ce défn f un arbre s vide,il l'habitude de b havin n'importe quel niveau n v cant envisager il y avait zéro,coz niveau de la racine de zéro ..donc arbre vide niveau -1,que accordin 2 défn son -1+1=0..donc ZERO s d hauteur de l'arbre vide...bt n de nombreux livre elles ont donné -1 bt aucune explication s donné

    OriginalL'auteur angad