Nieuporządkowane przechodzenie drzewa binarnego
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);> > }> }> |
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
