logo

TechCodeview

Förbeställ genomgång av binärt träd

Förbeställ genomgång definieras som en typ av trädpassering som följer Root-Vänster-Höger-policyn där:

urval sortera i java
  • Rotnoden för underträdet besöks först.
  • Sedan korsas det vänstra underträdet.
  • Äntligen korsas det högra underträdet.
Förbeställ genomgång

Förbeställ genomgång

Algoritm för förbeställningsövergång av binärt träd

Algoritmen för genomgång av förbeställning visas enligt följande:



Förbeställning (root):

  1. Följ steg 2 till 4 tills root != NULL
  2. Skriv root -> data
  3. Förbeställning (root -> vänster)
  4. Förbeställ (root -> höger)
  5. Slutslinga

Hur fungerar Preorder Traversal of Binary Tree?

Tänk på följande träd:

Exempel på binärt träd

Exempel på binärt träd

Om vi ​​utför en förbeställningsgenomgång i det här binära trädet, så kommer övergången att vara som följer:

Steg 1: Först kommer roten att besökas, dvs nod 1.

Nod 1 besöks

Nod 1 besöks

Steg 2: Efter detta, gå i det vänstra underträdet. Nu är roten av det vänstra underträdet besökt, dvs nod 2 besöks.

Nod 2 besöks

Nod 2 besöks

alfabet till siffror

Steg 3: Återigen korsas det vänstra underträdet av nod 2 och roten till det underträdet, dvs. nod 4 besöks.

Nod 4 besöks

Nod 4 besöks

Steg 4: Det finns inget underträd av 4 och det vänstra underträdet av nod 2 besöks. Så nu kommer det högra underträdet av nod 2 att korsas och roten till det underträdet, dvs nod 5 kommer att besökas.

Nod 5 besöks

Nod 5 besöks

Steg 5: Det vänstra underträdet av nod 1 besöks. Så nu kommer det högra underträdet av nod 1 att korsas och rotnoden, dvs nod 3 besöks.

sträng till int konvertering i java
Nod 3 besöks

Nod 3 besöks

Steg 6: Nod 3 har inget vänster underträd. Så det högra underträdet kommer att korsas och roten till underträdet, dvs nod 6 kommer att besökas. Efter det finns det ingen nod som ännu inte har passerats. Så övergången slutar.

Hela trädet besöks

Hela trädet besöks

Så ordningen för korsning av noder är 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

java om annat

Program för att implementera förbeställningsövergång av binärt träd

Nedan är kodimplementeringen av förbeställningsgenomgången:

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->vänster);  // Återkommande på höger underträd printPreorder(nod->höger); } // Drivrutinskod int main() { struct Node* root = new Node(1);  root->left = new Node(2);  root->right = new Node(3);  root->left->left = new Node(4);  root->vänster->höger = ny Node(5);  root->right->right = new Node(6);  // Funktionsanrop 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();>
Produktion 
Preorder traversal of binary tree is: 1 2 4 5 3 6>

Förklaring:

Hur förbeställningsövergång fungerar

Hur förbeställningsövergång fungerar

Komplexitetsanalys:

Tidskomplexitet: O(N) där N är det totala antalet noder. Eftersom den korsar alla noder minst en gång.
Hjälputrymme:

  • O(1) om inget rekursionsstackutrymme beaktas.
  • Annat, Åh) där h är höjden på trädet
  • I värsta fall, h kan vara samma som N (när trädet är ett skevt träd)
  • I bästa fall, h kan vara samma som lugna (när trädet är ett komplett träd)

Användningsfall av förbeställningstrafik:

Några användningsfall av förbeställningsövergång är:

  • Detta används ofta för att skapa en kopia av ett träd.
  • Det är också användbart att hämta prefixuttrycket från ett uttrycksträd.

Relaterade artiklar:

  • Typer av trädpassering
  • Iterativ genomgång av förbeställning
  • Kontrollera om given array kan representera förbeställningsgenomgång av BST
  • Preorder from inorder and postorder traversals
  • Hitta den n:te noden i förbeställningsgenomgång av ett binärt träd
  • Förbeställ korsning av ett N-ärt träd