Рубрики

Итеративный обход почтового заказа | Набор 1 (с использованием двух стеков)

Мы обсудили итеративный порядок и итеративный обход предзаказа . В этом посте обсуждается итеративный обход по порядку, который является более сложным, чем два других обхода (из-за своей природы нехвостовой рекурсии , есть дополнительный оператор после последнего рекурсивного вызова самого себя). Однако обратный порядок заказа может быть легко выполнен с использованием двух стеков. Идея состоит в том, чтобы перенести обратный обход пост-заказа в стек. Как только мы получим в стеке обратный обход пост-заказа, мы можем просто вытолкнуть все элементы один за другим из стека и распечатать их; этот порядок печати будет в почтовом порядке из-за свойства стеков LIFO. Теперь вопрос в том, как получить элементы стека обратного порядка в стеке — для этого используется второй стек. Например, в следующем дереве нам нужно получить 1, 3, 7, 6, 2, 5, 4 в стеке. Если внимательнее взглянуть на эту последовательность, мы можем заметить, что эта последовательность очень похожа на обход предзаказа. Единственное отличие состоит в том, что правого потомка посещают раньше, чем левого, и, следовательно, последовательность «корень справа налево» вместо «корень слева направо». Итак, мы можем сделать что-то вроде итеративного обхода предварительного заказа со следующими отличиями:
а) Вместо того, чтобы печатать предмет, мы помещаем его в стек.
б) Толкаем левое поддерево перед правым поддеревом.

Ниже приводится полный алгоритм. После шага 2 мы получаем обратный ход прохождения заказа во втором стеке. Мы используем первый стек, чтобы получить правильный порядок.

1. Push root to first stack.
2. Loop while first stack is not empty
   2.1 Pop a node from first stack and push it to second stack
   2.2 Push left and right children of the popped node to first stack
3. Print contents of second stack

Давайте рассмотрим следующее дерево

Ниже приведены шаги для распечатки обхода по порядку вышеупомянутого дерева с использованием двух стеков.

1. Push 1 to first stack.
      First stack: 1
      Second stack: Empty

2. Pop 1 from first stack and push it to second stack. 
   Push left and right children of 1 to first stack
      First stack: 2, 3
      Second stack: 1

3. Pop 3 from first stack and push it to second stack. 
   Push left and right children of 3 to first stack
      First stack: 2, 6, 7
      Second stack: 1, 3

4. Pop 7 from first stack and push it to second stack.
      First stack: 2, 6
      Second stack: 1, 3, 7

5. Pop 6 from first stack and push it to second stack.
      First stack: 2
      Second stack: 1, 3, 7, 6

6. Pop 2 from first stack and push it to second stack. 
   Push left and right children of 2 to first stack
      First stack: 4, 5
      Second stack: 1, 3, 7, 6, 2

7. Pop 5 from first stack and push it to second stack.
      First stack: 4
      Second stack: 1, 3, 7, 6, 2, 5

8. Pop 4 from first stack and push it to second stack.
      First stack: Empty
      Second stack: 1, 3, 7, 6, 2, 5, 4

The algorithm stops here since there are no more items in the first stack. 
Observe that the contents of second stack are in postorder fashion. Print them. 

Ниже приводится реализация итеративного обхода после заказа с использованием двух стеков.

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Узел дерева

struct Node {

  

    int data;

    Node *left, *right;

};

  
// Функция для создания нового узла с заданными данными

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return node;

}
// Итеративная функция для выполнения пост-заказа
// обход заданного двоичного дерева

void postOrderIterative(Node* root)

{

    if (root == NULL)

        return;

  

    // Создать два стека

    stack<Node *> s1, s2;

  

    // вставляем корень в первый стек

    s1.push(root);

    Node* node;

  

    // Выполнить, пока первый стек не пуст

    while (!s1.empty()) {

        // извлекаем элемент из s1 и помещаем его в s2

        node = s1.top();

        s1.pop();

        s2.push(node);

  

        // толкаем левых и правых детей

        // удаленного элемента в s1

        if (node->left)

            s1.push(node->left);

        if (node->right)

            s1.push(node->right);

    }

  

    // Распечатать все элементы второго стека

    while (!s2.empty()) {

        node = s2.top();

        s2.pop();

        cout << node->data << " ";

    }

}

  
// Код драйвера

int main()

{

    // Построим дерево

    // показано на рисунке выше

    Node* root = NULL;

    root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

  

    postOrderIterative(root);

  

    return 0;

}

С

#include <stdio.h>
#include <stdlib.h>

  
// Максимальный размер стека
#define MAX_SIZE 100

  
// Узел дерева

struct Node {

    int data;

    struct Node *left, *right;

};

  
// Тип стека

struct Stack {

    int size;

    int top;

    struct Node** array;

};

  
// Вспомогательная функция для создания нового узла дерева

struct Node* newNode(int data)

{

    struct Node* node = (struct Node*)malloc(sizeof(struct Node));

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
// Вспомогательная функция для создания стека заданного размера

struct Stack* createStack(int size)

{

    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

    stack->size = size;

    stack->top = -1;

    stack->array = (struct Node**)malloc(stack->size * sizeof(struct Node*));

    return stack;

}

  
// ОСНОВНЫЕ ОПЕРАЦИИ СТЕКА

int isFull(struct Stack* stack)

{

    return stack->top - 1 == stack->size;

}

  

int isEmpty(struct Stack* stack)

{

    return stack->top == -1;

}

  

void push(struct Stack* stack, struct Node* node)

{

    if (isFull(stack))

        return;

    stack->array[++stack->top] = node;

}

  

struct Node* pop(struct Stack* stack)

{

    if (isEmpty(stack))

        return NULL;

    return stack->array[stack->top--];

}

  
// Итеративная функция для выполнения обхода заданного двоичного дерева

void postOrderIterative(struct Node* root)

{

    if (root == NULL)

        return;

  

    // Создать два стека

    struct Stack* s1 = createStack(MAX_SIZE);

    struct Stack* s2 = createStack(MAX_SIZE);

  

    // вставляем корень в первый стек

    push(s1, root);

    struct Node* node;

  

    // Выполнить, пока первый стек не пуст

    while (!isEmpty(s1)) {

        // извлекаем элемент из s1 и помещаем его в s2

        node = pop(s1);

        push(s2, node);

  

        // Перетаскиваем левого и правого потомка удалённого элемента в s1

        if (node->left)

            push(s1, node->left);

        if (node->right)

            push(s1, node->right);

    }

  

    // Распечатать все элементы второго стека

    while (!isEmpty(s2)) {

        node = pop(s2);

        printf("%d ", node->data);

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Построим дерево, показанное на рисунке выше

    struct Node* root = NULL;

    root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

  

    postOrderIterative(root);

  

    return 0;

}

Джава

// Java-программа для итеративного поста
// заказ с использованием двух стеков

  

import java.util.*;

public class IterativePostorder {

  

    static class node {

        int data;

        node left, right;

  

        public node(int data)

        {

            this.data = data;

        }

    }

  

    // Два стека, используемые в объяснении

    static Stack<node> s1, s2;

  

    static void postOrderIterative(node root)

    {

        // Создать два стека

        s1 = new Stack<>();

        s2 = new Stack<>();

  

        if (root == null)

            return;

  

        // вставляем корень в первый стек

        s1.push(root);

  

        // Выполнить, пока первый стек не пуст

        while (!s1.isEmpty()) {

            // извлекаем элемент из s1 и помещаем его в s2

            node temp = s1.pop();

            s2.push(temp);

  

            // толкаем левых и правых детей

            // убрал элемент в s1

            if (temp.left != null)

                s1.push(temp.left);

            if (temp.right != null)

                s1.push(temp.right);

        }

  

        // Распечатать все элементы второго стека

        while (!s2.isEmpty()) {

            node temp = s2.pop();

            System.out.print(temp.data + " ");

        }

    }

  

    public static void main(String[] args)

    {

        // Построим дерево

        // показано на рисунке выше

  

        node root = null;

        root = new node(1);

        root.left = new node(2);

        root.right = new node(3);

        root.left.left = new node(4);

        root.left.right = new node(5);

        root.right.left = new node(6);

        root.right.right = new node(7);

  

        postOrderIterative(root);

    }

}

  
// Этот код предоставлен Rishabh Mahrsee

питон

# Python программа для итеративного заказа
# обход с использованием двух стеков

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Итеративная функция для выполнения заказа
# обход заданного двоичного дерева

def postOrderIterative(root): 

  

    if root is None:

        return        

      

    # Создать два стека

    s1 = []

    s2 = []

      

    # Вставить корень в первый стек

    s1.append(root)

      

    # Запуск пока первый стек не пуст

    while s1:

          

        # Взять предмет из s1 и

        # добавить его в s2

        node = s1.pop()

        s2.append(node)

      

        # Нажмите левую и правую детей

        # убрал предмет на s1

        if node.left:

            s1.append(node.left)

        if node.right:

            s1.append(node.right)

  

        # Распечатать все элементы второго стека

    while s2:

        node = s2.pop()

        print node.data,

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.left = Node(6)

root.right.right = Node(7)

postOrderIterative(root)

C #

// C # программа для итеративного поста
// заказ с использованием двух стеков

using System;

using System.Collections;

public class IterativePostorder {

  

    public class node {

        public int data;

        public node left, right;

  

        public node(int data)

        {

            this.data = data;

        }

    }

  

    // Два стека, используемые в объяснении

    static public Stack s1, s2;

  

    static void postOrderIterative(node root)

    {

        // Создать два стека

        s1 = new Stack();

        s2 = new Stack();

  

        if (root == null)

            return;

  

        // Вставить корень в первый стек

        s1.Push(root);

  

        // Выполнить, пока первый стек не пуст

        while (s1.Count > 0) {

            // извлекаем элемент из s1 и помещаем его в s2

            node temp = (node)s1.Pop();

            s2.Push(temp);

  

            // толкаем левых и правых детей

            // убрал элемент в s1

            if (temp.left != null)

                s1.Push(temp.left);

            if (temp.right != null)

                s1.Push(temp.right);

        }

  

        // Распечатать все элементы второго стека

        while (s2.Count > 0) {

            node temp = (node)s2.Pop();

            Console.Write(temp.data + " ");

        }

    }

  

    public static void Main(String[] args)

    {

        // Построим дерево

        // показано на рисунке выше

  

        node root = null;

        root = new node(1);

        root.left = new node(2);

        root.right = new node(3);

        root.left.left = new node(4);

        root.left.right = new node(5);

        root.right.left = new node(6);

        root.right.right = new node(7);

  

        postOrderIterative(root);

    }

}

  
// Этот код предоставлен Арнабом Кунду


Выход:

4 5 2 6 7 3 1

Ниже приводится обзор вышеупомянутого поста.
Итеративный обход предзаказа может быть легко реализован с использованием двух стеков. Первый стек используется для получения обратного обхода после заказа. Шаги для получения обратного заказа аналогичны итеративному предварительному заказу .

Вам также может понравиться метод, который использует только один стек .

Эта статья составлена Aashish Barnwal . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Итеративный обход почтового заказа | Набор 1 (с использованием двух стеков)

0.00 (0%) 0 votes