logo

TechCodeview

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

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
  1. Følg trinn 2 til 4 til root != NULL
  2. Skriv root -> data
  3. Forhåndsbestilling (root -> venstre)
  4. Forhåndsbestilling (root -> høyre)
  5. Sluttløkke

Hvordan fungerer Preorder Traversal of Binary Tree?

Tenk på følgende tre:

Eksempel på binært 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

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

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

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

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

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

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

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