ZAMÓW W PRZEDSPRZEDAŻY PRZEMIERZANIE DRZEWA BINARNEGO - TECHCODEVIEW.COM

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

Krok 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# 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)