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

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

本文概述

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

例子：

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

一种天真的方法首先要构造树, 然后使用简单的递归方法来打印所构造树的事后遍历。

我们可以在不构造树的情况下打印订单遍历。这个想法是, 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#

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

时间复杂度：上面的函数访问数组中的每个节点。对于每次访问, 它都会调用搜索, 这需要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#

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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: