Итеративный обход постпорядка | Комплект 3

Опубликовано: 23 Января, 2022

Мы видели разные способы выполнения обхода после порядка на двоичных деревьях.

  • Обход почтового заказа.
  • Итеративный обход после порядка с использованием двух стеков.
  • Итеративный обход с использованием одного стека.

Вот еще один способ итеративного выполнения обхода двоичного дерева с использованием одного стека.

Обратите внимание на терминологию, приведенную ниже:

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
Output:
4 5 2 3 1

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022