Рубрики

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

Мы обсудили простой итеративный обход пост-заказа с использованием двух стеков в предыдущем посте. В этом посте обсуждается подход только с одним стеком.

Идея состоит в том, чтобы переместиться вниз к крайнему левому узлу, используя левый указатель. При перемещении вниз нажмите root и правый дочерний элемент root в стек. Как только мы дойдем до самого левого узла, распечатайте его, если у него нет правого потомка. Если у него есть правильный дочерний элемент, измените корень так, чтобы правильный дочерний элемент обрабатывался ранее.

Ниже приводится подробный алгоритм.

1.1 Create an empty stack
2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child 
       is at top of stack, then remove the right child from stack,
       push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

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

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

1. Right child of 1 exists. 
   Push 3 to stack. Push 1 to stack. Move to left child.
        Stack: 3, 1

2. Right child of 2 exists. 
   Push 5 to stack. Push 2 to stack. Move to left child.
        Stack: 3, 1, 5, 2

3. Right child of 4 doesn't exist. '
   Push 4 to stack. Move to left child.
        Stack: 3, 1, 5, 2, 4

4. Current node is NULL. 
   Pop 4 from stack. Right child of 4 doesn't exist. 
   Print 4. Set current node to NULL.
        Stack: 3, 1, 5, 2

5. Current node is NULL. 
    Pop 2 from stack. Since right child of 2 equals stack top element, 
    pop 5 from stack. Now push 2 to stack.     
    Move current node to right child of 2 i.e. 5
        Stack: 3, 1, 2

6. Right child of 5 doesn't exist. Push 5 to stack. Move to left child.
        Stack: 3, 1, 2, 5

7. Current node is NULL. Pop 5 from stack. Right child of 5 doesn't exist. 
   Print 5. Set current node to NULL.
        Stack: 3, 1, 2

8. Current node is NULL. Pop 2 from stack. 
   Right child of 2 is not equal to stack top element. 
   Print 2. Set current node to NULL.
        Stack: 3, 1

9. Current node is NULL. Pop 1 from stack. 
   Since right child of 1 equals stack top element, pop 3 from stack. 
   Now push 1 to stack. Move current node to right child of 1 i.e. 3
        Stack: 1

10. Repeat the same as above steps and Print 6, 7 and 3. 
    Pop 1 and Print 1.

С

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


Выход:

Post Order traversal of binary tree is
[4, 5, 2, 6, 7, 3, 1]

Способ 2:
Нажмите прямо на корневой узел два раза, двигаясь влево. Во время всплывающего окна, если вы обнаружите, что stack top () совпадает с root, перейдите к root-> right, иначе print root.

// Простая 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);

    }

}

Выход:

Post Order traversal of binary tree is:
4, 5, 2, 6, 7, 3, 1

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

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

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

0.00 (0%) 0 votes