У овом чланку ћемо разговарати о обиласку постордера у структури података.
Линеарне структуре података као што су стек, низ, ред, итд., имају само један начин да прелазе податке. Али у хијерархијској структури података као што је дрво , постоји више начина да се пређу подаци. Дакле, овде ћемо разговарати о другом начину преласка структуре података стабла, тј. обилазак поштом . Постордер прелазак је једна од техника преласка која се користи за посету чвору у стаблу. Следи принцип ЛРН (лево-десно-чвор) . Постордер траверсал се користи за добијање постфиксног израза дрвета.
Следећи кораци се користе за обављање обиласка постордера:
- Пређите лево подстабло рекурзивним позивањем функције постордер.
- Пређите десно подстабло рекурзивним позивањем функције постордер.
- Приступите делу података тренутног чвора.
Техника преласка по налогу прати Лево Десно Корен политика. Овде, леви десни корен значи да се прво прелази лево подстабло коренског чвора, затим десно подстабло, и на крају, прелази се преко коренског чвора. Овде, само име Постордер сугерише да ће се коренски чвор дрвета коначно прећи.
Алгоритам
Сада, да видимо алгоритам обиласка постордера.
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}
Сложеност преласка наруџбине поште
Временска сложеност обиласка постордера је На) , где је 'н' величина бинарног стабла.
Док је просторна сложеност обиласка постордера О(1) , ако не узмемо у обзир величину стека за позиве функција. Иначе, просторна сложеност обиласка постордера је О(х) , где је 'х' висина дрвета.
Имплементација обиласка поште
Сада, да видимо имплементацију обиласка постордера у различитим програмским језицима.
Програм: Напишите програм за имплементацију обиласка постордера у језику Ц.
#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; } Излаз
Програм: Напишите програм за имплементацију обиласка постордера у Ц++.
#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></'
></'> Излаз
Након извршења горњег кода, излаз ће бити -
Програм: Напишите програм за имплементацију обиласка постордера у Јави.
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(); } } Излаз
предности и мане технологије
Након извршења горњег кода, излаз ће бити -
Дакле, то је све о чланку. Надамо се да ће вам чланак бити користан и информативан.