V tomto článku se budeme zabývat procházením stromu v datové struktuře. Termín 'procházení stromem' znamená procházení nebo návštěvu každého uzlu stromu. Existuje jediný způsob, jak procházet lineární datovou strukturou, jako je propojený seznam, fronta a zásobník. Vzhledem k tomu, že existuje několik způsobů, jak procházet stromem, které jsou uvedeny následovně -
- Přechod předobjednávky
- Průjezd nepořádku
- Předání poštovní poukázky
V tomto článku tedy probereme výše uvedené techniky procházení stromu. Nyní začněme diskutovat o způsobech procházení stromů.
Přechod předobjednávky
Tato technika se řídí zásadou „root left right“. To znamená, že nejprve je navštíven kořenový uzel, poté se rekurzivně projde levý podstrom a nakonec se rekurzivně projde pravý podstrom. Protože kořenový uzel prochází před (nebo před) levým a pravým podstromem, nazývá se to procházení předobjednávkou.
Takže v předobjednávkovém průchodu je každý uzel navštíven před oběma jeho podstromy.
Mezi aplikace procházení předobjednávky patří -
- Používá se k vytvoření kopie stromu.
- Lze jej také použít k získání předponového výrazu stromu výrazů.
Algoritmus
Until all nodes of the tree are not visited Step 1 - Visit the root node Step 2 - Traverse the left subtree recursively. Step 3 - Traverse the right subtree recursively.
Příklad
Nyní se podívejme na příklad techniky předobjednávky.
Nyní začněte aplikovat předobjednávku na výše uvedený strom. Nejprve projdeme kořenový uzel A; poté se přesuňte do jeho levého podstromu B , který bude také procházet v předobjednávkách.
Takže pro levý podstrom B nejprve kořenový uzel B je překročen sám; poté jeho levý podstrom D je projetá. Od uzlu D nemá žádné děti, přesuňte se do pravého podstromu A . Protože uzel E také nemá žádné potomky, je procházení levého podstromu kořenového uzlu A dokončeno.
odstranit první znak excel
Nyní přejděte k pravému podstromu kořenového uzlu A, což je C. Takže pro pravý podstrom C nejprve kořenový uzel C prošel sám sebe; poté jeho levý podstrom F je projetá. Od uzlu F nemá žádné děti, přesuňte se do pravého podstromu G . Protože uzel G také nemá žádné potomky, procházení pravého podstromu kořenového uzlu A je dokončeno.
Proto jsou procházeny všechny uzly stromu. Takže výstupem procházení předobjednávky výše uvedeného stromu je -
A → B → D → E → C → F → G
Chcete-li se dozvědět více o předobjednávkovém průchodu v datové struktuře, můžete kliknout na odkaz Přechod předobjednávky .
Předání poštovní poukázky
Tato technika se řídí zásadou 'levý-pravý kořen'. To znamená, že se projde první levý podstrom kořenového uzlu, poté rekurzivně projde pravý podstrom a nakonec se projde kořenový uzel. Protože kořenový uzel prochází po (nebo po) levém a pravém podstromu, nazývá se to procházení postorderu.
Takže při procházení postorderu je každý uzel navštíven po obou svých podstromech.
Aplikace postorder traversal zahrnují -
- Používá se k odstranění stromu.
- Může být také použit k získání postfixového výrazu stromu výrazů.
Algoritmus
zobrazit skryté aplikace
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Traverse the right subtree recursively. Step 3 - Visit the root node.
Příklad
Nyní se podívejme na příklad techniky postorder traversal.
Nyní začněte aplikovat postorder traversal na výše uvedený strom. Nejprve projdeme levý podstrom B, kterým se bude procházet v postorderu. Poté projdeme správným podstromem C v postorderu. A konečně kořenový uzel výše uvedeného stromu, tj. A , je projetá.
Takže pro levý podstrom B nejprve jeho levý podstrom D je projetá. Od uzlu D nemá žádné děti, přejděte přes pravý podstrom A . Protože uzel E také nemá žádné potomky, přesuňte se do kořenového uzlu B. Po projetí uzlem B, procházení levého podstromu kořenového uzlu A je dokončeno.
Nyní přejděte k pravému podstromu kořenového uzlu A, což je C. Takže pro pravý podstrom C nejprve jeho levý podstrom F je projetá. Od uzlu F nemá žádné děti, přejděte přes pravý podstrom G . Protože uzel G také nemá žádné potomky, proto konečně kořen pravého podstromu, tj. C, je projetá. Procházení pravého podstromu kořenového uzlu A je dokončeno.
Nakonec projděte kořenový uzel daného stromu, tj. A . Po projetí kořenového uzlu je postorderový průchod daného stromu dokončen.
Proto jsou procházeny všechny uzly stromu. Takže výstup postorder traversal výše uvedeného stromu je -
co je zpracování výjimek v Javě
D → E → B → F → G → C → A
Chcete-li se dozvědět více o postorder traversal v datové struktuře, můžete kliknout na odkaz Předání poštovní poukázky .
Průjezd nepořádku
Tato technika se řídí zásadou „levý kořen vpravo“. To znamená, že po projití kořenového uzlu je navštíven první levý podstrom a nakonec pravý podstrom. Protože kořenový uzel prochází mezi levým a pravým podstromem, nazývá se procházení bez pořadí.
Takže při procházení v pořadí je každý uzel navštíven mezi svými podstromy.
Aplikace Inorder traversal zahrnují -
- Používá se k získání uzlů BST v rostoucím pořadí.
- Lze jej také použít k získání předponového výrazu stromu výrazů.
Algoritmus
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Visit the root node. Step 3 - Traverse the right subtree recursively.
Příklad
Nyní se podívejme na příklad techniky Inorder traversal.
Nyní začněte na výše uvedeném stromě aplikovat procházení v pořadí. Nejprve projdeme levý podstrom B které budou procházet v pořadí. Poté projdeme kořenový uzel A . A nakonec ten správný podstrom C je překročen v pořadí.
vyhledávací algoritmy
Takže pro levý podstrom B , nejprve jeho levý podstrom D je projetá. Od uzlu D nemá žádné děti, takže po jejím projetí uzel B bude procházet a konečně pravý podstrom uzlu B, tzn A , je projetá. Uzel E také nemá žádné děti; proto je procházení levého podstromu kořenového uzlu A dokončeno.
Poté projděte kořenový uzel daného stromu, tj. A .
Nakonec přejděte k pravému podstromu kořenového uzlu A, což je C. Takže pro pravý podstrom C; nejprve jeho levý podstrom F je projetá. Od uzlu F nemá žádné děti, node C bude procházet a nakonec pravý podstrom uzlu C, tj. G , je projetá. Uzel G také nemá žádné potomky; proto je procházení pravého podstromu kořenového uzlu A dokončeno.
Když jsou procházeny všechny uzly stromu, je neřadové procházení daného stromu dokončeno. Výstupem procházení pořadí výše uvedeného stromu je -
D → B → E → A → F → C → G
Chcete-li se dozvědět více o procházení pořadí v datové struktuře, můžete kliknout na odkaz Inorder Traversal .
Složitost technik procházení stromů
Výše diskutovaná časová složitost technik procházení stromů je Na) , kde 'n' je velikost binárního stromu.
Zatímco prostorová složitost technik procházení stromů diskutovaná výše je O(1) pokud neuvažujeme velikost zásobníku pro volání funkcí. Jinak prostorová náročnost těchto technik je Ach) , kde 'h' je výška stromu.
Implementace Tree traversal
Nyní se podívejme na implementaci výše diskutovaných technik pomocí různých programovacích jazyků.
převod data na řetězec
Program: Napište program pro implementaci technik procházení stromů v C.
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } int main() { struct node* root = createNode(36); root->left = createNode(26); root->right = createNode(46); root->left->left = createNode(21); root->left->right = createNode(31); root->left->left->left = createNode(11); root->left->left->right = createNode(24); root->right->left = createNode(41); root->right->right = createNode(56); root->right->right->left = createNode(51); root->right->right->right = createNode(66); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); printf('
The Inorder traversal of given binary tree is -
'); traverseInorder(root); printf('
The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } Výstup
Program: Napište program pro implementaci technik procházení stromů v C#.
using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Preorder traversal of given binary tree is - '); bt.traversePreorder(); Console.WriteLine(); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); Console.WriteLine(); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } Výstup
Program: Napište program pro implementaci technik procházení stromů v C++.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<right); } *function to traverse the nodes of binary tree in postorder* void traversepostorder(struct node* root) { if (root="=" null) return; traversepostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); cout<<'
inorder traverseinorder(root); postorder traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-6.webp" alt="Tree Traversal"> <p> <strong>Program:</strong> Write a program to implement tree traversal techniques in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class Tree { Node root; /* root of the tree */ Tree() { root = null; } /*function to print the nodes of given binary in Preorder*/ void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } /*function to print the nodes of given binary in Inorder*/ void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } /*function to print the nodes of given binary in Postorder*/ void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { Tree pt = new Tree(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println('
'); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println('
'); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-7.webp" alt="Tree Traversal"> <h2>Conclusion</h2> <p>In this article, we have discussed the different types of tree traversal techniques: preorder traversal, inorder traversal, and postorder traversal. We have seen these techniques along with algorithm, example, complexity, and implementation in C, C++, C#, and java.</p> <p>So, that's all about the article. Hope it will be helpful and informative to you.</p> <hr></'
></'></'></'> Výstup
Po provedení výše uvedeného kódu bude výstupem -
Závěr
V tomto článku jsme diskutovali o různých typech technik procházení stromem: procházení před objednávkou, procházení v pořadí a procházení postorderu. Viděli jsme tyto techniky spolu s algoritmem, příkladem, složitostí a implementací v C, C++, C# a Java.
Tak to je k článku vše. Doufám, že to pro vás bude užitečné a informativní.