[HOJ]1452 Tree Recovery(对二叉树的先序、中序、后序的熟悉与掌握)

这个题主要是由给定的二叉树的先序和中序序列来还原二叉树，并且能再给出后序序列，重点和难点都是在如何还原二叉树，后序遍历只是检测是否还原正确的一个手段而已；

由于先序序列的特点是先访问根节点在访问左右节点，中序序列则是先左节点->根节点->右节点；

所以我们可以先由先序序列得到根，再到中序序列找到根的位置，而根的左边的就是其左子树的节点，右边的就是其右子树的节点，依次，递归下去就能还原二叉树，不过在递归的过程中应考虑到左左、左右、右左、右右等几种特殊的情况，有一个好的判别方法；

其他就是，还会有部分关于字符串的处理，需要掌握相应的知识。

题目: 

Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes. 

This is an example of one of her creations:

         D
        / \
       /   \
      B     E
     / \     \
    /   \     \
   A     C     G
              /
             /
            F

To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG. 

She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).

Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree. 

However, doing the reconstruction by hand, soon turned out to be tedious. 

So now she asks you to write a program that does the job for her!

Input

The input will contain one or more test cases. 

Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)

Input is terminated by end of file.

Output

For each test case, recover Valentine‘s binary tree and print one line containing the tree‘s postorder traversal (left subtree, right subtree, root).

Sample Input

DBACEGF ABCDEFG
BCAD CBAD

ACBFGED
CDAB

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;
struct node
{
    node *left;
    node *right;
    char data;
};
string str,porderStr,inorderStr;
int n = 0;
node* GetLeftRoot(string str1);
node* GetRightRoot(string str2);
void BuiltTree(node *root,int num);
void postOrderBT(node *root);

node* GetLeftRoot(string str1)
{
    string leftStr,rightStr;
    int position = -1;
    node *root,*leftree,*rightree;
    char ch;
    int length = 0;
    ch = porderStr[n];
    n++;
    position = str1.find(ch);
    root = new node;
    root->data = ch;
    length = str1.length();

    if(position == 0){
        if(length > 1){
            rightStr.assign(str1,1,length);
            rightree = GetRightRoot(rightStr);
            root->left = NULL;
            root->right = rightree;
            return root;
        }
        else{
            root->left = NULL;
            root->right = NULL;
            return root;
        }
    }
    else{
        leftStr.assign(str1,0,position);
        rightStr.assign(str1,position+1,length);
        if(!leftStr.empty()){
            leftree = GetLeftRoot(leftStr);
            root->left = leftree;
        }
        else
            root->left = NULL;
        if(!rightStr.empty()){
            rightree = GetRightRoot(rightStr);
            root->right = rightree;
        }
        else
            root->right = NULL;
        return root;
    }
}
node* GetRightRoot(string str2)//建立右子树
{
    string leftStr,rightStr;
    int position = -1;
    node *leftree,*rightree,*root;
    char ch;
    int length = 0;
    ch = porderStr[n];
    n++;
    position = str2.find(ch);
    root = new node;
    root->data = ch;
    length = str2.length();
    if(position == 0){
        if(length > 1){
            rightStr.assign(str2,1,length);
            rightree = GetRightRoot(rightStr);
            root->left = NULL;
            root->right = rightree;
            return root;
        }
        else{
            root->left = NULL;
            root->right = NULL;
            return root;
        }
    }
    else{
        leftStr.assign(str2,0,position);
        rightStr.assign(str2,position+1,length);
        if(!leftStr.empty()){
            leftree = GetLeftRoot(leftStr);
            root->left = leftree;
        }
        else
            root->left = NULL;
        if(!rightStr.empty()){
            rightree = GetRightRoot(rightStr);
            root->right = rightree;
        }
        else
            root->right = NULL;
        return root;
    }
}
void BuiltTree(node *root,int num)//用于还原二叉树
{
    int position = 0;
    node *leftree,*rightree;
    string leftStr,rightStr;
    char ch = porderStr[n];
    n++;
    position = inorderStr.find(ch);
    leftStr.assign(inorderStr,0,position);
    rightStr.assign(inorderStr,position+1,num);
    leftree = GetLeftRoot(leftStr);//调用递归函数，利用先序和中序序列特点
    rightree = GetRightRoot(rightStr);
    root->data = ch;
    root->left = leftree;
    root->right = rightree;
}
void postOrderBT(node *root)
{
    if(root->left != NULL)
        postOrderBT(root->left);
    if(root->right != NULL)
        postOrderBT(root->right);
    cout<<root->data;
}
int main()
{
        string leftStr,rightStr;
        int num;//中序序列的长度
        node *root;


        getline(cin,str);
        while(!str.empty()){//判断是否到达输入的末端
            root = new node;
            n = 0;
            num = str.length() / 2;//因为是整行输入所以需要分开先序和中序序列
            porderStr.assign(str,0,num);
            inorderStr.assign(str,num+1,2*num);
            BuiltTree(root,num);//复原原二叉树
            postOrderBT(root);//后序遍历二叉树；
            cout<<endl;
            getline(cin,str);
        }
        return 0;
}

[HOJ]1452 Tree Recovery(对二叉树的先序、中序、后序的熟悉与掌握),布布扣,bubuko.com

[HOJ]1452 Tree Recovery(对二叉树的先序、中序、后序的熟悉与掌握)

原文：http://blog.csdn.net/ymzmdx/article/details/21259217