"Escalade" d'un arbre binaire

Question

Existe-t-il un moyen de grimper directement au nombre sans visiter d'autres succursales? Par exemple si j'ai le numéro 11 je dois le visiter en allant à 2 puis à 5 et à 11 sans aucun type de recherche.

        0 
          /  \ 
         /   \ 
         /   \ 
         1    2 
        / \   / \ 
        / \  / \ 
        3  4  5  6 
       /\ /\ /\ /\ 
       / \ / \ / \ / \ 
       7  8 9 10 11 12 13 14 

J'ai tué beaucoup de temps la seule chose que je suis maintenant est que pour obtenir la première route (1 ou 2) du numéro N vous devez (n-1)/2 jusqu'à ce que n est égal à 1 ou 2. Exemple: (12 - 1)/2 => (5 - 1)/2 => 2. (7-1)/2 => (3-1)/2 => 1. (11-1)/5 => (2-1)/2 => 1. Mais fin il serait correct de couper la racine (0) et traiter 2 comme une nouvelle:

  2 
     /\ 
     / \ 
    / \ 
    5  6 
    /\ /\ 
/ \ / \ 
    11 12 13 14 

     to 

      0 
     /\ 
     / \ 
    / \ 
    1  2 
    /\ /\ 
/ \ / \ 
    3  4 5  6 

Solution :

int climb(int ID, Tree<int> t) 
{ 

    int time = 0; 
    if (tree.exists()) { 
     time += t.value(); 
     tree t1, t2; 
     t.branches(t1, t2); 
     int branch = ID; 
     while (branch > 2) branch = (branch - 1)/2; 
     int offset = 1; 
     while (offset*2 < ID - 1) offset *= 2; 
     if (aux == 1) time += climb(ID - offset2/, a1); 
     if (aux == 2) time += climb(ID - offset, a2); 
    } 
    return time; 
} 

Vous pouvez accéder à n'importe quel élément (1, 5, 13, etc) de l'arbre binaire complet.

Answer 1

Si vous souhaitez ignorer tous les noeuds intermédiaires, utilisez un conteneur de hachage (par exemple, std::map ou std::set) et effectuez une recherche de hachage. Les arbres binaires sont destinés à être parcourus récursivement. Notez que set n'est pas associatif, vous devrez donc contourner le problème. Si vous tentez trop d'ajouter des variables de code/membres personnalisées à des nœuds arbre/arbre, vous risquez de vous retrouver avec un arbre impliqué qui est lourd en mémoire (la réponse de David en est un très bon exemple).

- modifier -

Si vos identifiants sont toujours une séquence sans trop de trous (par exemple 0, 1, 2,..., 50 OU 68, 69,...,230,231) Je recommande l'ancien tableau clair! Faites-moi savoir si vous voulez en savoir plus.

En général, mon message est de choisir le bon conteneur/structure en premier, et seulement si nécessaire faire des modifications «mineures» à la structure elle-même.

Answer 2

Je suppose que vous avez un arbre binaire parfait (toutes les feuilles sont à la même profondeur, et dans chaque parent a deux enfants) et les valeurs de tous les nœuds sont comme dans l'exemple que vous avez fourni.

Dans ce cas, notez les éléments suivants:

• Un nœud n est que les enfants les noeuds avec des valeurs 2 * n + 1, 2 * n + 2
• Si vous voulez aller un nœud avec la valeur impaire K, alors son parent est le nœud (K-1)/2
• Si vous voulez visiter un nœud avec la valeur paire K, son parent est le nœud (K-2)/2

Vous répétez la même procédure puisque vous atteignez le nœud 0 et que vous avez tous les nœuds que vous avez à visiter.

Donc, pour votre exemple que vous voulez visiter le noeud 11.

11 is odd so its parent is (11-1)/2 = 5 
5 is odd so its parent is (5-1)/2 = 2 
2 is even so its parent is (2-2)/0 = 0 

we have reached the root node, so you have to follow the path 0->2->5->11 

Answer 3

Je voulais « monter » à une branche ou une feuille sans accès à des branches qui ne sont pas de la manière (si je grimpe à « 4 'alors je vais directement 0 -> 2 -> 4). Et seul le chemin que j'ai raté était décalé qui va "morpher" la branche en arbre (voir question).

Je reçois décalage comme ça:

int offset = 1; 
while (offset*2 < ID - 1) offset *= 2; 

Il travaille pour la branche '2' et offset/2 travaillera pour la branche '1'.

int climb(int ID, Tree<int> t) 
{ 

    int time = 0; 
    if (tree.exists()) { 
     time += t.value(); 
     tree t1, t2; 
     t.branches(t1, t2); 
     int branch = ID; 
     while (branch > 2) branch = (branch - 1)/2; 
     int offset = 1; 
     while (offset*2 < ID - 1) offset *= 2; 
     if (aux == 1) time += climb(ID - offset2/, a1); 
     if (aux == 2) time += climb(ID - offset, a2); 
    } 
    return time; 
} 

Answer 4

Autre moyen était de faire une pile:

void solve(int n) 
{ 
    stack<direction> path; 
//Calculate the way 
    while (n > 0) 
    { 
    if (n & 1) // if n is odd; 
     path.push_back(left); 
    else 
     path.push_back(right); 

    n = (n - 1)/2; 
    } 

    //Do actual "climbing" 

    while (!path.empty()) 
    { 
    if (path.top() == left) 
    { 
     go left 
    } 
    else 
    { 
     go right 
    } 

    path.pop(); 
    } 
} 

Thx à Raving_Zealot de linux.org.ru