在二叉樹的前序周遊序列中,第一個數字總是樹的根節點的值。中序周遊序列中,根節點的值位于序列的中間,左子樹的結點位于序列的左邊,右子樹的結點位于序列的右邊。是以要掃描中序周遊序列,得到根節點的位置。
在中序周遊序列找到根節點的位置後,則根節點左邊的序列為左子樹的結點,右子樹的結點位于根節點的右邊序列。此時将左右子樹的大小l_size和r_size記錄下來。在前序周遊序列中,左子樹結點即為根節點之後的l_size個結點,右子樹結點為左子樹結點之後的r_size個結點。
實作例程如下,重建後列印二叉樹的後序周遊序列:
#include<iostream>
using namespace std;
struct BinaryTree{
int val;
BinaryTree *left;
BinaryTree *right;
};
BinaryTree *Construct(int *preorder,int *inorder,int startPre,int endPre,int startIn,int endIn)
{
if(preorder==NULL||inorder==NULL||(endPre-startPre)!=(endIn-startIn))
return NULL;
int rootValue=preorder[startPre];
int pos;
for(int i=startIn;i<=endIn;i++)
{
if(inorder[i]==rootValue)
{
pos=i;
break;
}
}
BinaryTree *root=new BinaryTree();
root->val=rootValue;
root->left=root->right=NULL;
if(pos-startIn>0)
{
root->left=Construct(preorder,inorder,startPre+1,startPre+pos-startIn,startIn,pos-1);
}
if(endIn-pos>0)
{
root->right=Construct(preorder,inorder,startPre+pos-startIn+1,endPre,pos+1,endIn);
}
return root;
}
void PostOrderTraverse(BinaryTree *root)
{
if(root->left)
PostOrderTraverse(root->left);
if(root->right)
PostOrderTraverse(root->right);
cout<<root->val<<" ";
}
int main()
{
int preorder[]={1,2,4,7,3,5,6,8};
int inorder[]={4,7,2,1,5,3,8,6};
BinaryTree *root=Construct(preorder,inorder,0,sizeof(preorder)/sizeof(preorder[0])-1,0,sizeof(inorder)/sizeof(inorder[0])-1);
PostOrderTraverse(root);
return 0;
}