PRÉCOMMANDE TRAVERSÉE DE L'ARBRE BINAIRE

Parcours des précommandes est défini comme un type de parcours d'arbre qui suit la politique Root-Left-Right où :

Le nœud racine du sous-arbre est visité en premier.
Ensuite, le sous-arbre gauche est parcouru.
Enfin, le sous-arbre droit est parcouru.

Parcours des précommandes

Algorithme pour la traversée de précommande de l'arbre binaire

L'algorithme de parcours de précommande est présenté comme suit :

Précommande (root) :

Suivez les étapes 2 à 4 jusqu'à ce que root != NULL
Écrire racine -> données
Précommande (racine -> gauche)
Précommande (racine -> droite)
Fin de la boucle

Comment fonctionne la traversée de précommande de l'arbre binaire ?

Considérons l'arbre suivant :

Exemple d'arbre binaire

Si nous effectuons un parcours de précommande dans cet arbre binaire, alors le parcours sera le suivant :

Étape 1: Dans un premier temps, la racine sera visitée, c'est-à-dire le nœud 1.

Le nœud 1 est visité

Étape 2: Après cela, parcourez le sous-arbre de gauche. Maintenant, la racine du sous-arbre gauche est visitée, c'est-à-dire que le nœud 2 est visité.

Le nœud 2 est visité

Étape 3: Encore une fois, le sous-arbre gauche du nœud 2 est parcouru et la racine de ce sous-arbre, c'est-à-dire le nœud 4, est visitée.

Le nœud 4 est visité

Étape 4: Il n’y a pas de sous-arbre de 4 et le sous-arbre gauche du nœud 2 est visité. Alors maintenant, le sous-arbre droit du nœud 2 sera parcouru et la racine de ce sous-arbre, c'est-à-dire le nœud 5, sera visitée.

Le nœud 5 est visité

Étape 5 : Le sous-arbre gauche du nœud 1 est visité. Alors maintenant, le sous-arbre droit du nœud 1 sera parcouru et le nœud racine, c'est-à-dire le nœud 3, sera visité.

Le nœud 3 est visité
schéma du modèle e-r

Étape 6 : Le nœud 3 n'a pas de sous-arbre gauche. Ainsi, le sous-arbre droit sera parcouru et la racine du sous-arbre, c'est-à-dire le nœud 6, sera visitée. Après cela, il n’y a plus de nœud qui ne soit pas encore traversé. La traversée se termine donc.

L'arbre complet est visité

L’ordre de parcours des nœuds est donc 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

Programme pour implémenter la traversée de précommande de l'arbre binaire

Vous trouverez ci-dessous l'implémentation du code du parcours de précommande :

C++

 // C++ program for preorder traversals #include  using namespace std; // Structure of a Binary Tree Node struct Node {  int data;  struct Node *left, *right;  Node(int v)  {  data = v;  left = right = NULL;  } }; // Function to print preorder traversal void printPreorder(struct Node* node) {  if (node == NULL)  return;  // Deal with the node  cout << node->données<< ' ';  // Recur on left subtree  printPreorder(node->gauche);  // Récurrence sur le sous-arbre droit printPreorder(node->right); } // Code du pilote int main() { struct Node* root = new Node(1);  racine->gauche = new Node(2);  racine->droite = new Node(3);  racine->gauche->gauche = new Node(4);  racine->gauche->droite = new Node(5);  racine->droite->droite = new Node(6);  // Appel de fonction cout<< 'Preorder traversal of binary tree is: 
';  printPreorder(root);  return 0; }>

Java

 // Java program for preorder traversals class Node {  int data;  Node left, right;  public Node(int item) {  data = item;  left = right = null;  } } class BinaryTree {  Node root;  BinaryTree() {  root = null;  }  // Function to print preorder traversal  void printPreorder(Node node) {  if (node == null)  return;  // Deal with the node  System.out.print(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void main(String[] args) {  BinaryTree tree = new BinaryTree();  // Constructing the binary tree  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  // Function call  System.out.println('Preorder traversal of binary tree is: ');  tree.printPreorder(tree.root);  } }>

Python3

 # Python program for preorder traversals # Structure of a Binary Tree Node class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Function to print preorder traversal def printPreorder(node): if node is None: return # Deal with the node print(node.data, end=' ') # Recur on left subtree printPreorder(node.left) # Recur on right subtree printPreorder(node.right) # Driver code if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) # Function call print('Preorder traversal of binary tree is:') printPreorder(root)>

 // C# program for preorder traversals using System; // Structure of a Binary Tree Node public class Node {  public int data;  public Node left, right;  public Node(int v)  {  data = v;  left = right = null;  } } // Class to print preorder traversal public class BinaryTree {  // Function to print preorder traversal  public static void printPreorder(Node node)  {  if (node == null)  return;  // Deal with the node  Console.Write(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void Main()  {  Node root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  Console.WriteLine(  'Preorder traversal of binary tree is: ');  printPreorder(root);  } } // This code is contributed by Susobhan Akhuli>

Javascript

 // Structure of a Binary Tree Node class Node {  constructor(v) {  this.data = v;  this.left = null;  this.right = null;  } } // Function to print preorder traversal function printPreorder(node) {  if (node === null) {  return;  }  // Deal with the node  console.log(node.data);  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right); } // Driver code function main() {  const root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  console.log('Preorder traversal of binary tree is:');  printPreorder(root); } main();>

Sortir

Preorder traversal of binary tree is: 1 2 4 5 3 6>

Explication:

Comment fonctionne le parcours de précommande

Analyse de complexité :

Complexité temporelle : O(N) où N est le nombre total de nœuds. Parce qu'il traverse tous les nœuds au moins une fois.
Espace auxiliaire :

O(1) si aucun espace de pile de récursion n'est pris en compte.
Sinon, Oh) où h est la hauteur de l'arbre
Au pire des cas, h peut être le même que N (quand l'arbre est un arbre de travers)
Dans le meilleur des cas, h peut être le même que calme (quand l'arbre est un arbre complet)

Cas d'utilisation de Preorder Traversal :

Voici quelques cas d'utilisation du parcours de précommande :

Ceci est souvent utilisé pour créer une copie d’un arbre.
Il est également utile d'obtenir l'expression de préfixe à partir d'un arbre d'expression.

Articles Liés:

Types de traversée d’arbres
Parcours itératif de précommande
Vérifiez si le tableau donné peut représenter une traversée de précommande de BST
Précommande à partir des traversées de commande et de post-commande
Trouver le nième nœud dans le parcours de pré-ordre d'un arbre binaire
Parcours de précommande d'un arbre N-aire