# 如何从给定的中序和先序遍历中打印后序遍历？

2021年3月26日17:31:18 发表评论 868 次浏览

## 本文概述

``````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}``````

``````1
/    \
2       3
/   \      \
4     5      6``````

## C ++

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

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

``````# Python program to print postorder
# traversal from preorder and
# inorder traversals
def printpostorder(inorder, preorder, n):
if preorder[ 0 ] in inorder:
root = inorder.index(preorder[ 0 ])

if root ! = 0 : # left subtree exists
printpostorder(inorder[:root], preorder[ 1 :root + 1 ], len (inorder[:root]))

if root ! = n - 1 : # right subtree exists
printpostorder(inorder[root + 1 :], preorder[root + 1 :], len (inorder[root + 1 :]))

print preorder[ 0 ], # Driver Code
inorder = [ 4 , 2 , 5 , 1 , 3 , 6 ];
preorder = [ 1 , 2 , 4 , 5 , 3 , 6 ];
n = len (inorder)
print "Postorder traversal "
printpostorder(inorder, preorder, n)

# This code is contributed by SaiNath``````

## C#

``````// 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 29AjayKumar``````

``````Postorder traversal
4 5 2 6 3 1``````

## C ++

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

``````// 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#

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

``4 5 2 6 3 1``

## C ++

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

``````// 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);
}
}``````

## C#

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

``4 5 2 6 3 1``