C++ - arbre fileté, traversée ordonnée

Question

Je viens de mettre en place un arbre fileté en C++, et maintenant j'essaie de cout tous les éléments dans l'ordre.

L'arbre était un arbre trié binaire (non équilibré) avant que je l'ai enfilé.

J'ai essayé de faire ceci:

E min = _min(root); //returns the minimum element of the tree 
E max = _max(root); //returns the maximum element of the tree 

while (min != max) 
{ 
    std::cout << min << ", "; 
    min = _successor(root, min); 
} 
std::cout << max << ", "; 
std::cout << std::endl; 

mais depuis l'arbre est maintenant enfilé, ma fonction successeur retourne toujours le minimum de l'arbre entier (en gros, il va une fois dans le sous-arbre droit, puis va dans le sous-arbre de gauche autant de fois que possible, jusqu'à ce qu'il trouve une feuille.) Donc quand j'essaie d'appeler cette fonction, il faut seulement cout 1 (parce que 1 est la valeur minimale de mon arbre).

Aussi, j'ai essayé quelque chose d'autre:

E min = _min(root); //returns min element of the tree 
    E max = _max(root); //returns max element of the tree 
    Node* tmp = _getNode(root, min); //returns the node of the specified element, therefore the minimum node of the tree 
    while(tmp->data < max) 
    { 
      std::cout << tmp->data << ", "; 
      tmp = _getNode(root, tmp->data)->rightChild; //gets the right child node of tmp 
    } 
    std::cout << tmp->data << ", "; 

Cependant, en faisant cela, il y a des valeurs qui sont ignorées. (Voir image ci-dessous)

(liens verts ont été ajoutés après le filetage de l'arbre.) Si vous voyez, par exemple, le nœud # 6 ne reçoit la visite du dernier algorithme, parce que ce n'est pas droit de l'enfant d'un nœud dans l'arbre ...

est ici la sortie de la fonction précédente:

1, 2, 3, 5, 7, 8, 11, 71 

est-ce que quelqu'un a une idée de la façon dont je pouvais résoudre ce problème, ou des conseils pour mon problème?

Merci

EDIT: Après tout ce que je viens d'avoir à traverser l'arbre du minimum au maximum et modifier mes méthodes de _predecessor et _successor, donc ils ne vérifierait pas dans les sous-arbres qui sont filetés. :)

Espérons que cela aidera les futurs lecteurs.

Answer 1

Essayez

Node* n = _min(root); 
while (n->right) { 
    cout << n->val << ", "; 
    n = _successor(n); 
} 
cout << n->val << endl; 

Ceci est essentiellement votre premier code (notez que je suppose que l'arbre est non vide comme vous ne). Cela ne vous donnera pas non plus un «,».

L'important est de faire en sorte que la fonction de votre successeur soit correcte. Il devrait être comme ça

Node* _successor(Node* n) { 
    if (is_thread(o, RIGHT)) return o->right; 
    return _min(o->right); 
} 

Et pour être complet

Node* _min(Node* n) { 
    while (!is_thread(o, LEFT)) n = o->left; 
    return n; 
} 

Pour ces deux toutes les flèches vertes sont des fils.

Answer 2

Je n'ai jamais vu d'arbres filetés auparavant, mais je vais quand même tenter de le faire. Pour créer une traversée inorder, vous pouvez approcher la racine de l'arborescence à partir de deux directions à la fois:

1. Commencez à la racine.
2. Suivez tous les liens de gauche jusqu'à ce que vous en trouviez un pointant vers null. Cet élément est la valeur minimale de l'arbre.
3. Suivez tous les bons liens jusqu'à la racine. Si vous avez correctement construit l'arbre, celui-ci devrait traverser chaque élément dans l'ordre croissant.
4. Répétez les étapes 2 et 3 dans le sens opposé (recherchez l'élément max, marchez vers l'arrière).
5. Joignez ces deux listes avec la racine au milieu.

Ce n'est probablement pas l'algorithme le plus rapide, mais je pense qu'il va produire une réponse correcte. Et vous n'avez pas eu besoin d'utiliser la récursivité, ce qui, je suppose, est le point principal pour utiliser un arbre fileté.

Answer 3

Après tout ce que je viens d'avoir à traverser l'arbre du minimum aux ET maximales modifier mes méthodes de _predecessor et _successor, donc ils ne vérifierait pas dans les sous-arbres qui sont filetés. :)

Espérons que cela aidera les futurs lecteurs.