Przejście w przedsprzedaży jest zdefiniowany jako rodzaj przechodzenie przez drzewo zgodnie z polityką Root-Left-Right, gdzie:
- Najpierw odwiedzany jest węzeł główny poddrzewa.
- Następnie przechodzi się przez lewe poddrzewo.
- W końcu następuje przemierzenie prawego poddrzewa.
Przejście w przedsprzedaży
Algorytm przechodzenia przez drzewo binarne w przedsprzedaży
Algorytm przeglądania zamówień w przedsprzedaży przedstawiono w następujący sposób:
Zamów w przedsprzedaży (root):
- Wykonaj kroki od 2 do 4, aż root != NULL
- Napisz root -> dane
- Zamów w przedsprzedaży (root -> lewy)
- Zamów w przedsprzedaży (root -> prawo)
- Zakończ pętlę
Jak działa przeglądanie drzewa binarnego w przedsprzedaży?
Rozważmy następujące drzewo:
Przykład drzewa binarnego
Jeśli wykonamy przechodzenie w przedsprzedaży w tym drzewie binarnym, wówczas przechodzenie będzie wyglądać następująco:
Krok 1: Najpierw odwiedzony zostanie korzeń, czyli węzeł 1.
Węzeł 1 jest odwiedzany
Krok 2: Następnie przejdź przez lewe poddrzewo. Teraz odwiedzany jest korzeń lewego poddrzewa, tj. odwiedzany jest węzeł 2.
Węzeł 2 jest odwiedzany
Krok 3: Ponownie przemierzane jest lewe poddrzewo węzła 2 i odwiedzany jest korzeń tego poddrzewa, tj. węzeł 4.
Węzeł 4 jest odwiedzany
Krok 4: Nie ma poddrzewa węzła 4 i odwiedzane jest lewe poddrzewo węzła 2. Zatem teraz przejdziemy przez prawe poddrzewo węzła 2 i odwiedzimy korzeń tego poddrzewa, tj. węzeł 5.
Węzeł 5 jest odwiedzany
Krok 5: Odwiedzane jest lewe poddrzewo węzła 1. Zatem teraz przejdziemy przez prawe poddrzewo węzła 1 i odwiedzimy węzeł główny, tj. węzeł 3.
Węzeł 3 jest odwiedzany
Verma dhanashreeKrok 6: Węzeł 3 nie ma lewego poddrzewa. Zatem prawe poddrzewo zostanie przeszukane i odwiedzony zostanie korzeń poddrzewa, tj. węzeł 6. Następnie nie ma już węzła, który nie zostałby jeszcze przebyty. Tak kończy się przeprawa.
Odwiedzane jest całe drzewo
Zatem kolejność przechodzenia węzłów jest następująca 1 -> 2 -> 4 -> 5 -> 3 -> 6 .
Program do implementacji przedpremierowego przeglądania drzewa binarnego
Poniżej znajduje się implementacja kodu przejścia w przedsprzedaży:
C++ // C++ program for preorder 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 preorder traversal void printPreorder(struct Node* node) { if (node == NULL) return; // Deal with the node cout << node->dane<< ' '; // Recur on left subtree printPreorder(node->lewy); // Powtórz w prawym poddrzewie printPreorder(node->right); } // 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<< 'Preorder traversal of binary tree is:
'; printPreorder(root); return 0; }> Jawa // Java program for preorder traversals class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } // Function to print preorder traversal void printPreorder(Node node) { if (node == null) return; // Deal with the node System.out.print(node.data + ' '); // Recur on left subtree printPreorder(node.left); // Recur on right subtree printPreorder(node.right); } // Driver code public static void main(String[] args) { BinaryTree tree = new BinaryTree(); // Constructing the binary tree tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.right = new Node(6); // Function call System.out.println('Preorder traversal of binary tree is: '); tree.printPreorder(tree.root); } }> Python3 # Python program for preorder traversals # Structure of a Binary Tree Node class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Function to print preorder traversal def printPreorder(node): if node is None: return # Deal with the node print(node.data, end=' ') # Recur on left subtree printPreorder(node.left) # Recur on right subtree printPreorder(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('Preorder traversal of binary tree is:') printPreorder(root)> C# // C# program for preorder 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 print preorder traversal public class BinaryTree { // Function to print preorder traversal public static void printPreorder(Node node) { if (node == null) return; // Deal with the node Console.Write(node.data + ' '); // Recur on left subtree printPreorder(node.left); // Recur on right subtree printPreorder(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( 'Preorder traversal of binary tree is: '); printPreorder(root); } } // This code is contributed by Susobhan Akhuli> JavaScript // Structure of a Binary Tree Node class Node { constructor(v) { this.data = v; this.left = null; this.right = null; } } // Function to print preorder traversal function printPreorder(node) { if (node === null) { return; } // Deal with the node console.log(node.data); // Recur on left subtree printPreorder(node.left); // Recur on right subtree printPreorder(node.right); } // Driver code function main() { 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('Preorder traversal of binary tree is:'); printPreorder(root); } main();> Wyjście
Preorder traversal of binary tree is: 1 2 4 5 3 6>
Wyjaśnienie:
Jak działa przeglądanie zamówień w przedsprzedaży
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, Oh) 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 opcji Preorder Travers:
Oto niektóre przypadki użycia przeglądania zamówień w przedsprzedaży:
- Jest to często używane do tworzenia kopii drzewa.
- Przydatne jest również pobranie wyrażenia przedrostkowego z drzewa wyrażeń.
Powiązane artykuły:
- Rodzaje przechodzenia przez drzewa
- Iteracyjne przeglądanie zamówień w przedsprzedaży
- Sprawdź, czy podana tablica może reprezentować przejście BST w przedsprzedaży
- Zamówienia w przedsprzedaży z przesyłek inorderowych i postorderowych
- Znajdź n-ty węzeł w przedsprzedażowym przejściu drzewa binarnego
- Zamów w przedsprzedaży przejście drzewa N-ary