Arbre binaire représenté à l'aide du tableau

Considérons le tableau suivant, qui est censé avoir représenté un arbre binaire:

[1, 2, 5, 6, -1, 8, 11]

Donné que l'indice de la valeur -1 indique que l'élément racine, j'ai questions ci-dessous:

a) Comment est-il représenté?

Devrions-nous suivre ci-dessous les formules (source à partir de ce lien) à la figure de l'arbre?
Trois formules simples vous permettent d'aller de l'indice de la mère à l'index de ses enfants, et vice versa:

* if index(parent) = N, index(left child) = 2*N+1
* if index(parent) = N, index(right child) = 2*N+2
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation)

Si nous utilisons les formules ci-dessus, alors l'index(racine) = 3, index(à gauche de l'enfant) = 7, ce qui n'existe pas.

b) Est-il important de savoir si c'est un arbre binaire ou pas?

OriginalL'auteur Sanjeev Kulkarni N | 2011-11-24

  1. 8

    Donné un tableau, vous pourriez penser à un certain nombre de façons comment pourrait-tableau représentent un arbre binaire. Donc, il n'y a aucun moyen de savoir, vous avoir à aller à la source de ce tableau (quelle qu'elle soit).

    Un de ces moyens est la manière tas binaire est généralement représentée par votre lien. Si c'était la représentation utilisée, -1 ne serait pas l'élément racine. Et le nœud à la position 3 aurait pas d'enfants, c'est à dire qu'il serait une feuille.

    Et, oui, c'est probablement important de savoir si c'est censé être une arborescence complète ou non.

    En général, vous ne devriez pas essayer de comprendre ce qui n'certaines données, comme ceci. Vous devez disposer de la documentation ou du code source qui utilise les données. Si vous n'avez pas et que vous avez vraiment besoin de rétro-conception, vous avez probablement besoin d'en savoir plus sur les données. L'observation du comportement du code qui utilise il devrait vous aider. Ou la décompilation du code.

    OriginalL'auteur svick

  2. 14

    N=0 doit être le nœud racine depuis par les règles de la liste, il n'a pas de parent. 0 ne peuvent pas être créés à partir des expressions (2*N + 1) ou (2*N + 2), en supposant que rien de négatif à N.

    Remarque, l'indice n'est pas la valeur stockée dans la matrice, c'est la place dans le tableau.
    Pour [1, 2, 5, 6, -1, 8, 11]
    L'Index 0 = 1
    Indice 1 = 2
    Indice 2 = 5, etc.

    Si c'est un arbre, alors -1 est une valeur valide et l'arbre est

        1  
   / \  
  2    5  
 /\  /\  
6 -1 8  11

    -1 pourrait aussi être un "NULL" pointeur pour indiquer aucune valeur n'existe au niveau de ce nœud.

    Si l'Arbre ressemblerait 

        1  
   /\  
  2   5  
 /  /\  
6   8  11
    Je pense qu'il est également intéressant de noter que le parent du nœud d'indice i peut être consulté par la recherche au niveau de l'index (i-1)/2.

    OriginalL'auteur J Yu

  3. 0

    Il peut ne pas être complète arbre binaire, mais il ne peut pas être arbitraire. Vous pouvez représenter un arbre qui produit tout au plus quelques de la la plus à droite, quelques feuilles sont manquants (ou, si vous avez d'échange de la convention pour la gauche et la droite, les enfants, tout au plus un peu de gauche à feuilles manquantes).

    Vous ne pouvez pas vous représenter dans votre tableau:

        A
   /\
  B   C
 /  /
D   E

    Mais vous pouvez représenter cette

        A
   /\
  B   C
 /\  
D   E

    ou ceci:

        A
   /\
  B   C
 /\  
D   E

    (pour la dernière, ont 2k+1 de la droit enfant et 2k+2 le gauche enfant)

    Vous avez seulement besoin de savoir le nombre de nœuds dans le trois.

    OriginalL'auteur chill