TRAVERSAREA ÎN ORDINE A ARBORELUI BINAR

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

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: