Parcurs în ordine este definit ca un tip de tehnica traversării arborilor care urmează modelul Stânga-Rădăcină-Dreapta, astfel încât:
- Subarborele din stânga este parcurs mai întâi
- Apoi se parcurge nodul rădăcină pentru acel subarbor
- În cele din urmă, subarborele din dreapta este parcurs
Parcurs în ordine
css wrap text
Algoritm pentru traversarea în ordine a arborelui binar
Algoritmul pentru traversarea în ordine este prezentat după cum urmează:
În ordine (rădăcină):
- Urmați pașii de la 2 la 4 până la root != NULL
- În ordine (rădăcină -> stânga)
- Scrieți rădăcină -> date
- În ordine (rădăcină -> dreapta)
- Sfârșit bucla
Cum funcționează traversarea în ordine a arborelui binar?
Luați în considerare următorul arbore:
Exemplu de arbore binar
Dacă efectuăm o traversare în ordine în acest arbore binar, atunci traversarea va fi după cum urmează:
Pasul 1: Parcursul va merge de la 1 la subarborele din stânga, adică 2, apoi de la 2 la rădăcina din stânga, adică 4. Acum 4 nu are subarborele stâng, deci va fi vizitat. De asemenea, nu are niciun subarbore corect. Deci, nu mai trece de la 4
Nodul 4 este vizitat
Pasul 2: Deoarece subarborele din stânga al lui 2 este vizitat complet, acum citește datele nodului 2 înainte de a trece la subarborele din dreapta.
Nodul 2 este vizitat
Pasul 3: Acum va fi traversat subarborele din dreapta al lui 2, adică treceți la nodul 5. Pentru nodul 5 nu există subarborele din stânga, deci este vizitat și după aceea, traversarea revine deoarece nu există subarborele din dreapta al nodului 5.
Nodul 5 este vizitat
Pasul 4: Așa cum este subarborele din stânga al nodului 1, rădăcina însăși, adică nodul 1 va fi vizitată.
Nodul 1 este vizitat
Pasul 5: Subarborele din stânga al nodului 1 și nodul însuși este vizitat. Deci acum va fi traversat subarborele din dreapta al lui 1, adică mutați la nodul 3. Deoarece nodul 3 nu are subarborele din stânga, acesta este vizitat.
Nodul 3 este vizitat
Pasul 6: Se vizitează subarborele din stânga al nodului 3 și nodul însuși. Deci, traversați spre subarborele din dreapta și vizitați nodul 6. Acum traversarea se termină pe măsură ce toate nodurile sunt parcurse.
Arborele complet este străbătut
Deci ordinea de parcurgere a nodurilor este 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Program pentru implementarea traversării în ordine a arborelui binar:
Mai jos este implementarea codului traversării în ordine:
C++
// C++ program for inorder 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 inorder traversal> void> printInorder(>struct> Node* node)> {> >if> (node == NULL)> >return>;> >// First recur on left subtree> >printInorder(node->stânga);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->dreapta); } // Cod driver int main() { struct Node* root = new Node(1); root->left = nou Nod(2); root->right = nou Nod(3); rădăcină->stânga->stânga = nou Nod(4); rădăcină->stânga->dreapta = nou Nod(5); root->right->right = Nod nou(6); // Apelul funcției cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
Java
// Java program for inorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> >int> data;> >Node left, right;> >Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Main class> class> GFG {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >System.out.print(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> main(String[] args)> >{> >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> >System.out.println(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> // This code is contributed by prasad264> |
>
>
Python3
# Structure of a Binary Tree Node> class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Function to print inorder traversal> def> printInorder(node):> >if> node>is> None>:> >return> ># First recur on left subtree> >printInorder(node.left)> ># Now deal with the node> >print>(node.data, end>=>' '>)> ># Then recur on right subtree> >printInorder(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>(>'Inorder traversal of binary tree is:'>)> >printInorder(root)> |
>
>
C#
// C# program for inorder 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 store and print inorder traversal> public> class> BinaryTree {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >Console.Write(node.data +>' '>);> >// Then recur on right subtree> >printInorder(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(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> |
>
>
Javascript
// JavaScript program for inorder traversals> // Structure of a Binary Tree Node> class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Function to print inorder traversal> function> printInorder(node) {> >if> (node ===>null>) {> >return>;> >}> > >// First recur on left subtree> >printInorder(node.left);> > >// Now deal with the node> >console.log(node.data);> > >// Then recur on right subtree> >printInorder(node.right);> }> // Driver code> 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(>'Inorder traversal of binary tree is: '>);> printInorder(root);> |
>
>Ieșire
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Explicaţie:
Cum funcționează traversarea în ordine
Analiza complexității:
Complexitatea timpului: O(N) unde N este numărul total de noduri. Pentru că străbate toate nodurile cel puțin o dată.
Spațiu auxiliar: O(1) dacă nu se ia în considerare spațiul stivei recursive. În caz contrar, O(h) unde h este înălțimea copacului
- În cel mai rău caz, h poate fi la fel ca N (când copacul este un copac înclinat)
- În cel mai bun caz, h poate fi la fel ca calm (când copacul este un copac complet)
Cazuri de utilizare ale traversării în ordine:
În cazul BST (Arborele de căutare binar), dacă în orice moment este nevoie de a obține nodurile în ordine nedescrescătoare, cea mai bună modalitate este de a implementa o traversare în ordine.
Articole similare:
- Tipuri de traversări ale copacilor
- Parcurs iterativ în ordine
- Construiți arbore binar din parcurgerea precomanda și în ordine
- Parcursul Morris pentru parcurgerea în ordine a arborelui
- Parcurs în ordine fără recursivitate