FORHÅNDSBESTILL TRAVERSAL OF BINARY TREE

Forhåndsbestill traversering er definert som en type kryssing av tre som følger Root-venstre-høyre-policyen der:

Rotnoden til undertreet besøkes først.
Deretter krysses det venstre undertreet.
Til slutt krysses det høyre undertreet.

Forhåndsbestill traversering

Algoritme for forhåndsbestillingsgjennomgang av binært tre

Algoritmen for forhåndsbestillingsgjennomgang vises som følger:

Forhåndsbestilling (root):
hvordan endre streng til int

Følg trinn 2 til 4 til root != NULL
Skriv root -> data
Forhåndsbestilling (root -> venstre)
Forhåndsbestilling (root -> høyre)
Sluttløkke

Hvordan fungerer Preorder Traversal of Binary Tree?

Tenk på følgende tre:

Eksempel på binært tre

Hvis vi utfører en forhåndsbestillingsgjennomgang i dette binære treet, vil gjennomgangen være som følger:

Trinn 1: Først vil roten bli besøkt, dvs. node 1.

Node 1 er besøkt

Steg 2: Etter dette, gå i venstre undertre. Nå er roten til det venstre undertreet besøkt, dvs. node 2 er besøkt.

Node 2 er besøkt

Trinn 3: Igjen krysses det venstre undertreet til node 2 og roten til det undertreet, dvs. node 4 besøkes.

Node 4 er besøkt

Trinn 4: Det er ikke noe undertre av 4 og venstre undertre av node 2 besøkes. Så nå vil det høyre undertreet til node 2 krysses og roten til det undertreet, dvs. node 5 vil bli besøkt.

Node 5 er besøkt

Trinn 5: Det venstre undertreet til node 1 besøkes. Så nå vil det høyre undertreet til node 1 krysses og rotnoden, dvs. node 3, besøkes.

Node 3 er besøkt

Trinn 6: Node 3 har ikke noe venstre undertre. Så det høyre undertreet vil bli krysset og roten til undertreet, dvs. node 6 vil bli besøkt. Etter det er det ingen node som ennå ikke er krysset. Så kryssingen slutter.

Hele treet er besøkt

Så rekkefølgen for kryssing av noder er 1 -> 2 -> 4 -> 5 -> 3 -> 6 .
greibach normal form

Program for å implementere forhåndsbestillingsgjennomgang av binært tre

Nedenfor er kodeimplementeringen av forhåndsbestillingsgjennomgangen:

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->data<< ' ';  // Recur on left subtree  printPreorder(node->venstre);  // Gjenta på høyre undertre printPreorder(node->right); } // Driverkode int main() { struct Node* root = new Node(1);  root->venstre = ny node(2);  root->right = ny node(3);  root->venstre->venstre = ny node(4);  root->venstre->høyre = ny node(5);  root->right->right = ny node(6);  // Function call 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# 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();>

Produksjon

Preorder traversal of binary tree is: 1 2 4 5 3 6>

Forklaring:

Hvordan forhåndsbestillingsovergang fungerer

Kompleksitetsanalyse:

Tidskompleksitet: O(N) hvor N er det totale antallet noder. Fordi den krysser alle nodene minst én gang.
Hjelpeplass:

O(1) hvis ingen rekursjonsstabelplass vurderes.
Ellers, Åh) hvor h er høyden på treet
I verste fall, h kan være det samme som N (når treet er et skjevt tre)
I beste fall, h kan være det samme som rolig (når treet er et komplett tre)

Bruk tilfeller av forhåndsbestillingsgjennomgang:

Noen brukstilfeller for kryssing av forhåndsbestilling er:

Dette brukes ofte til å lage en kopi av et tre.
Det er også nyttig å hente prefiksuttrykket fra et uttrykkstre.

Relaterte artikler:

Typer trekryssing
Iterativ forhåndsbestillingsgjennomgang
Sjekk om gitt matrise kan representere forhåndsbestillingsgjennomgang av BST
Forhåndsbestill fra inorder og postorder traversaler
Finn n'te node i forhåndsbestillingsgjennomgang av et binært tre
Forhåndsbestill traversering av et N-ært tre