logo

TechCodeview

Prehod prednaročila binarnega drevesa

Prehod po prednaročilu je opredeljena kot vrsta prečenje drevesa ki sledi pravilniku Root-Left-Right, kjer:

  • Najprej se obišče korensko vozlišče poddrevesa.
  • Nato se prečka levo poddrevo.
  • Končno se prečka desno poddrevo.
Prehod po prednaročilu

Prehod po prednaročilu

Algoritem za prehod pred naročilom binarnega drevesa

Algoritem za prečkanje prednaročila je prikazan takole:



Prednaročilo (root):

  1. Sledite korakom od 2 do 4, dokler ni root != NULL
  2. Zapiši root -> data
  3. Prednaročilo (root -> levo)
  4. Prednaročilo (root -> desno)
  5. Končna zanka

Kako deluje prehod pred naročilom binarnega drevesa?

Razmislite o naslednjem drevesu:

izjema vrzi javo
Primer binarnega drevesa

Primer binarnega drevesa

povezava java mysql

Če v tem binarnem drevesu izvedemo prehod pred naročilom, bo prehod naslednji:

Korak 1: Najprej bo obiskan koren, tj. vozlišče 1.

Vozlišče 1 je obiskano

Vozlišče 1 je obiskano

2. korak: Za tem prečkajte levo poddrevo. Zdaj je obiskan koren levega poddrevesa, tj. obiskano je vozlišče 2.

Vozlišče 2 je obiskano

Vozlišče 2 je obiskano

java indeks od

3. korak: Spet se prečka levo poddrevo vozlišča 2 in obišče se koren tega poddrevesa, tj. vozlišče 4.

Vozlišče 4 je obiskano

Vozlišče 4 je obiskano

4. korak: Ni poddrevesa 4 in levo poddrevo vozlišča 2 je obiskano. Tako bo zdaj prečkano desno poddrevo vozlišča 2 in obiskano bo koren tega poddrevesa, tj. vozlišče 5.

Vozlišče 5 je obiskano

Vozlišče 5 je obiskano

5. korak: Obiskano je levo poddrevo vozlišča 1. Tako bo zdaj prečkano desno poddrevo vozlišča 1 in obiskano je korensko vozlišče, tj. vozlišče 3.

greatandhra
Vozlišče 3 je obiskano

Vozlišče 3 je obiskano

6. korak: Vozlišče 3 nima levega poddrevesa. Tako bo prečkano desno poddrevo in obiskano bo koren poddrevesa, tj. vozlišče 6. Po tem ni vozlišča, ki še ni prečkano. Tako se prehod konča.

Obišče se celotno drevo

Obišče se celotno drevo

Vrstni red prečkanja vozlišč je torej 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

Program za izvajanje prednaročilnega prehoda binarnega drevesa

Spodaj je implementacija kode prečkanja prednaročila:

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->podatke<< ' ';  // Recur on left subtree  printPreorder(node->levo);  // Ponavlja se na desnem poddrevesu printPreorder(node->right); } // Koda gonilnika int main() { struct Node* root = new Node(1);  root->left = novo vozlišče(2);  root->desno = novo vozlišče(3);  root->left->left = novo vozlišče(4);  koren->levo->desno = novo vozlišče(5);  root->desno->desno = novo vozlišče(6);  // Klic funkcije cout<< 'Preorder traversal of binary tree is: 
';  printPreorder(root);  return 0; }>
Java 
// 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();>
Izhod 
Preorder traversal of binary tree is: 1 2 4 5 3 6>

Pojasnilo:

Kako deluje prehod pred naročilom

Kako deluje prehod pred naročilom

Analiza kompleksnosti:

Časovna zapletenost: O(N), kjer je N skupno število vozlišč. Ker vsaj enkrat prečka vsa vozlišča.
Pomožni prostor:

nadrejeni jquery
  • O(1) če se ne upošteva prostor sklada rekurzije.
  • Sicer pa O(h) kjer je h višina drevesa
  • V najslabšem primeru h lahko enako kot n (ko je drevo poševno drevo)
  • V najboljšem primeru h lahko enako kot miren (ko je drevo popolno drevo)

Primeri uporabe prehoda pred naročilom:

Nekateri primeri uporabe prečkanja prednaročila so:

  • To se pogosto uporablja za ustvarjanje kopije drevesa.
  • Koristno je tudi pridobiti predponski izraz iz izraznega drevesa.

Povezani članki:

  • Vrste prečkanja dreves
  • Iterativno prečkanje prednaročila
  • Preverite, ali dana matrika lahko predstavlja prehod BST pred naročilom
  • Prednaročilo iz prečkanja v vrstnem redu in po vrstnem redu
  • Poiščite n-to vozlišče v prečkanju prednaročila binarnega drevesa
  • Prednaročilno prečkanje N-arnega drevesa