Итеративный обход постпорядка | Комплект 3
Мы видели разные способы выполнения обхода после порядка на двоичных деревьях.
- Обход почтового заказа.
- Итеративный обход после порядка с использованием двух стеков.
- Итеративный обход с использованием одного стека.
Вот еще один способ итеративного выполнения обхода двоичного дерева с использованием одного стека.
Обратите внимание на терминологию, приведенную ниже:
0 - левый элемент 1 - Правый элемент 2 - Узловой элемент
Ниже приводится подробный алгоритм:
Возьмите стек и выполните следующие операции: 1) Вставьте пару корневых узлов как (узел, 0). 2) Вставьте верхний элемент, чтобы получить пару (Пусть a = node и b переменная) Если b равно 0: Вставьте другую пару как (узел, 1) и Нажмите на левый дочерний элемент как (node-> left, 0) Повторите шаг 2 Иначе Если b равно 1: Вставьте другую пару как (узел, 2) и Нажать правый дочерний элемент узла как (node-> right, 0) Повторите шаг 2 Иначе Если b равно 2: Печать (узел-> данные) 3) Повторите вышеуказанные шаги, пока стек не пуст.
Рассмотрим нижеприведенное двоичное дерево всего с 3 узлами:
Иллюстрация:
1) Толчок (a, 0) Стек - (a, 0) 2) верх = (а, 0) Толчок (а, 1) Нажать (b, 0) Стек - (b, 0) (а, 1) 3) верх = (b, 0) Толчок (b, 1) Стек - (b, 1) (а, 1) 4) верх = (б, 1) Толчок (b, 2) Стек - (b, 2) (а, 1) 5) верх = (б, 2) печать (б) Стек - (a, 1) 6) верх = (а, 1) толкать (а, 2) push (c, 0) Стек - (c, 0) (а, 2) 7) верх = (c, 0) толкнуть (c, 1) Стек - (c, 1) (а, 2) 8) верх = (c, 1) толкнуть (c, 2) Стек - (c, 2) (а, 2) 9) верх = (c, 2) печать (с) Стек - (a, 2) 10) верх = (а, 2) печать (а) Стек - пустой ()
Below is the implementation of the above approach:
C++
// C++ program to print postorder traversal // iteratively #include <bits/stdc++.h> using namespace std; // Binary Tree Node struct Node { int data; struct Node* left; struct Node* right; }; // Helper function to create a // new Binary Tree node struct Node* newNode( int data) { struct Node* node = new Node; node->data = data; node->left = NULL; node->right = NULL; return (node); } // Function to perform postorder // traversal iteratively void iterativePostorder(Node* root) { stack<pair<Node*, int > > st; st.push(make_pair(root, 0)); while (!st.empty()) { struct Node* temp = st.top().first; int b = st.top().second; st.pop(); if (temp == NULL) continue ; if (b == 0) { st.push(make_pair(temp, 1)); if (temp->left != NULL) st.push(make_pair(temp->left, 0)); } else if (b == 1) { st.push(make_pair(temp, 2)); if (temp->right != NULL) st.push(make_pair(temp->right, 0)); } else cout << temp->data << " " ; } } // Driver Code int main() { // Construct the below Binary Tree // 1 // / // 2 3 // / // 4 5 Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); iterativePostorder(root); return 0; } |
Java
// Java program to print postorder traversal // iteratively import java.util.*; class GFG { //pair class static class Pair { Node first; int second; Pair(Node a, int b) { first = a; second = b; } } // Binary Tree Node static class Node { int data; Node left; Node right; }; // Helper function to create a // new Binary Tree node static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = null ; node.right = null ; return (node); } // Function to perform postorder // traversal iteratively static void iterativePostorder(Node root) { Stack<Pair> st = new Stack<Pair>(); st.add( new Pair(root, 0 )); while (st.size() > 0 ) { Node temp = st.peek().first; int b = st.peek().second; st.pop(); if (temp == null ) continue ; if (b == 0 ) { st.add( new Pair(temp, 1 )); if (temp.left != null ) st.add( new Pair(temp.left, 0 )); } else if (b == 1 ) { st.add( new Pair(temp, 2 )); if (temp.right != null ) st.add( new Pair(temp.right, 0 )); } else System.out.print( temp.data + " " ); } } // Driver Code public static void main(String args[]) { // Con the below Binary Tree // 1 // / // 2 3 // / // 4 5 Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); iterativePostorder(root); } } // This code is contributed by Arnab Kundu |
Python
# Python program to print postorder traversal # iteratively # pair class class Pair: def __init__( self , a, b): self .first = a self .second = b # Binary Tree Node class Node : def __init__( self ): self .data = 0 self .left = None self .right = None # Helper function to create a # new Binary Tree node def newNode(data): node = Node() node.data = data node.left = None node.right = None return (node) # Function to perform postorder # traversal iteratively def iterativePostorder( root): st = [] st.append(Pair(root, 0 )) while ( len (st)> 0 ): temp = st[ - 1 ].first b = st[ - 1 ].second st.pop() if (temp = = None ): continue if (b = = 0 ) : st.append(Pair(temp, 1 )) if (temp.left ! = None ): st.append(Pair(temp.left, 0 )) elif (b = = 1 ): st.append(Pair(temp, 2 )) if (temp.right ! = None ): st.append(Pair(temp.right, 0 )) else : print ( temp.data ,end = " " ) # Driver Code # Con the below Binary Tree # 1 # / # 2 3 # / # 4 5 root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) iterativePostorder(root) # This code is contributed by Arnab Kundu |
C#
// C# program to print postorder traversal // iteratively using System; using System.Collections.Generic; class GFG { //pair class public class Pair { public Node first; public int second; public Pair(Node a, int b) { first = a; second = b; } } // Binary Tree Node public class Node { public int data; public Node left; public Node right; }; // Helper function to create a // new Binary Tree node static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = null ; node.right = null ; return (node); } // Function to perform postorder // traversal iteratively static void iterativePostorder(Node root) { Stack<Pair> st = new Stack<Pair>(); st.Push( new Pair(root, 0)); while (st.Count > 0) { Node temp = st.Peek().first; int b = st.Peek().second; st.Pop(); if (temp == null ) continue ; if (b == 0) { st.Push( new Pair(temp, 1)); if (temp.left != null ) st.Push( new Pair(temp.left, 0)); } else if (b == 1) { st.Push( new Pair(temp, 2)); if (temp.right != null ) st.Push( new Pair(temp.right, 0)); } else Console.Write(temp.data + " " ); } } // Driver Code public static void Main(String []args) { // Con the below Binary Tree // 1 // / // 2 3 // / // 4 5 Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); iterativePostorder(root); } } // This code is contributed by 29AjayKumar |
4 5 2 3 1
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.