У цій статті ми обговоримо постпорядковий обхід у структурі даних.
Лінійні структури даних, такі як стек, масив, черга тощо, мають лише один спосіб обходу даних. Але в ієрархічній структурі даних, наприклад дерево , існує кілька способів перегляду даних. Отже, тут ми обговоримо інший спосіб обходу структури даних дерева, тобто проходження замовлення поштою . Обхід після замовлення є одним із методів обходу, який використовується для відвідування вузла в дереві. Це слідує принципу LRN (лівий-правий вузол) . Постпорядковий обхід використовується для отримання постфіксного виразу дерева.
Для виконання обходу після замовлення використовуються наступні кроки:
рядок до символу java
- Перейдіть до лівого піддерева, викликавши функцію postorder рекурсивно.
- Перейдіть до правого піддерева, викликавши функцію postorder рекурсивно.
- Доступ до частини даних поточного вузла.
Техніка обходу пост-замовлення наступна Лівий правий корінь політики. Тут «лівий правий корінь» означає, що спочатку обходиться ліве піддерево кореневого вузла, потім праве піддерево і, нарешті, обходиться кореневий вузол. Тут сама назва Postorder говорить про те, що кореневий вузол дерева нарешті буде переміщено.
Алгоритм
Тепер давайте подивимося на алгоритм обходу postorder.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: POSTORDER(TREE -> LEFT) Step 3: POSTORDER(TREE -> RIGHT) Step 4: Write TREE -> DATA [END OF LOOP] Step 5: END
Приклад обходу замовлення поштою
Тепер розглянемо приклад обходу після замовлення. На прикладі буде простіше зрозуміти процес обходу постордера.
Вузли з жовтим кольором ще не відвідуються. Тепер ми обійдемо вузли вищезазначеного дерева за допомогою обходу після порядку.
- Тут 40 є кореневим вузлом. Спершу ми відвідаємо ліве піддерево 40, тобто 30. Вузол 30 також буде проходити в постпорядку. 25 є лівим піддеревом 30, тому воно також обходиться в порядку посту. Тоді 15 є лівим піддеревом 25. Але 15 не має піддерева, отже друк 15 і рухайтеся до правого піддерева 25.
- 28 є правим піддеревом 25, і воно не має дітей. Так, друк 28 .
- тепер, надрукувати 25 , і обхід після замовлення для 25 закінчено.
- Далі перейдіть до правого піддерева 30. 35 є правим піддеревом 30, і воно не має дітей. Так, надрукувати 35 .
- Після того, надрукувати 30 , і обхід після замовлення для 30 закінчено. Отже, ліве піддерево заданого бінарного дерева обходиться.
- Тепер перейдіть до правого піддерева 40, тобто 50, і воно також пройде в порядку пост. 45 є лівим піддеревом 50, і воно не має дітей. Так, надрукувати 45 і рухайтеся до правого піддерева 50.
- 60 є правим піддеревом 50, яке також буде проходитися в порядку пост. 55 — ліве піддерево 60, яке не має дітей. Так, надрукувати 55 .
- тепер, друк 70, що є правим піддеревом 60.
- тепер, друк 60, і обхід пост-замовлення для 60 завершено.
- тепер, друк 50, і обхід пост-замовлення для 50 завершено.
- Нарешті, друк 40, який є кореневим вузлом даного бінарного дерева, і обхід пост-замовлення для вузла 40 завершено.
Остаточним результатом, який ми отримаємо після обходу після замовлення, є -
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Складність обходу поштового замовлення
Часова складність обходу після замовлення становить O(n) , де 'n' — розмір бінарного дерева.
У той час як просторова складність обходу постпорядку є O(1) , якщо не враховувати розмір стека для викликів функцій. В іншому випадку складність обходу постпорядку становить простір O(h) , де «h» — висота дерева.
Реалізація обходу поштового замовлення
Тепер давайте подивимося реалізацію postorder traversal різними мовами програмування.
програма: Напишіть програму для реалізації postorder traversal мовою C.
поличні собаки
#include #include struct node { s 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 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(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } Вихід
програма: Напишіть програму для реалізації postorder traversal на 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 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 postorder traversal of given binary tree is -
'; traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-14.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in C#.</p> <pre> 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 traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } 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 Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } </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/85/postorder-traversal-15.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); 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 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/85/postorder-traversal-16.webp" alt="Postorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Вихід
Після виконання наведеного вище коду результатом буде -
програма: Напишіть програму для реалізації postorder traversal на Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); 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 Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } Вихід
Після виконання наведеного вище коду результатом буде -
Отже, це все про статтю. Сподіваюся, стаття буде для вас корисною та інформативною.
функції arduino