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

// C-программа для итеративного обхода после заказа с использованием одного стека
#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--];

}

struct Node* peek(struct Stack* stack)

{

    if (isEmpty(stack))

        return NULL;

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

}

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

void postOrderIterative(struct Node* root)

{

    // Проверка на пустое дерево

    if (root == NULL)

        return;

    struct Stack* stack = createStack(MAX_SIZE);

    do

    {

        // Перейти к крайнему левому узлу

        while (root)

        {

            // Вставить правого потомка root, а затем root в стек.

            if (root->right)

                push(stack, root->right);

            push(stack, root);

            // Установить root как левого потомка root

            root = root->left;

        }

        // извлекаем элемент из стека и устанавливаем его как root

        root = pop(stack);

        // Если у всплывающего элемента есть правильный дочерний элемент, а правильный дочерний элемент не

        // обработано еще, затем убедитесь, что правый потомок обработан до root

        if (root->right && peek(stack) == root->right)

        {

            pop(stack);  // удаляем правого потомка из стека

            push(stack, root);  // толкаем корень обратно в стек

            root = root->right; // изменить корень так, чтобы право

                                // потомок обрабатывается следующим

        }

        else  // Остальное вывести данные root и установить root в NULL

        {

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

            root = NULL;

        }

    } while (!isEmpty(stack));

}

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

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);

    printf("Post order traversal of binary tree is :\n");

    printf("[");

    postOrderIterative(root);

    printf("]");

    return 0;

}

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

import java.util.ArrayList;

import java.util.Stack;

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

class Node 

{

    int data;

    Node left, right;

    Node(int item) 

    {

        data = item;

        left = right;

    }

}

class BinaryTree 

{

    Node root;

    ArrayList<Integer> list = new ArrayList<Integer>();

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

    // данного двоичного дерева

    ArrayList<Integer> postOrderIterative(Node node) 

    {

        Stack<Node> S = new Stack<Node>();

        // Проверка на пустое дерево

        if (node == null)

            return list;

        S.push(node);

        Node prev = null;

        while (!S.isEmpty()) 

        {

            Node current = S.peek();

            / * спуститься по дереву в поисках листа и обработать его

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

            if (prev == null || prev.left == current || 

                                        prev.right == current) 

            {

                if (current.left != null)

                    S.push(current.left);

                else if (current.right != null)

                    S.push(current.right);

                else

                {

                    S.pop();

                    list.add(current.data);

                }

                / * подняться по дереву от левого узла, если ребенок прав

                   поместите его в стек, иначе обработайте parent и pop

                   стек *

            } 

            else if (current.left == prev) 

            {

                if (current.right != null)

                    S.push(current.right);

                else 

                {

                    S.pop();

                    list.add(current.data);

                }

                / * подняться по дереву от правого узла и после возвращения

                 из правого узла обрабатывает родительский и попсовый стек * /

            } 

            else if (current.right == prev) 

            {

                S.pop();

                list.add(current.data);

            }

            prev = current;

        }

        return list;

    }

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

    public static void main(String args[]) 

    {

     BinaryTree tree = new BinaryTree();

        // Давайте создадим деревья, показанные на диаграмме выше

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

        ArrayList<Integer> mylist = tree.postOrderIterative(tree.root);

        System.out.println("Post order traversal of binary tree is :");

        System.out.println(mylist);

    }

}

   
// Этот код предоставлен Mayank Jaiswal

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

  
# Хранит ответ

ans = []

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

class Node:

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def peek(stack):

    if len(stack) > 0:

        return stack[-1]

    return None

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

def postOrderIterative(root):

    # Проверить на пустое дерево

    if root is None:

        return 

    stack = []

    while(True):

        while (root):

             # Нажмите правый дочерний элемент root, а затем root в стек

             if root.right is not None:

                stack.append(root.right)

             stack.append(root)

             # Установить root как левого потомка root

             root = root.left

        # Вытолкнуть предмет из стека и установить его как root

        root = stack.pop()

        # Если у всплывающего элемента есть правильный дочерний элемент и

        # правый ребенок еще не обработан, тогда убедитесь

        # правый потомок обрабатывается до корня

        if (root.right is not None and 

            peek(stack) == root.right):

            stack.pop() # Удалить правого потомка из стека

            stack.append(root) # Вернуть корень в стек

            root = root.right # изменить корень так, чтобы

                             # Right Childis обрабатывается следующим

        # Иначе распечатать данные root и установить root как None

        else:

            ans.append(root.data) 

            root = None

        if (len(stack) <= 0):

                break

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

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)

print "Post Order traversal of binary tree is"

postOrderIterative(root)

print ans

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

// Простая Java-программа для печати PostOrder Traversal (Iterative)

import java.util.Stack;

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

class Node 

{

    int data;

    Node left, right;

    Node(int item) 

    {

        data = item;

        left = right;

    }

}

  
// создаем класс почтового перевода

class PostOrder

{ 

    Node root;

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

    // данного двоичного дерева

    private void postOrderIterative(Node root) {

        Stack<Node> stack = new Stack<>();

        while(true) {

            while(root != null) {

                stack.push(root);

                stack.push(root);

                root = root.left;

            }

            // Проверка на пустой стек

            if(stack.empty()) return;

            root = stack.pop();

            if(!stack.empty() && stack.peek() == root) root = root.right;

            else {

                System.out.print(root.data + " "); root = null;

            }

        }

    }

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

    public static void main(String args[]) 

    {

    PostOrder tree = new PostOrder();

        // Давайте создадим деревья, показанные на диаграмме выше

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

        System.out.println("Post order traversal of binary tree is :");

        tree.postOrderIterative(tree.root);

    }

}