Рубрики

Распечатать обход почтового заказа из заданных обходов Inorder и Preorder

Если заданы обходы бинарного дерева по Inorder и Preorder, выведите обход по Postorder.

Пример:

Input:
Inorder traversal in[] = {4, 2, 5, 1, 3, 6}
Preorder traversal pre[] = {1, 2, 4, 5, 3, 6}

Output:
Postorder traversal is {4, 5, 2, 6, 3, 1}

Trversals в приведенном выше примере представляет следующее дерево

         1
      /    \    
     2       3
   /   \      \
  4     5      6

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

Мы можем напечатать обход по порядку без построения дерева . Идея в том, что root всегда является первым элементом в обходе предварительного заказа, и он должен быть последним элементом в обходе предварительного заказа. Сначала мы рекурсивно печатаем левое поддерево, а затем рекурсивно печатаем правое поддерево. Наконец, распечатайте root. Чтобы найти границы левого и правого поддеревьев в pre [] и в [], мы ищем корень в in [], все элементы перед корнем в in [] являются элементами левого поддерева, а все элементы после корня являются элементами правого поддерева. В pre [] все элементы после индекса корня в in [] являются элементами правого поддерева. И элементы перед индексом (включая элемент в индексе и исключая первый элемент) являются элементами левого поддерева.

C ++

// C ++ программа для печати обхода по порядку и порядку обхода
#include <iostream>

using namespace std;

  
// Полезная функция для поиска x в arr [] размера n

int search(int arr[], int x, int n)

{

    for (int i = 0; i < n; i++)

        if (arr[i] == x)

            return i;

    return -1;

}

  
// Печатает прохождение заказа по заданному обходу и порядку

void printPostOrder(int in[], int pre[], int n)

{

    // Первый элемент в pre [] всегда root, ищем его

    // in in [] чтобы найти левое и правое поддеревья

    int root = search(in, pre[0], n);

  

    // Если левое поддерево не пустое, вывести левое поддерево

    if (root != 0)

        printPostOrder(in, pre + 1, root);

  

    // Если правое поддерево не пустое, вывести правое поддерево

    if (root != n - 1)

        printPostOrder(in + root + 1, pre + root + 1, n - root - 1);

  

    // Печать корня

    cout << pre[0] << " ";

}

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

int main()

{

    int in[] = { 4, 2, 5, 1, 3, 6 };

    int pre[] = { 1, 2, 4, 5, 3, 6 };

    int n = sizeof(in) / sizeof(in[0]);

    cout << "Postorder traversal " << endl;

    printPostOrder(in, pre, n);

    return 0;

}

Джава

// Java программа для печати по почте
// обход из предзаказа и
// порядок обхода

import java.util.Arrays;

  

class GFG

{

  
// Полезная функция для поиска x в arr [] размера n

static int search(int arr[], int x, int n)

{

    for (int i = 0; i < n; i++)

        if (arr[i] == x)

            return i;

    return -1;

}

  
// Печатает прохождение заказа из
// данный обход и предзаказ обхода

static void printPostOrder(int in1[],

                    int pre[], int n)

{

    // Первый элемент в pre []

    // всегда root, ищем его в []

    // найти левое и правое поддеревья

    int root = search(in1, pre[0], n);

  

    // Если левое поддерево не пустое,

    // печать левого поддерева

    if (root != 0)

        printPostOrder(in1, Arrays.copyOfRange(pre, 1, n), root);

  

    // Если правое поддерево не пустое,

    // выводим правильное поддерево

    if (root != n - 1)

        printPostOrder(Arrays.copyOfRange(in1, root+1, n),

            Arrays.copyOfRange(pre, 1+root, n), n - root - 1);

  

    // Печать корня

    System.out.print( pre[0] + " ");

}

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

public static void main(String args[])

{

    int in1[] = { 4, 2, 5, 1, 3, 6 };

    int pre[] = { 1, 2, 4, 5, 3, 6 };

    int n = in1.length;

    System.out.println("Postorder traversal " );

    printPostOrder(in1, pre, n);

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

python3

# Python программа для печати по почте
# обход от предзаказа и
# порядок обхода

def printpostorder(inorder, preorder, n):

    if preorder[0] in inorder:

        root = inorder.index(preorder[0])

          

    if root != 0: # левое поддерево существует

        printpostorder(inorder[:root], 

                       preorder[1:root + 1], 

                       len(inorder[:root]))

      

    if root != n - 1: # существует правильное поддерево

        printpostorder(inorder[root + 1:],  

                       preorder[root + 1:], 

                       len(inorder[root + 1:]))

      

    print preorder[0],

          
Код водителя

inorder = [4, 2, 5, 1, 3, 6];

preorder = [1, 2, 4, 5, 3, 6];

n = len(inorder)

print "Postorder traversal "

printpostorder(inorder, preorder, n)

  
# Этот код предоставлен SaiNath

Выход:

Postorder traversal 
4 5 2 6 3 1

Ниже приведена реализация.

Джава

// Java-программа для печати обхода Postorder из заданного Inorder
// и Предзаказ обходов.

  

public class PrintPost {

    static int preIndex = 0;

    void printPost(int[] in, int[] pre, int inStrt, int inEnd)

    {

        if (inStrt > inEnd) 

            return;        

  

        // Находим индекс следующего элемента в обходе предзаказа в

        // чтобы.

        int inIndex = search(in, inStrt, inEnd, pre[preIndex++]);

  

        // пройти левое дерево

        printPost(in, pre, inStrt, inIndex - 1);

  

        // пройти правое дерево

        printPost(in, pre, inIndex + 1, inEnd);

  

        // печатаем корневой узел в конце обхода

        System.out.print(in[inIndex] + " ");

    }

  

    int search(int[] in, int startIn, int endIn, int data)

    {

        int i = 0;

        for (i = startIn; i < endIn; i++) 

            if (in[i] == data) 

                return i;            

        return i;

    }

  

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

    public static void main(String ars[])

    {

        int in[] = { 4, 2, 5, 1, 3, 6 };

        int pre[] = { 1, 2, 4, 5, 3, 6 };

        int len = in.length;

        PrintPost tree = new PrintPost();

        tree.printPost(in, pre, 0, len - 1);

    }

}

C #

// C # программа для печати Postorder
// обход заданного Inorder
// и Предзаказ обходов.

using System;

  

class GFG

{

public static int preIndex = 0;

public virtual void printPost(int[] arr, int[] pre, 

                              int inStrt, int inEnd)

{

    if (inStrt > inEnd)

    {

        return;

    }

  

    // Находим индекс следующего элемента в предзаказе

    // обход в порядке.

    int inIndex = search(arr, inStrt, inEnd, 

                         pre[preIndex++]);

  

    // пройти левое дерево

    printPost(arr, pre, inStrt, inIndex - 1);

  

    // пройти правое дерево

    printPost(arr, pre, inIndex + 1, inEnd);

  

    // печатаем корневой узел в конце обхода

    Console.Write(arr[inIndex] + " ");

}

  

public virtual int search(int[] arr, int startIn,

                          int endIn, int data)

{

    int i = 0;

    for (i = startIn; i < endIn; i++)

    {

        if (arr[i] == data)

        {

            return i;

        }

    }

    return i;

}

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

public static void Main(string[] ars)

{

    int[] arr = new int[] {4, 2, 5, 1, 3, 6};

    int[] pre = new int[] {1, 2, 4, 5, 3, 6};

    int len = arr.Length;

    GFG tree = new GFG();

    tree.printPost(arr, pre, 0, len - 1);

}
}

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

Выход:

4 5 2 6 3 1

Сложность времени: вышеупомянутая функция посещает каждый узел в массиве. Для каждого посещения он вызывает поиск, который занимает O (n) времени. Следовательно, общая временная сложность функции составляет O (n 2 )

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

Джава

// Java-программа для печати обхода Postorder из
// заданные обходы Inorder и Preorder.

import java.util.*;

  

public class PrintPost { 

    static int preIndex = 0

    void printPost(int[] in, int[] pre, int inStrt,

               int inEnd, HashMap<Integer, Integer> hm) 

    

        if (inStrt > inEnd) 

            return;         

  

        // Находим индекс следующего элемента в обходе предзаказа в

        // чтобы.

        int inIndex = hm.get(pre[preIndex++]); 

  

        // пройти левое дерево

        printPost(in, pre, inStrt, inIndex - 1, hm); 

  

        // пройти правое дерево

        printPost(in, pre, inIndex + 1, inEnd, hm); 

  

        // печатаем корневой узел в конце обхода

        System.out.print(in[inIndex] + " "); 

    

  

    void printPostMain(int[] in, int[] pre) 

    {

        int n = pre.length;

        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)

           hm.put(in[i], i);

             

        printPost(in, pre, 0, n-1, hm);

    }

  

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

    public static void main(String ars[]) 

    

        int in[] = { 4, 2, 5, 1, 3, 6 }; 

        int pre[] = { 1, 2, 4, 5, 3, 6 }; 

        PrintPost tree = new PrintPost(); 

        tree.printPostMain(in, pre); 

    

C #

// C # программа для печати Postorder
// обход заданного Inorder
// и Предзаказ обходов.

using System;

  

class GFG

{

public static int preIndex = 0;

public virtual void printPost(int[] arr, int[] pre, 

                              int inStrt, int inEnd)

{

    if (inStrt > inEnd)

    {

        return;

    }

  

    // Находим индекс следующего элемента в предзаказе

    // обход в порядке.

    int inIndex = search(arr, inStrt, inEnd, 

                         pre[preIndex++]);

  

    // пройти левое дерево

    printPost(arr, pre, inStrt, inIndex - 1);

  

    // пройти правое дерево

    printPost(arr, pre, inIndex + 1, inEnd);

  

    // печатаем корневой узел на

    // конец обхода

    Console.Write(arr[inIndex] + " ");

}

  

public virtual int search(int[] arr, int startIn,

                          int endIn, int data)

{

    int i = 0;

    for (i = startIn; i < endIn; i++)

    {

        if (arr[i] == data)

        {

            return i;

        }

    }

    return i;

}

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

public static void Main(string[] ars)

{

    int[] arr = new int[] {4, 2, 5, 1, 3, 6};

    int[] pre = new int[] {1, 2, 4, 5, 3, 6};

    int len = arr.Length;

    GFG tree = new GFG();

    tree.printPost(arr, pre, 0, len - 1);

}
}

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

Выход:

4 5 2 6 3 1

Временная сложность: O (n)

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

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

Распечатать обход почтового заказа из заданных обходов Inorder и Preorder

0.00 (0%) 0 votes