Przeprawa nieuporządkowana jest zdefiniowany jako rodzaj technika przechodzenia przez drzewa który jest zgodny ze wzorem Lewy-Korzeń-Prawy, tak że:
- Najpierw przemierzane jest lewe poddrzewo
- Następnie przechodzi się przez węzeł główny tego poddrzewa
- Na koniec przechodzi się przez prawe poddrzewo
Przeprawa nieuporządkowana
Algorytm nieuporządkowanego przechodzenia drzewa binarnego
Algorytm przejścia w kolejności uporządkowanej przedstawiono w następujący sposób:
Kolejność (korzeń):
- Wykonaj kroki od 2 do 4, aż root != NULL
- Inorder (korzeń -> lewy)
- Napisz root -> dane
- Inorder (korzeń -> prawo)
- Zakończ pętlę
Jak działa Inorder Traversal of Binary Tree?
Rozważmy następujące drzewo:
Przykład drzewa binarnego
Jeśli wykonamy przechodzenie w tym drzewie binarnym w sposób nieuporządkowany, wówczas przechodzenie będzie wyglądało następująco:
Krok 1: Przechodzenie będzie przebiegać od 1 do lewego poddrzewa, tj. 2, następnie od 2 do lewego korzenia poddrzewa, tj. 4. Teraz 4 nie ma lewego poddrzewa, więc zostanie odwiedzone. Nie ma również żadnego prawego poddrzewa. Więc nie będzie więcej przechodzenia od 4
Węzeł 4 jest odwiedzany
Krok 2: Ponieważ lewe poddrzewo 2 zostało całkowicie odwiedzone, teraz odczytuje dane z węzła 2 przed przejściem do prawego poddrzewa.
Węzeł 2 jest odwiedzany
Krok 3: Teraz zostanie przebyte prawe poddrzewo 2, tj. przejdź do węzła 5. Dla węzła 5 nie ma lewego poddrzewa, więc zostaje ono odwiedzone, a następnie przejście powraca, ponieważ nie ma prawego poddrzewa węzła 5.
Węzeł 5 jest odwiedzany
Krok 4: Ponieważ lewe poddrzewo węzła 1 jest odwiedzone, sam korzeń, tj. węzeł 1, zostanie odwiedzony.
Węzeł 1 jest odwiedzany
Krok 5: Odwiedzane jest lewe poddrzewo węzła 1 i sam węzeł. Zatem teraz zostanie przebyte prawe poddrzewo 1, tj. przejdź do węzła 3. Ponieważ węzeł 3 nie ma lewego poddrzewa, zostanie on odwiedzony.
Węzeł 3 jest odwiedzany
Krok 6: Odwiedzane jest lewe poddrzewo węzła 3 i sam węzeł. Przejdź więc do prawego poddrzewa i odwiedź węzeł 6. Teraz przechodzenie kończy się, gdy wszystkie węzły zostaną przebyte.
Całe drzewo jest przemierzane
Zatem kolejność przechodzenia węzłów jest następująca 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Program do implementacji Inorder Traversal of Binary Tree:
Poniżej znajduje się kodowa implementacja przejścia wewnętrznego:
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->lewo);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->Prawidłowy); } // Kod sterownika int main() { struct Node* root = new Node(1); root->left = nowy węzeł(2); root->right = nowy węzeł(3); root->left->left = nowy węzeł(4); root->lewy->prawy = nowy węzeł(5); root->right->right = nowy węzeł(6); // Wywołanie funkcji cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
Jawa
// 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);> >}> }> |
węzeł listy Java
>
>
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);> |
>
>Wyjście
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Wyjaśnienie:
Jak działa przechodzenie wewnątrz uporządkowane
Analiza złożoności:
Złożoność czasowa: O(N) gdzie N jest całkowitą liczbą węzłów. Ponieważ przechodzi przez wszystkie węzły przynajmniej raz.
Przestrzeń pomocnicza: O(1), jeśli nie jest brana pod uwagę przestrzeń stosu rekurencji. W przeciwnym razie O(h) gdzie h jest wysokością drzewa
- W najgorszym wypadku, H może być taki sam jak N (kiedy drzewo jest drzewem przekrzywionym)
- W najlepszym przypadku, H może być taki sam jak spokój (kiedy drzewo jest drzewem kompletnym)
Przypadki użycia Inorder Traversal:
W przypadku BST (Binary Search Tree), jeśli w dowolnym momencie istnieje potrzeba uzyskania węzłów w kolejności niemalejącej, najlepszym sposobem jest wdrożenie przechodzenia w kolejności.
Powiązane artykuły:
- Rodzaje przechodzenia przez drzewa
- Iteracyjne przechodzenie wewnątrz rzędu
- Konstruuj drzewo binarne na podstawie przechodzenia w przedsprzedaży i kolejności
- Przechodzenie Morrisa w celu przejścia przez drzewo w sposób uporządkowany
- Przechodzenie w kolejności bez rekurencji