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

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):

Izpildiet 2. līdz 4. darbību, līdz sakne != NULL

Ierakstiet saknes -> datus

Priekšpasūtīšana (sakne —> pa kreisi)

Priekšpasūtīšana (sakne —> pa labi)

Beigu cilpa

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

Apsveriet šādu koku:

Binārā koka piemērs

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

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

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. 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. 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.

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

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

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:

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)