C++实现二叉树遍历序列的求解方法

三、已知二叉树的后序序列和中序序列，求先序序列。

同理，由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树，所以进而可以唯一地确定先序遍历序列。因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分。

C++实现代码如下：

/*************************************************************************
 > File Name: Test1.cpp
 > Author: SongLee
 ************************************************************************/
#include<iostream>
using namespace std;

struct TreeNode
{
  struct TreeNode* left;
  struct TreeNode* right;
  char elem;
};

TreeNode* PreOrderFromOrderings(char* inorder, char* postorder, int length)
{
  if(length == 0)
  {
    return NULL;
  }
  TreeNode* node = new TreeNode;
  node->elem = postorder[length-1];
  int rootIndex = 0;
  for(; rootIndex < length; rootIndex++)  // 求左子树的长度
  {
    if(inorder[rootIndex] == postorder[length-1])
      break;
  }
  cout << node->elem << " ";  // 求先序序列，所以先输出根结点
  node->left = PreOrderFromOrderings(inorder, postorder, rootIndex);
  node->right = PreOrderFromOrderings(inorder + rootIndex + 1, postorder + rootIndex, length - (rootIndex + 1));
  return node;
}

int main()
{
  char* post = "DEBFGCA";
  char* in = "DBEAFCG";
  PreOrderFromOrderings(in, post, 7);
  cout << endl;
  return 0;
}