Imprimir passagem de pedido de encomenda a partir de dados de pedido de encomenda e passagens de pedido
Dados os percursos Inorder e Preorder de uma árvore binária, imprima o percurso Postorder.
Exemplo:
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}
As travessias no exemplo acima representam a seguinte árvore
1
/ \
2 3
/ \ \
4 5 6
Um método ingênuo é primeiro construir a árvore e, em seguida, usar o método recursivo simples para imprimir o percurso pós-ordem da árvore construída.
Podemos imprimir o percurso do postorder sem construir a árvore . A ideia é que a raiz é sempre o primeiro item na travessia de pré-pedido e deve ser o último item na travessia de pós-pedido. Primeiro imprimimos recursivamente a subárvore esquerda, depois imprimimos recursivamente a subárvore direita. Finalmente, imprima a raiz. Para encontrar os limites das subárvores esquerda e direita em pre [] e em [], buscamos raiz em [], todos os elementos antes da raiz em [] são elementos da subárvore esquerda e todos os elementos após a raiz são elementos da subárvore direita. Em pre [], todos os elementos após o índice da raiz em [] são elementos da subárvore direita. E os elementos antes do índice (incluindo o elemento no índice e excluindo o primeiro elemento) são elementos da subárvore esquerda.
// C++ program to print postorder traversal from preorder and inorder traversals
#include <iostream>
using namespace std;
// A utility function to search x in arr[] of size n
int search(int arr[], int x, int n)
{
for (int i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
// Prints postorder traversal from given inorder and preorder traversals
void printPostOrder(int in[], int pre[], int n)
{
// The first element in pre[] is always root, search it
// in in[] to find left and right subtrees
int root = search(in, pre[0], n);
// If left subtree is not empty, print left subtree
if (root != 0)
printPostOrder(in, pre + 1, root);
// If right subtree is not empty, print right subtree
if (root != n - 1)
printPostOrder(in + root + 1, pre + root + 1, n - root - 1);
// Print root
cout << pre[0] << " ";
}
// Driver program to test above functions
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 program to print postorder
// traversal from preorder and
// inorder traversals
import java.util.Arrays;
class GFG
{
// A utility function to search x in arr[] of size 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;
}
// Prints postorder traversal from
// given inorder and preorder traversals
static void printPostOrder(int in1[],
int pre[], int n)
{
// The first element in pre[] is
// always root, search it in in[]
// to find left and right subtrees
int root = search(in1, pre[0], n);
// If left subtree is not empty,
// print left subtree
if (root != 0)
printPostOrder(in1, Arrays.copyOfRange(pre, 1, n), root);
// If right subtree is not empty,
// print right subtree
if (root != n - 1)
printPostOrder(Arrays.copyOfRange(in1, root+1, n),
Arrays.copyOfRange(pre, 1+root, n), n - root - 1);
// Print root
System.out.print( pre[0] + " ");
}
// Driver code
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);
}
}
// This code is contributed by Arnab Kundu# Python3 program to print postorder
# traversal from preorder and inorder
# traversals
# A utility function to search x in
# arr[] of size n
def search(arr, x, n):
for i in range(n):
if (arr[i] == x):
return i
return -1
# Prints postorder traversal from
# given inorder and preorder traversals
def printPostOrder(In, pre, n):
# The first element in pre[] is always
# root, search it in in[] to find left
# and right subtrees
root = search(In, pre[0], n)
# If left subtree is not empty,
# print left subtree
if (root != 0):
printPostOrder(In, pre[1:n], root)
# If right subtree is not empty,
# print right subtree
if (root != n - 1):
printPostOrder(In[root + 1 : n],
pre[root + 1 : n],
n - root - 1)
# Print root
print(pre[0], end = " ")
# Driver code
In = [ 4, 2, 5, 1, 3, 6 ]
pre = [ 1, 2, 4, 5, 3, 6 ]
n = len(In)
print("Postorder traversal ")
printPostOrder(In, pre, n)
# This code is contributed by avanitrachhadiya2155// C# program to print postorder
// traversal from preorder and
// inorder traversals
using System;
class GFG
{
// A utility function to search x
// in []arr of size 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;
}
// Prints postorder traversal from
// given inorder and preorder traversals
static void printPostOrder(int []in1,
int []pre, int n)
{
// The first element in pre[] is
// always root, search it in in[]
// to find left and right subtrees
int root = search(in1, pre[0], n);
// If left subtree is not empty,
// print left subtree
int []ar;
if (root != 0)
{
ar = new int[n - 1];
Array.Copy(pre, 1, ar, 0, n - 1);
printPostOrder(in1, ar, root);
}
// If right subtree is not empty,
// print right subtree
if (root != n - 1)
{
ar = new int[n - (root + 1)];
Array.Copy(in1, root + 1, ar, 0,
n - (root + 1));
int []ar1 = new int[n - (root + 1)];
Array.Copy(pre, root + 1, ar1, 0,
n - (root + 1));
printPostOrder(ar, ar1, n - root - 1);
}
// Print root
Console.Write(pre[0] + " ");
}
// Driver code
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;
Console.WriteLine("Postorder traversal " );
printPostOrder(in1, pre, n);
}
}
// This code is contributed by 29AjayKumarSaída:
Travessia do Postorder 4 5 2 6 3 1
Abaixo está a implementação.
// C++ program to print Postorder
// traversal from given Inorder
// and Preorder traversals.
#include <iostream>
using namespace std;
int preIndex = 0;
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;
}
void printPost(int arr[], int pre[],int inStrt, int inEnd)
{
if (inStrt > inEnd)
{
return;
}
// Find index of next item in preorder
// traversal in inorder.
int inIndex = search(arr, inStrt, inEnd,pre[preIndex++]);
// traverse left tree
printPost(arr, pre, inStrt, inIndex - 1);
// traverse right tree
printPost(arr, pre, inIndex + 1, inEnd);
// print root node at the end of traversal
cout << arr[inIndex] << " ";
}
// Driver code
int main()
{
int arr[] = {4, 2, 5, 1, 3, 6};
int pre[] = {1, 2, 4, 5, 3, 6};
int len = sizeof(arr)/sizeof(arr[0]);
printPost(arr, pre, 0, len - 1);
}
// This code is contributed by SHUBHAMSINGH10// Java program to print Postorder traversal from given Inorder
// and Preorder traversals.
public class PrintPost {
static int preIndex = 0;
void printPost(int[] in, int[] pre, int inStrt, int inEnd)
{
if (inStrt > inEnd)
return;
// Find index of next item in preorder traversal in
// inorder.
int inIndex = search(in, inStrt, inEnd, pre[preIndex++]);
// traverse left tree
printPost(in, pre, inStrt, inIndex - 1);
// traverse right tree
printPost(in, pre, inIndex + 1, inEnd);
// print root node at the end of traversal
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;
}
// Driver code
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# program to print Postorder
// traversal from given Inorder
// and Preorder traversals.
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;
}
// Find index of next item in preorder
// traversal in inorder.
int inIndex = search(arr, inStrt, inEnd,
pre[preIndex++]);
// traverse left tree
printPost(arr, pre, inStrt, inIndex - 1);
// traverse right tree
printPost(arr, pre, inIndex + 1, inEnd);
// print root node at the end of traversal
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;
}
// Driver code
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);
}
}
// This code is contributed by Shrikant13<script>
// JavaScript program to print Postorder
// traversal from given Inorder
// and Preorder traversals.
class GFG {
constructor() {
this.preIndex = 0;
}
printPost(arr, pre, inStrt, inEnd) {
if (inStrt > inEnd) {
return;
}
// Find index of next item in preorder
// traversal in inorder.
var inIndex = this.search(arr, inStrt, inEnd,
pre[this.preIndex++]);
// traverse left tree
this.printPost(arr, pre, inStrt, inIndex - 1);
// traverse right tree
this.printPost(arr, pre, inIndex + 1, inEnd);
// print root node at the end of traversal
document.write(arr[inIndex] + " ");
}
search(arr, startIn, endIn, data) {
var i = 0;
for (i = startIn; i < endIn; i++) {
if (arr[i] == data) {
return i;
}
}
return i;
}
}
// Driver code
var arr = [4, 2, 5, 1, 3, 6];
var pre = [1, 2, 4, 5, 3, 6];
var len = arr.length;
var tree = new GFG();
tree.printPost(arr, pre, 0, len - 1);
</script>Saída:
4 5 2 6 3 1
Complexidade de tempo: a função acima visita todos os nós da array. Para cada visita, ele chama a pesquisa que leva tempo O (n). Portanto, a complexidade de tempo geral da função é O (n 2 )
A solução acima pode ser otimizada usando hashing. Usamos um HashMap para armazenar elementos e seus índices para que possamos encontrar rapidamente o índice de um elemento.
// C++ program to print Postorder traversal from
// given Inorder and Preorder traversals.
#include<bits/stdc++.h>
using namespace std;
int preIndex = 0;
void printPost(int in[], int pre[], int inStrt,
int inEnd, map<int, int> hm)
{
if (inStrt > inEnd)
return;
// Find index of next item in preorder traversal in
// inorder.
int inIndex = hm[pre[preIndex++]];
// traverse left tree
printPost(in, pre, inStrt, inIndex - 1, hm);
// traverse right tree
printPost(in, pre, inIndex + 1, inEnd, hm);
// print root node at the end of traversal
cout << in[inIndex] << " ";
}
void printPostMain(int in[], int pre[],int n)
{
map<int,int> hm ;
for (int i = 0; i < n; i++)
hm[in[i]] = i;
printPost(in, pre, 0, n - 1, hm);
}
// Driver code
int main()
{
int in[] = { 4, 2, 5, 1, 3, 6 };
int pre[] = { 1, 2, 4, 5, 3, 6 };
int n = sizeof(pre)/sizeof(pre[0]);
printPostMain(in, pre, n);
return 0;
}
// This code is contributed by Arnab Kundu// Java program to print Postorder traversal from
// given Inorder and Preorder traversals.
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;
// Find index of next item in preorder traversal in
// inorder.
int inIndex = hm.get(pre[preIndex++]);
// traverse left tree
printPost(in, pre, inStrt, inIndex - 1, hm);
// traverse right tree
printPost(in, pre, inIndex + 1, inEnd, hm);
// print root node at the end of traversal
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);
}
// Driver code
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);
}
}# Python3 program to prPostorder traversal from
# given Inorder and Preorder traversals.
def printPost(inn, pre, inStrt, inEnd):
global preIndex, hm
if (inStrt > inEnd):
return
# Find index of next item in preorder traversal in
# inorder.
inIndex = hm[pre[preIndex]]
preIndex += 1
# traverse left tree
printPost(inn, pre, inStrt, inIndex - 1)
# traverse right tree
printPost(inn, pre, inIndex + 1, inEnd)
# prroot node at the end of traversal
print(inn[inIndex], end = " ")
def printPostMain(inn, pre, n):
for i in range(n):
hm[inn[i]] = i
printPost(inn, pre, 0, n - 1)
# Driver code
if __name__ == '__main__':
hm = {}
preIndex = 0
inn = [4, 2, 5, 1, 3, 6]
pre = [1, 2, 4, 5, 3, 6]
n = len(pre)
printPostMain(inn, pre, n)
# This code is contributed by mohit kumar 29// C# program to print Postorder
// traversal from given Inorder
// and Preorder traversals.
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;
}
// Find index of next item in preorder
// traversal in inorder.
int inIndex = search(arr, inStrt, inEnd,
pre[preIndex++]);
// traverse left tree
printPost(arr, pre, inStrt, inIndex - 1);
// traverse right tree
printPost(arr, pre, inIndex + 1, inEnd);
// print root node at the
// end of traversal
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;
}
// Driver code
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);
}
}
// This code is contributed by Shrikant13<script>
// Javascript program to print
// Postorder traversal from given
// Inorder and Preorder traversals.
let preIndex = 0;
function printPost(In, pre, inStrt, inEnd, hm)
{
if (inStrt > inEnd)
return;
// Find index of next item in
// preorder traversal in inorder.
let inIndex = hm.get(pre[preIndex++]);
// Traverse left tree
printPost(In, pre, inStrt, inIndex - 1, hm);
// Traverse right tree
printPost(In, pre, inIndex + 1, inEnd, hm);
// Print root node at the end of traversal
document.write(In[inIndex] + " ");
}
function printPostMain(In, pre)
{
let n = pre.length;
let hm = new Map();
for(let i = 0; i < n; i++)
hm.set(In[i], i);
printPost(In, pre, 0, n - 1, hm);
}
// Driver code
let In = [ 4, 2, 5, 1, 3, 6 ];
let pre = [ 1, 2, 4, 5, 3, 6 ];
printPostMain(In, pre);
// This code is contributed by unknown2108
</script>Saída:
4 5 2 6 3 1
Complexidade de tempo: O (n)
Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
