C ++从树的Preorder和Inorder遍历中打印Postorder遍历

给定树的预排序和有序遍历

例如：给出一棵树

Inorder traversal of the given tree is: - 9, 20, 29, 30, 50, 90, 100, 120Preorder traversal of the given tree is: - 30, 20, 9, 29, 90, 50, 120, 100Postorder traversal of the given tree is: - 9, 29, 20, 50, 100, 120, 90, 30

算法：

众所周知，在遍历遍历中，根始终是第一个元素，因此我们将递归地找到左和右子树，最后找到根，为此，我们必须按顺序搜索左和右子树。首先，我们将按顺序搜索preorder的元素，因为按顺序搜索的元素索引之后的元素是右子树的成员，而索引之前的元素是右子树的元素，而被搜索的元素是该子树的根。

考虑一下程序：

#include<iostream>
using namespace std;

/*Find x in inOrder*/
int search(int arr[],int x,int n)   
{
	int i;
	for(i=0;i<n;i++)
	{
		if(arr[i]==x)
		 return i; /*return the index of the element found*/
	}
	return -1;                      
}

void printPostOrder(int inOrder[],int preOrder[],int n)
{
	int rootNode=search(inOrder,preOrder[0],n);
	if(rootNode)	/*If right subtree is not empty */
	{	
		printPostOrder(inOrder,preOrder+1,rootNode);
	}
	if(rootNode!=n-1)	/*If left subtree is not empty*/
	{	
		printPostOrder(inOrder+rootNode+1,preOrder+rootNode+1,n-rootNode-1);
	}
	cout<<preOrder[0]<<" ";          
}

int main(){
	int inOrder[]={9,20,29,30,50,90,100,120};
	int preOrder[]={30,20,9,29,90,50,120,100};
	
	int n=sizeof(inOrder)/sizeof(inOrder[0]);
	
	cout<<"Post order : ";
	printPostOrder(inOrder,preOrder,n);
	cout<<endl;
	
	return 0;
}

输出结果

Post order : 9 29 20 50 100 120 90 30