Dans cet article, nous discuterons du parcours de précommande dans la structure de données. Les structures de données linéaires telles que la pile, le tableau, la file d'attente, etc. n'ont qu'un seul moyen de parcourir les données. Mais dans une structure de données hiérarchique telle que arbre , il existe plusieurs façons de parcourir les données.
Lors du parcours de précommande, le nœud racine est d'abord visité, puis le sous-arbre gauche et ensuite le sous-arbre droit est visité. Le processus de parcours de précommande peut être représenté comme -
architecture de démarrage à ressort
root → left → right
Le nœud racine est toujours traversé en premier lors du parcours pré-ordre, alors qu'il est le dernier élément du parcours post-ordre. Le parcours de précommande est utilisé pour obtenir l'expression de préfixe d'un arbre.
Les étapes pour effectuer le parcours de précommande sont répertoriées comme suit -
- Tout d’abord, visitez le nœud racine.
- Ensuite, visitez le sous-arbre de gauche.
- Enfin, visitez le sous-arbre de droite.
La technique de traversée des précommandes suit la Racine Gauche Droite politique. Le nom preorder lui-même suggère que le nœud racine serait traversé en premier.
Algorithme
Voyons maintenant l'algorithme de parcours de précommande.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END
Exemple de parcours de précommande
Voyons maintenant un exemple de parcours de précommande. Il sera plus facile de comprendre le processus de parcours des précommandes à l'aide d'un exemple.
Les nœuds de couleur jaune ne sont pas encore visités. Maintenant, nous allons parcourir les nœuds de l'arborescence ci-dessus en utilisant le parcours de précommande.
- Commencez par le nœud racine 40. Tout d’abord, imprimer 40 puis parcourez récursivement le sous-arbre gauche.
- Maintenant, passez au sous-arbre de gauche. Pour le sous-arbre gauche, le nœud racine est 30. Imprimer 30 , et déplacez-vous vers le sous-arbre gauche de 30.
- Dans le sous-arbre gauche de 30, il y a un élément 25, donc imprimer 25 , et parcourez le sous-arbre gauche de 25.
- Dans le sous-arbre gauche de 25, il y a un élément 15 et 15 n'a pas de sous-arbre. Donc, imprimer 15 , et déplacez-vous vers le sous-arbre droit de 25.
- Dans le sous-arbre droit de 25, il y en a 28 et 28 n'a pas de sous-arbre. Donc, imprimer 28 , et déplacez-vous vers le sous-arbre droit de 30.
- Dans le sous-arbre droit de 30, il y en a 35 qui n'ont pas de sous-arbre. Donc imprimer 35 , et parcourez le sous-arbre droit de 40.
- Dans le sous-arbre droit de 40, il y en a 50. Imprimer 50 , et parcourez le sous-arbre gauche de 50.
- Dans le sous-arbre gauche de 50, il y en a 45 qui n’ont aucun enfant. Donc, imprimer 45 , et parcourez le sous-arbre droit de 50.
- Dans le sous-arbre droit de 50, il y en a 60. Imprimer 60 et parcourez le sous-arbre gauche de 60.
- Dans le sous-arbre gauche de 60, il y en a 55 qui n’ont aucun enfant. Donc, imprimer 55 et passez au sous-arbre droit de 60.
- Dans le sous-arbre droit de 60, il y en a 70 qui n’ont aucun enfant. Donc, imprimer 70 et arrêter le processus.
Une fois le parcours de précommande terminé, le résultat final est -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Complexité du parcours de précommande
La complexité temporelle du parcours de précommande est Sur) , où 'n' est la taille de l'arbre binaire.
Alors que la complexité spatiale du parcours de précommande est O(1) , si l'on ne considère pas la taille de la pile pour les appels de fonction. Sinon, la complexité spatiale du parcours de précommande est Oh) , où « h » est la hauteur de l'arbre.
Implémentation du parcours de précommande
Voyons maintenant l'implémentation du parcours de précommande dans différents langages de programmation.
Programme: Écrivez un programme pour implémenter le parcours de précommande en langage C.
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); return 0; } Sortir
Après l'exécution du code ci-dessus, le résultat sera -
Programme: Écrivez un programme pour implémenter le parcours de précommande en C++.
entreprise contre entreprise
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } int main() { struct node* root = createNode(39); root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-14.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(38); bt.root.left = new Node(28); bt.root.right = new Node(48); bt.root.left.left = new Node(23); bt.root.left.right = new Node(33); bt.root.left.left.left = new Node(13); bt.root.left.left.right = new Node(26); bt.root.right.left = new Node(43); bt.root.right.right = new Node(58); bt.root.right.right.left = new Node(53); bt.root.right.right.right = new Node(68); Console.WriteLine('Preorder traversal of given binary tree is - '); bt.traversePreorder(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-15.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-16.webp" alt="Preorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Sortir
Après l'exécution du code ci-dessus, le résultat sera -
Programme: Écrivez un programme pour implémenter le parcours de précommande en Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } Sortir
Après l'exécution du code ci-dessus, le résultat sera -
Donc, c'est tout à propos de l'article. J'espère que l'article vous sera utile et informatif.