La recherche de l'emplacement d'un parent du nœud dans un arbre binaire

Donc j'ai besoin d'aide venir avec une expression qui me donnent toujours l'emplacement d'un parent de l'enfant nœud dans un arbre binaire. Voici un exemple d'un problème de mon professeur va mettre sur notre examen:

"Considérer un arbre binaire complet avec exactement de 10 000 nœuds, mis en œuvre avec un tableau commençant à l'index 0 . Le tableau est rempli dans l'ordre par l'extraction d'éléments de l'arbre d'un niveau à la fois de gauche à droite. Supposons qu'un nœud a sa valeur stockée dans l'emplacement 4999. Où est la valeur stockée pour ce nœud parent?"

Mon professeur ne nous a pas dit comment résoudre un problème de ce genre. Elle a juste dit "Dessiner un arbre binaire et trouver un patron." Je n'ai que ça, mais je ne pouvais pas trouver quoi que ce soit! s'il vous plaît aider. merci.

Vous devriez écrire exactement ce que vous avez essayé. Il y a peut être une simple erreur quelque part.
Comme indiqué, cette question est impossible. Vous devez avoir mal compris ou mal rappelé. Je peux immédiatement penser à des façons que les deux 4998 et 5000 sont la réponse.
pas de. L'expression qui me donnera l'emplacement de n'importe quel parent de l'enfant sera sous la forme de "2^(n+1) - 1" ou quelque chose comme ça. Ensuite, vous mettez dans la situation de l'enfant (4999 dans ce cas) et l'expression devrait vous donner l'emplacement du nœud parent.
Je n'ai pas vraiment besoin de savoir comment résoudre ce problème. J'ai besoin de plus d'une stratégie visant à trouver un algorithme ou d'une équation comme celle-ci qui va me donner l'emplacement du nœud parent. Elle dit qu'elle va nous donner un arbre binaire de mise en œuvre comme un tableau. La racine de l'arbre binaire pourrait commencer à l'indice 0 du tableau ou à 99. Mon travail est de trouver une équation telle que lorsque vous branchez l'emplacement d'un nœud enfant, il va produire de l'emplacement du nœud parent. J'espère que je fais de bon sens ici
Vraiment? Il y a 2^k éléments dans la k-ième ligne, afin que nous puissions carte 4999 retour à l'arbre de l'emplacement, de sortir l'arbre de localisation de la mère, et puis la carte que le retour à l'index de tableau, sûrement? Pourquoi y aurait-il une ambiguïté dans le résultat?

OriginalL'auteur user2188910 | 2013-03-20

  1. 8

    La suite est entièrement à l'aide d'division entière. I. e. les fractions les restes sont déposés. Pour un nœud donné index N, les enfants de ce nœud sera toujours dans des endroits 2N+1 et 2(N+1) dans le même tableau.

    Par conséquent, Le parent d'un nœud N > 0 dans le tableau sera toujours à l'index (N-1)/2.

    Parent à l'Enfant Exemples: 

    Parent 0: children 1,2
Parent 1: children 3,4
Parent 2: children 5,6
Parent 3: children 7,8
etc...

    Enfant à Parent Exemples:

    Child 8 : Parent = (8-1)/2 = 7/2 = 3
Child 7 : Parent = (7-1)/2 = 6/2 = 3
Child 6 : Parent = (6-1)/2 = 5/2 = 2
Child 5 : Parent = (5-1)/2 = 4/2 = 2

    Alors, pour ton problème:

    (4999-1)/2 = 4998/2 = 2499

    Remarque: rappelez-vous ceci, puisque vous serez à l'aide largement lorsque vous démarrez le codage basée sur la baie de tas-algorithmes de tri.

    OriginalL'auteur WhozCraig

  2. 2

    Il semble que ce est la façon dont les éléments de matrice de la carte vers l'arbre basé sur les indices de tableau

         0
  1     2
3   4 5   6

    Si oui, alors le parent de l'indice de n est à floor( (n - 1) /2 ) (pour n != 0)

    OriginalL'auteur Arun

  3. 2

    Merci à tous pour votre aide les gars. Et j'ai trouvé la réponse à ma question!

    L'algorithme général pour la recherche de l'emplacement du nœud parent est:

    [i + (racine - 1)] /2 où i est l'emplacement du nœud donné et de la racine est l'emplacement de la racine. Ainsi, dans le problème, au-dessus de la racine commence à la position 0. donc l'équation pour trouver le nœud parent d'un nœud est [i + (0 - 1)] /2 = (i - 1) /2

    Disons maintenant que la racine a commencé à la position 3, alors l'équation [i + (3 - 1)] /2
    = (i + 2) /2!!!! C'est l'algorithme dont j'avais besoin. La plupart d'entre vous m'a aidé à résoudre un problème que j'ai fourni, mais j'ai vraiment besoin de la solution générale pour un arbre binaire dont la racine peut commencer à tout postions; pas seulement à zéro

    OriginalL'auteur user2188910

  4. 0

    Si vous ne le log2 du nombre demandé (4999) et de prendre la partie entière, il vous donnera le plus proche de la puissance de deux pour le nombre (12). Il est de 2^12 = 4096.

    Le parent des nœuds entre 4096 et 2^13 - 1, sont celles entre le 2^11 et 2^12 - 1. Et pour chaque paire de nœuds dans la première plage que vous avez son parent dans la seconde. Alors vous pouvez mapper en prenant la partie entière de la moitié de la différence (4999 - 4096) et de l'ajouter au parent, au début de la plage (2048).

    De sorte que vous aurez étage de 903 /2, et l'ajouter à 2048, se 2499.

    Notez que je n'ai pas fait de calcul précis, à prendre la stratégie de la réponse n'est pas les résultats.

    Vous pouvez mettre cet algorithme dans une expression mathématique, avec un peu de travail.

    Espère que cela aide!

    bon. vous avez obtenu la bonne réponse si vous savez ce que je demande ici. Maintenant j'ai juste à lire attentivement ce que vous avez dit et essayer de comprendre votre stratégie lol. merci pour la réponse.
    alors que votre réponse est correcte à 100%, (stratégie, je n'ai pas vérifier les cas de bord), il y a un très équation simple qui devrait donner la même réponse.

    OriginalL'auteur nico