如何从给定的中序和先序遍历中打印后序遍历（） _二叉树

本文概述

C ++
Java
Python3
C#
C ++
Java
C#
C ++
Java
C#

给定二叉树的中序遍历和先序遍历, 请打印后序遍历。
例子：

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 /\ 23 /\\ 456

一种天真的方法首先要构造树, 然后使用简单的递归方法来打印所构造树的事后遍历。
我们可以在不构造树的情况下打印订单遍历。这个想法是, root始终是预遍历中的第一项, 它必须是后遍历中的最后一项。我们首先递归打印左子树, 然后递归打印右子树。最后, 打印根目录。要查找pre []和in []中左右子树的边界, 我们搜索in []的根, in []中root之前的所有元素都是左子树的元素, root之后的所有元素都是右子树的元素。在pre []中, in []中的根索引之后的所有元素都是右子树的元素。索引之前的元素(包括索引处的元素, 但不包括第一个元素)是左子树的元素。
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# 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# 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

时间复杂度：上面的函数访问数组中的每个节点。对于每次访问, 它都会调用搜索, 这需要O(n)时间。因此, 该函数的整体时间复杂度为O(n2)
可以使用哈希优化以上解决方案。我们使用HashMap来存储元素及其索引, 以便我们可以快速找到元素的索引。
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# 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

输出如下：