Donné un
Un arbre de recherche binaire
Sortir:
Traversée dans l'ordre : 10 20 30 100 150 200 300
Traversée de précommande : 100 20 10 30 200 150 300
Mandat postal Traversée : 10 30 20 150 300 200 100
Saisir:
Arbre de recherche binaire
Sortir:
Traversée dans l'ordre : 8 12 20 22 25 30 40
Traversée en précommande : 22 12 8 20 30 25 40
Vente par correspondance Traversée : 8 20 12 25 40 30 22
Traversée dans l'ordre :
Voici l'idée pour résoudre le problème :
Au premier passage sous-arbre gauche puis visitez le racine puis traversez le sous-arbre droit .
Suivez les étapes ci-dessous pour mettre en œuvre l'idée :
- Traverser le sous-arbre gauche
- Visitez la racine et imprimez les données.
- Traverser le sous-arbre de droite
Le parcours dans l'ordre du BST donne les valeurs des nœuds par ordre trié. Pour obtenir l’ordre décroissant, visitez le sous-arbre droit, racine et gauche.
Vous trouverez ci-dessous l'implémentation du parcours inorder.
C++
// C++ code to implement the approach> #include> using> namespace> std;> // Class describing a node of tree> class> Node {> public>:> >int> data;> >Node* left;> >Node* right;> >Node(>int> v)> >{> >this>->données = v;> >this>->gauche =>this>->droite = NULL;> >}> };> // Inorder Traversal> void> printInorder(Node* node)> {> >if> (node == NULL)> >return>;> >// Traverse left subtree> >printInorder(node->à gauche);> >// Visit node> >cout ' '; // Traverse right subtree printInorder(node->droite); } // Code du pilote int main() { // Construire l'arborescence Node* root = new Node(100); racine->gauche = new Node(20); racine->droite = nouveau nœud (200); racine->gauche->gauche = new Node(10); racine->gauche->droite = new Node(30); racine->droite->gauche = new Node(150); racine->droite->droite = new Node(300); // Appel de fonction cout<< 'Inorder Traversal: '; printInorder(root); return 0; }> |
>
rebase git
>
Java
// Java code to implement the approach> import> java.io.*;> // Class describing a node of tree> class> Node {> >int> data;> >Node left;> >Node right;> >Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> class> GFG {> >// Inorder Traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// Traverse left subtree> >printInorder(node.left);> >// Visit node> >System.out.print(node.data +>' '>);> >// Traverse right subtree> >printInorder(node.right);> >}> >// Driver Code> >public> static> void> main(String[] args)> >{> >// Build the tree> >Node root =>new> Node(>100>);> >root.left =>new> Node(>20>);> >root.right =>new> Node(>200>);> >root.left.left =>new> Node(>10>);> >root.left.right =>new> Node(>30>);> >root.right.left =>new> Node(>150>);> >root.right.right =>new> Node(>300>);> >// Function call> >System.out.print(>'Inorder Traversal: '>);> >printInorder(root);> >}> }> // This code is contributed by Rohit Pradhan> |
>
>
Python3
# Python3 code to implement the approach> # Class describing a node of tree> class> Node:> >def> __init__(>self>, v):> >self>.left>=> None> >self>.right>=> None> >self>.data>=> v> # Inorder Traversal> def> printInorder(root):> >if> root:> ># Traverse left subtree> >printInorder(root.left)> > ># Visit node> >print>(root.data,end>=>' '>)> > ># Traverse right subtree> >printInorder(root.right)> # Driver code> if> __name__>=>=> '__main__'>:> ># Build the tree> >root>=> Node(>100>)> >root.left>=> Node(>20>)> >root.right>=> Node(>200>)> >root.left.left>=> Node(>10>)> >root.left.right>=> Node(>30>)> >root.right.left>=> Node(>150>)> >root.right.right>=> Node(>300>)> ># Function call> >print>(>'Inorder Traversal:'>,end>=>' '>)> >printInorder(root)> ># This code is contributed by ajaymakvana.> |
>
>
C#
// Include namespace system> using> System;> // Class describing a node of tree> public> class> Node> {> >public> int> data;> >public> Node left;> >public> Node right;> >public> Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> public> class> GFG> {> >// Inorder Traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >{> >return>;> >}> >// Traverse left subtree> >GFG.printInorder(node.left);> >// Visit node> >Console.Write(node.data.ToString() +>' '>);> >// Traverse right subtree> >GFG.printInorder(node.right);> >}> >// Driver Code> >public> static> void> Main(String[] args)> >{> >// Build the tree> >var> root =>new> Node(100);> >root.left =>new> Node(20);> >root.right =>new> Node(200);> >root.left.left =>new> Node(10);> >root.left.right =>new> Node(30);> >root.right.left =>new> Node(150);> >root.right.right =>new> Node(300);> >// Function call> >Console.Write(>'Inorder Traversal: '>);> >GFG.printInorder(root);> >}> }> |
>
>
Javascript
// JavaScript code to implement the approach> class Node {> constructor(v) {> this>.left =>null>;> this>.right =>null>;> this>.data = v;> }> }> // Inorder Traversal> function> printInorder(root)> {> if> (root)> {> // Traverse left subtree> printInorder(root.left);> // Visit node> console.log(root.data);> // Traverse right subtree> printInorder(root.right);> }> }> // Driver code> if> (>true>)> {> // Build the tree> let root =>new> Node(100);> root.left =>new> Node(20);> root.right =>new> Node(200);> root.left.left =>new> Node(10);> root.left.right =>new> Node(30);> root.right.left =>new> Node(150);> root.right.right =>new> Node(300);> // Function call> console.log(>'Inorder Traversal:'>);> printInorder(root);> }> // This code is contributed by akashish__> |
>
>Sortir
Inorder Traversal: 10 20 30 100 150 200 300>
Complexité temporelle : O(N), où N est le nombre de nœuds.
Espace auxiliaire : O(h), où h est la hauteur de l'arbre
Traversée de précommande :
Voici l'idée pour résoudre le problème :
Dans un premier temps, visitez le racine puis traverser sous-arbre gauche puis traversez le sous-arbre droit .
Suivez les étapes ci-dessous pour mettre en œuvre l'idée :
- Visitez la racine et imprimez les données.
- Traverser le sous-arbre gauche
- Traverser le sous-arbre de droite
Vous trouverez ci-dessous l'implémentation du parcours de précommande.
C++
// C++ code to implement the approach> #include> using> namespace> std;> // Class describing a node of tree> class> Node {> public>:> >int> data;> >Node* left;> >Node* right;> >Node(>int> v)> >{> >this>->données = v;> >this>->gauche =>this>->droite = NULL;> >}> };> // Preorder Traversal> void> printPreOrder(Node* node)> {> >if> (node == NULL)> >return>;> >// Visit Node> >cout ' '; // Traverse left subtree printPreOrder(node->gauche); // Traverse le sous-arbre droit printPreOrder(node->right); } // Code du pilote int main() { // Construire l'arborescence Node* root = new Node(100); racine->gauche = new Node(20); racine->droite = nouveau nœud (200); racine->gauche->gauche = new Node(10); racine->gauche->droite = new Node(30); racine->droite->gauche = new Node(150); racine->droite->droite = new Node(300); // Appel de fonction cout<< 'Preorder Traversal: '; printPreOrder(root); return 0; }> |
>
>
Java
// Java code to implement the approach> import> java.io.*;> // Class describing a node of tree> class> Node {> >int> data;> >Node left;> >Node right;> >Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> class> GFG {> >// Preorder Traversal> >public> static> void> printPreorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// Visit node> >System.out.print(node.data +>' '>);> >// Traverse left subtree> >printPreorder(node.left);> >// Traverse right subtree> >printPreorder(node.right);> >}> >public> static> void> main(String[] args)> >{> >// Build the tree> >Node root =>new> Node(>100>);> >root.left =>new> Node(>20>);> >root.right =>new> Node(>200>);> >root.left.left =>new> Node(>10>);> >root.left.right =>new> Node(>30>);> >root.right.left =>new> Node(>150>);> >root.right.right =>new> Node(>300>);> >// Function call> >System.out.print(>'Preorder Traversal: '>);> >printPreorder(root);> >}> }> // This code is contributed by lokeshmvs21.> |
>
>
Python3
class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Preorder Traversal> def> printPreOrder(node):> >if> node>is> None>:> >return> ># Visit Node> >print>(node.data, end>=> ' '>)> ># Traverse left subtree> >printPreOrder(node.left)> ># Traverse right subtree> >printPreOrder(node.right)> # Driver code> if> __name__>=>=> '__main__'>:> ># Build the tree> >root>=> Node(>100>)> >root.left>=> Node(>20>)> >root.right>=> Node(>200>)> >root.left.left>=> Node(>10>)> >root.left.right>=> Node(>30>)> >root.right.left>=> Node(>150>)> >root.right.right>=> Node(>300>)> ># Function call> >print>(>'Preorder Traversal: '>, end>=> '')> >printPreOrder(root)> |
>
>
C#
// Include namespace system> using> System;> // Class describing a node of tree> public> class> Node> {> >public> int> data;> >public> Node left;> >public> Node right;> >public> Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> public> class> GFG> {> >// Preorder Traversal> >public> static> void> printPreorder(Node node)> >{> >if> (node ==>null>)> >{> >return>;> >}> >// Visit node> >Console.Write(node.data.ToString() +>' '>);> >// Traverse left subtree> >GFG.printPreorder(node.left);> >// Traverse right subtree> >GFG.printPreorder(node.right);> >}> >public> static> void> Main(String[] args)> >{> >// Build the tree> >var> root =>new> Node(100);> >root.left =>new> Node(20);> >root.right =>new> Node(200);> >root.left.left =>new> Node(10);> >root.left.right =>new> Node(30);> >root.right.left =>new> Node(150);> >root.right.right =>new> Node(300);> >// Function call> >Console.Write(>'Preorder Traversal: '>);> >GFG.printPreorder(root);> >}> }> |
>
renard ou loup
>
Javascript
class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> function> printPreOrder(node) {> >if> (node ==>null>)>return>;> >console.log(node.data +>' '>);> >printPreOrder(node.left);> >printPreOrder(node.right);> }> // Build the tree> let root =>new> Node(100);> root.left =>new> Node(20);> root.right =>new> Node(200);> root.left.left =>new> Node(10);> root.left.right =>new> Node(30);> root.right.left =>new> Node(150);> root.right.right =>new> Node(300);> console.log(>'Preorder Traversal: '>);> printPreOrder(root);> // This code is contributed by akashish__> |
>
>Sortir
Preorder Traversal: 100 20 10 30 200 150 300>
Complexité temporelle : O(N), où N est le nombre de nœuds.
Espace auxiliaire : O(H), où H est la hauteur de l'arbre
Traversée des commandes postales :
Voici l'idée pour résoudre le problème :
Au premier passage sous-arbre gauche puis parcourez le sous-arbre droit puis visitez le racine .
Suivez les étapes ci-dessous pour mettre en œuvre l'idée :
- Traverser le sous-arbre gauche
- Traverser le sous-arbre de droite
- Visitez la racine et imprimez les données.
Vous trouverez ci-dessous l'implémentation du parcours post-commande :
C++
// C++ code to implement the approach> #include> using> namespace> std;> // Class to define structure of a node> class> Node {> public>:> >int> data;> >Node* left;> >Node* right;> >Node(>int> v)> >{> >this>->données = v;> >this>->gauche =>this>->droite = NULL;> >}> };> // PostOrder Traversal> void> printPostOrder(Node* node)> {> >if> (node == NULL)> >return>;> >// Traverse left subtree> >printPostOrder(node->à gauche);> >// Traverse right subtree> >printPostOrder(node->à droite);> >// Visit node> >cout ' '; } // Driver code int main() { Node* root = new Node(100); root->gauche = nouveau nœud (20); racine->droite = nouveau nœud (200); racine->gauche->gauche = new Node(10); racine->gauche->droite = new Node(30); racine->droite->gauche = new Node(150); racine->droite->droite = new Node(300); // Appel de fonction cout<< 'PostOrder Traversal: '; printPostOrder(root); cout << '
'; return 0; }> |
>
>
Java
// Java code to implement the approach> import> java.io.*;> // Class describing a node of tree> class> GFG {> > >static> class> Node {> >int> data;> >Node left;> >Node right;> >Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> >// Preorder Traversal> >public> static> void> printPreorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// Traverse left subtree> >printPreorder(node.left);> >// Traverse right subtree> >printPreorder(node.right);> > >// Visit node> >System.out.print(node.data +>' '>);> >}> >public> static> void> main(String[] args)> >{> >// Build the tree> >Node root =>new> Node(>100>);> >root.left =>new> Node(>20>);> >root.right =>new> Node(>200>);> >root.left.left =>new> Node(>10>);> >root.left.right =>new> Node(>30>);> >root.right.left =>new> Node(>150>);> >root.right.right =>new> Node(>300>);> >// Function call> >System.out.print(>'Preorder Traversal: '>);> >printPreorder(root);> >}> }> |
nœud de liste Java
>
>
C#
// Include namespace system> using> System;> // Class describing a node of tree> public> class> Node> {> >public> int> data;> >public> Node left;> >public> Node right;> >public> Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> public> class> GFG> {> >// Preorder Traversal> >public> static> void> printPreorder(Node node)> >{> >if> (node ==>null>)> >{> >return>;> >}> >// Traverse left subtree> >GFG.printPreorder(node.left);> >// Traverse right subtree> >GFG.printPreorder(node.right);> >// Visit node> >Console.Write(node.data.ToString() +>' '>);> >}> >public> static> void> Main(String[] args)> >{> >// Build the tree> >var> root =>new> Node(100);> >root.left =>new> Node(20);> >root.right =>new> Node(200);> >root.left.left =>new> Node(10);> >root.left.right =>new> Node(30);> >root.right.left =>new> Node(150);> >root.right.right =>new> Node(300);> >// Function call> >Console.Write(>'Preorder Traversal: '>);> >GFG.printPreorder(root);> >}> }> |
>
>
Python3
class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Preorder Traversal> def> printPostOrder(node):> >if> node>is> None>:> >return> ># Traverse left subtree> >printPostOrder(node.left)> ># Traverse right subtree> >printPostOrder(node.right)> > ># Visit Node> >print>(node.data, end>=> ' '>)> # Driver code> if> __name__>=>=> '__main__'>:> ># Build the tree> >root>=> Node(>100>)> >root.left>=> Node(>20>)> >root.right>=> Node(>200>)> >root.left.left>=> Node(>10>)> >root.left.right>=> Node(>30>)> >root.right.left>=> Node(>150>)> >root.right.right>=> Node(>300>)> ># Function call> >print>(>'Postorder Traversal: '>, end>=> '')> >printPostOrder(root)> |
>
>
Javascript
class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Preorder Traversal> function> printPostOrder(node) {> >if> (node ===>null>) {> >return>;> >}> >// Traverse left subtree> >printPostOrder(node.left);> >// Traverse right subtree> >printPostOrder(node.right);> >// Visit Node> >console.log(node.data, end =>' '>);> }> // Driver code> // Build the tree> let root =>new> Node(100);> root.left =>new> Node(20);> root.right =>new> Node(200);> root.left.left =>new> Node(10);> root.left.right =>new> Node(30);> root.right.left =>new> Node(150);> root.right.right =>new> Node(300);> // Function call> console.log(>'Postorder Traversal: '>, end =>''>);> printPostOrder(root);> // This code is contributed by akashish__> |
>
>Sortir
PostOrder Traversal: 10 30 20 150 300 200 100>
Complexité temporelle : O(N), où N est le nombre de nœuds.
Espace auxiliaire : O(H), où H est la hauteur de l'arbre