logo

TechCodeview

Binārā koka pārvietošanās priekšpasūtīšana

Iepriekšpasūtīšanas šķērsošana ir definēts kā veids koku šķērsošana kas atbilst saknes-kreisās-labās puses politikai, kur:

  • Vispirms tiek apmeklēts apakškoka saknes mezgls.
  • Pēc tam tiek šķērsots kreisais apakškoks.
  • Beidzot tiek šķērsots labais apakškoks.
Iepriekšpasūtīšanas šķērsošana

Iepriekšpasūtīšanas šķērsošana

Algoritms binārā koka priekšpasūtīšanai

Iepriekšpasūtīšanas šķērsošanas algoritms ir parādīts šādi:



Priekšpasūtīšana (sakne):

  1. Izpildiet 2. līdz 4. darbību, līdz sakne != NULL
  2. Ierakstiet saknes -> datus
  3. Priekšpasūtīšana (sakne —> pa kreisi)
  4. Priekšpasūtīšana (sakne —> pa labi)
  5. Beigu cilpa

Kā darbojas binārā koka priekšpasūtīšanas caurlaide?

Apsveriet šādu koku:

python ierakstiet json failā
Binārā koka piemērs

Binārā koka piemērs

savienojuma virkne java

Ja mēs šajā binārajā kokā veicam priekšpasūtīšanas šķērsošanu, tad pārvietošanās būs šāda:

1. darbība: Sākumā tiks apmeklēta sakne, t.i., mezgls 1.

1. mezgls ir apmeklēts

1. mezgls ir apmeklēts

2. darbība: Pēc tam pārejiet pa kreiso apakškoku. Tagad tiek apmeklēta kreisā apakškoka sakne, t.i., tiek apmeklēts 2. mezgls.

2. mezgls ir apmeklēts

2. mezgls ir apmeklēts

noķer un izmēģini javu

3. darbība: Atkal tiek šķērsots 2. mezgla kreisais apakškoks un tiek apmeklēta šī apakškoka sakne, t.i., 4. mezgls.

4. mezgls ir apmeklēts

4. mezgls ir apmeklēts

4. darbība: Nav 4. apakškoka un tiek apmeklēts 2. mezgla kreisais apakškoks. Tātad tagad tiks šķērsots 2. mezgla labais apakškoks un tiks apmeklēta šī apakškoka sakne, t.i., 5. mezgls.

5. mezgls ir apmeklēts

5. mezgls ir apmeklēts

5. darbība: Tiek apmeklēts 1. mezgla kreisais apakškoks. Tātad tagad tiks šķērsots 1. mezgla labais apakškoks un tiek apmeklēts saknes mezgls, t.i., mezgls 3.

java masīvi
3. mezgls ir apmeklēts

3. mezgls ir apmeklēts

6. darbība: 3. mezglam nav kreisā apakškoka. Tātad tiks šķērsots pareizais apakškoks un tiks apmeklēta apakškoka sakne, t.i., mezgls 6. Pēc tam nav neviena mezgla, kas vēl nebūtu šķērsots. Tātad šķērsošana beidzas.

Tiek apmeklēts viss koks

Tiek apmeklēts viss koks

Tātad mezglu šķērsošanas secība ir 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

Programma binārā koka priekšpasūtīšanas šķērsošanas ieviešanai

Tālāk ir sniegta priekšpasūtīšanas šķērsošanas koda ieviešana.

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->datus<< ' ';  // Recur on left subtree  printPreorder(node->pa kreisi);  // Atkārtoties labajā apakškokā printPreorder(node->right); } // Draivera kods int main() { struct Node* root = new Node(1);  sakne->pa kreisi = jauns mezgls(2);  sakne->pa labi = jauns mezgls (3);  sakne->pa kreisi->pa kreisi = jauns mezgls(4);  sakne->pa kreisi->pa labi = jauns mezgls(5);  sakne->labais->pa labi = jauns mezgls(6);  // Funkcijas izsaukums<< '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();>
Izvade 
Preorder traversal of binary tree is: 1 2 4 5 3 6>

Paskaidrojums:

Kā darbojas priekšpasūtīšanas šķērsošana

Kā darbojas priekšpasūtīšanas šķērsošana

Sarežģītības analīze:

Laika sarežģītība: O(N), kur N ir kopējais mezglu skaits. Jo tas vismaz vienu reizi šķērso visus mezglus.
Palīgtelpa:

mākslīgais intelekts un viedie aģenti
  • O(1) ja netiek ņemta vērā rekursijas steka vieta.
  • Citādi, O(h) kur h ir koka augstums
  • Sliktākajā gadījumā, h var būt tāds pats kā N (kad koks ir šķībs koks)
  • Labākajā gadījumā, h var būt tāds pats kā mierīgs (kad koks ir pilnīgs koks)

Priekšpasūtīšanas aprites izmantošanas gadījumi:

Daži priekšpasūtīšanas izmantošanas gadījumi ir šādi:

  • To bieži izmanto, lai izveidotu koka kopiju.
  • Ir arī noderīgi iegūt prefiksa izteiksmi no izteiksmju koka.

Saistītie raksti:

  • Koku šķērsošanas veidi
  • Iteratīva priekšpasūtīšanas šķērsošana
  • Pārbaudiet, vai dotais masīvs var attēlot BST priekšpasūtīšanas šķērsošanu
  • Priekšpasūtīšana no inorder un postorder traversals
  • Atrodiet n-to mezglu binārā koka priekšpasūtīšanas šķērsošanā
  • Iepriekš pasūtiet N-veida koka šķērsošanu