已知树的中序序列和先序/后序序列，求树的结构？

 已知树的中序序列和先序/后序序列，求树的结构？


这类问题比较经典了，刚好CSDN上有人问起，所以自己写了一个递归算法，根据中序和先序（后序）建立树结构。这里需要说明的是：必须要知道中序序列，先序和后序可选的情况下才能推导出树结构，只知道后序先序是推导不出。简单说明一下基本思路，例：
   已知后序： DEBGFCA  中序：DBEAFGC 求先序？或者求树结构？

因为有后序序列DEBGFCA，所以根节点为A,再根据中序序列，DBE|A|FGC，所以DBE肯定是左子树，FGC是右子树；再看左子树DBE，因为后序序列DEB，所以可以确定根节点为B，所以中序序列D|B|E可以分成D和E两个左子树，以此类推，这样就形成了一个递归过程。根据这个推断就很容易把树构造出来：

#include <string>
using namespace std;

typedef struct _BITREENODE
{
    _BITREENODE(){::memset(this, 0, sizeof(_BITREENODE));}
    char _data;
    _BITREENODE* _leftChild;
    _BITREENODE* _rightChild;
}BTreeNode, *PBTreeNode;

enum eBTreeType {bttPreOrder, bttLastOrder};

//找出字符相同（排列次序不同）
string IsContain(string strDes, string strSrc)
{
    string strTmp;
    bool bTmp = false;

    for (int i=0; i<strDes.length(); ++i)
    {
        strTmp = strDes.substr(i, strSrc.length());

        for (int j=0; j<strSrc.length(); ++j)
        {
            bTmp = false;
            for (int k=0; k<strTmp.length(); ++k)
            {
                if (strTmp.at(k) == strSrc.at(j))
                {
                    bTmp = true;
                }
            }
           
            if (!bTmp) break;
        }

        if (bTmp) break;       
    }

    return strTmp;
}

//如果出错就返回false
bool CreateBTree(string strMid, string strSec, PBTreeNode &pRoot, eBTreeType eBtt)
{
    string strTmp;
    if (strMid.empty() || strSec.empty()) return true;
    if (strMid.size() == 1
        && strSec.size() == 1
        && strMid.size() == strSec.size())
    {
        pRoot->_data = strSec.at(0);
        return true;
    }

    char ch;
    if (eBtt == bttPreOrder)            //先序
    {
        ch = strSec.at(0);
    }
    else if (eBtt == bttLastOrder)    //后序
    {
        ch = strSec.at(strSec.length()-1);
    }

    pRoot->_data = ch;
    pRoot->_leftChild = new BTreeNode;
    pRoot->_rightChild = new BTreeNode;
           
    //左子树
    int iPos = strMid.find(ch);
    if (iPos == string::npos) return false;
    strTmp = strMid.substr(0, iPos);
    string str = IsContain(strSec, strTmp);
    if (!str.empty())
    {
        if (!CreateBTree(strTmp, str, pRoot->_leftChild, eBtt))
            return false;
    }       

    //右子树
    strTmp = strMid.substr(iPos+1, strMid.length()-1-iPos);
    str = IsContain(strSec, strTmp);
    if (!str.empty())
    {
        if (!CreateBTree(strTmp, str, pRoot->_rightChild, eBtt))
            return false;
    }

    return true;
}


int main()
{
    int i;
    BTreeNode *pRoot = new BTreeNode;
    if (CreateBTree("DBEAFGC", "ABDECFG", pRoot, bttPreOrder))
    {
        system("echo Successed");
    }

    system("pause");
}