Donné un arbre binaire, écrivez une solution itérative et récursive pour traverser l’arbre en utilisant la traversée en ordre en C++, Java et Python.
Contrairement aux listes chaînées, aux tableaux unidimensionnels et à d’autres structures de données linéaires, qui sont parcourues dans un ordre linéaire, les arbres peuvent être parcourus de plusieurs façons dans l’ordre de la profondeur (préordre, inordre et postordre) ou dans l’ordre de la largeur (traversée par ordre de niveau). Au-delà de ces traversées de base, divers schémas plus complexes ou hybrides sont possibles, tels que les recherches limitées en profondeur comme la recherche itérative en profondeur et en premier. Dans ce post, la traversée d’arbre en ordre est discutée en détail.
Traverser un arbre implique d’itérer sur tous les nœuds d’une certaine manière. Comme l’arbre n’est pas une structure de données linéaire, il peut y avoir plus d’un prochain nœud possible à partir d’un nœud donné, donc certains nœuds doivent être différés, c’est-à-dire stockés d’une certaine manière pour une visite ultérieure. La traversée peut être faite de manière itérative où les nœuds différés sont stockés dans la pile, ou elle peut être faite par récursion, où les nœuds différés sont stockés implicitement dans la pile d’appel.
Pour traverser un arbre binaire (non vide) de manière ordonnée, nous devons faire ces trois choses pour chaque nœud n en commençant par la racine de l’arbre :
(L) Traverser récursivement son sous-arbre gauche. Lorsque cette étape est terminée, nous sommes de nouveau à n.(N) Traiter n lui-même.(R) Parcourir récursivement son sous-arbre droit. Lorsque cette étape est terminée, nous sommes de nouveau à n.Dans une traversée normale en ordre, nous visitons le sous-arbre de gauche avant le sous-arbre de droite. Si nous visitons le sous-arbre de droite avant de visiter le sous-arbre de gauche, on parle de traversée en ordre inverse.
Comme nous pouvons le voir, avant de traiter un nœud, le sous-arbre de gauche est traité en premier, suivi du nœud, et le sous-arbre de droite est traité en dernier. Ces opérations peuvent être définies de manière récursive pour chaque nœud. L’implémentation récursive est appelée recherche en profondeur (DFS), car l’arbre de recherche est approfondi autant que possible sur chaque enfant avant de passer au frère ou à la sœur suivant(e).
Voici le programme C++, Java et Python qui le démontre :
Implémentation itérative –
Pour convertir la procédure récursive ci-dessus en une procédure itérative, nous avons besoin d’une pile explicite. Ci-dessous est un algorithme itératif simple basé sur la pile pour effectuer une traversée d’ordre.
iterativeInorder(node)
L’algorithme peut être implémenté comme suit en C++, Java et Python :
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
// Fonction itérative fonction pour effectuer un parcours en ordre sur l’arbre
void inorderIterative(Node *root)
{
// créer une pile vide
pile<Node*> ;
// commencer à partir du noeud racine (définir le noeud actuel au noeud racine)
Node *curr = racine ;
// si le noeud actuel est nul et que la pile est également vide, nous avons terminé
while ( !stack.empty() || curr != nullptr)
{
// si le noeud actuel existe, on le pousse dans la pile (on le reporte)
// et on se déplace vers son enfant gauche
if (curr != nullptr)
{
stack.push(curr) ;
curr = curr->left ;
}
else
{
// sinon, si le nœud actuel est nul, on extrait un élément de la pile,
// on l’imprime, et enfin on fixe le nœud actuel à son enfant de droite
curr = stack.top() ;
stack.pop() ;
cout << curr->data << » » ;
curr = curr->right ;
}
}
}
|
Télécharger Exécuter le code complet
.
Java
|
1
2
3
. 4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// Itératif fonction pour effectuer une traversée en ordre sur l’arbre
public static void inorderIterative(TreeNode root)
{
// créer une pile vide
Stack<TreeNode> stack = new Stack() ;
// commencer à partir du noeud racine (définir le noeud actuel au noeud racine)
TreeNode curr = root ;
// si le noeud actuel est nul et que la pile est également vide, nous avons terminé
while ( !stack.empty() || curr != null)
{
// si le nœud actuel existe, on le pousse dans la pile (on le reporte)
// et on se déplace vers son enfant gauche
si (curr != null)
{
stack.push(curr) ;
curr = curr.left ;
}
else
{
// sinon, si le nœud actuel est nul, on extrait un élément de la pile,
// on l’imprime, et enfin on fixe le nœud actuel à son enfant de droite
curr = stack.pop() ;
System.out.print(curr.data + » « ) ;
curr = curr.right ;
}
}
}
|
Télécharger exécuter le code complet
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
# Fonction itérative pour effectuer un parcours en ordre sur l’arbre
def inorderIterative(root) :
# créer une pile vide
pile = deque()
# commencer à partir du nœud racine (définir le nœud actuel sur le nœud racine)
curr = racine
# si le nœud actuel est None et que la pile est également vide, nous avons terminé
while stack or curr :
# si le noeud courant existe, on le pousse dans la pile (on le reporte)
# et on se déplace vers son enfant gauche
if curr :
stack.append(curr)
curr = curr.left
else :
# sinon, si le noeud courant est None, on extrait un élément de la pile,
# on l’imprime, et enfin on met le noeud courant à son enfant de droite
curr = stack.pop()
print(curr.data, end=’ ‘)
curr = curr.right
|
Télécharger le code complet
La complexité temporelle des solutions ci-dessus est O(n), où n est le nombre total de nœuds dans l’arbre binaire. La complexité spatiale du programme est O(n) car l’espace requis est proportionnel à la hauteur de l’arbre, qui peut être égale au nombre total de nœuds de l’arbre dans le pire des cas pour les arbres asymétriques.