Prehod prednaročila binarnega drevesa
Prehod po prednaročilu je opredeljena kot vrsta prečenje drevesa ki sledi pravilniku Root-Left-Right, kjer:
- Najprej se obišče korensko vozlišče poddrevesa.
- Nato se prečka levo poddrevo.
- Končno se prečka desno poddrevo.
Prehod po prednaročilu
Algoritem za prehod pred naročilom binarnega drevesa
Algoritem za prečkanje prednaročila je prikazan takole:
Prednaročilo (root):
- Sledite korakom od 2 do 4, dokler ni root != NULL
- Zapiši root -> data
- Prednaročilo (root -> levo)
- Prednaročilo (root -> desno)
- Končna zanka
Kako deluje prehod pred naročilom binarnega drevesa?
Razmislite o naslednjem drevesu:
Primer binarnega drevesa
Če v tem binarnem drevesu izvedemo prehod pred naročilom, bo prehod naslednji:
Korak 1: Najprej bo obiskan koren, tj. vozlišče 1.
Vozlišče 1 je obiskano
2. korak: Za tem prečkajte levo poddrevo. Zdaj je obiskan koren levega poddrevesa, tj. obiskano je vozlišče 2.
Vozlišče 2 je obiskano
3. korak: Spet se prečka levo poddrevo vozlišča 2 in obišče se koren tega poddrevesa, tj. vozlišče 4.
Vozlišče 4 je obiskano
4. korak: Ni poddrevesa 4 in levo poddrevo vozlišča 2 je obiskano. Tako bo zdaj prečkano desno poddrevo vozlišča 2 in obiskano bo koren tega poddrevesa, tj. vozlišče 5.
Vozlišče 5 je obiskano
5. korak: Obiskano je levo poddrevo vozlišča 1. Tako bo zdaj prečkano desno poddrevo vozlišča 1 in obiskano je korensko vozlišče, tj. vozlišče 3.
Vozlišče 3 je obiskano
6. korak: Vozlišče 3 nima levega poddrevesa. Tako bo prečkano desno poddrevo in obiskano bo koren poddrevesa, tj. vozlišče 6. Po tem ni vozlišča, ki še ni prečkano. Tako se prehod konča.
Obišče se celotno drevo
Vrstni red prečkanja vozlišč je torej 1 -> 2 -> 4 -> 5 -> 3 -> 6 .
Program za izvajanje prednaročilnega prehoda binarnega drevesa
Spodaj je implementacija kode prečkanja prednaročila:
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->podatke < < ' '; // Recur on left subtree printPreorder(node->levo); // Ponavlja se na desnem poddrevesu printPreorder(node->right); } // Koda gonilnika int main() { struct Node* root = new Node(1); root->left = novo vozlišče(2); root->desno = novo vozlišče(3); root->left->left = novo vozlišče(4); koren->levo->desno = novo vozlišče(5); root->desno->desno = novo vozlišče(6); // Klic funkcije 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(); Izhod
Preorder traversal of binary tree is: 1 2 4 5 3 6
Pojasnilo:
Kako deluje prehod pred naročilom
Analiza kompleksnosti:
Časovna zapletenost: O(N), kjer je N skupno število vozlišč. Ker vsaj enkrat prečka vsa vozlišča.
Pomožni prostor:
- O(1) če se ne upošteva prostor sklada rekurzije.
- Sicer pa O(h) kjer je h višina drevesa
- V najslabšem primeru h lahko enako kot n (ko je drevo poševno drevo)
- V najboljšem primeru h lahko enako kot miren (ko je drevo popolno drevo)
Primeri uporabe prehoda pred naročilom:
Nekateri primeri uporabe prečkanja prednaročila so:
- To se pogosto uporablja za ustvarjanje kopije drevesa.
- Koristno je tudi pridobiti predponski izraz iz izraznega drevesa.
Povezani članki:
- Vrste prečkanja dreves
- Iterativno prečkanje prednaročila
- Preverite, ali dana matrika lahko predstavlja prehod BST pred naročilom
- Prednaročilo iz prečkanja v vrstnem redu in po vrstnem redu
- Poiščite n-to vozlišče v prečkanju prednaročila binarnega drevesa
- Prednaročilno prečkanje N-arnega drevesa
