给定中序遍历和另外一种遍历方法确定一棵二叉树

 给定中序遍历和另外一种遍历方法，可以得到一棵二叉树;原因是中序遍历的根节点可以把左右节点分成两半；而其他遍历方法都是给出子树头结点，不能把左右子树分开；因此另外三种遍历方法，任意给出两种遍历方法或者三种遍历方法一起都不能确定一棵二叉树；

    1)给出中序遍历和前序遍历确定一棵二叉树：
    假定前序遍历区间：[preL,preR]；中序遍历：[midL,midR]；
    k为中序遍历的二叉树的根节点；那么不难得知：
     左子树的个数：numl=k-midL；
        前序遍历的左子树区间：[preL+1,preL+numl]，中序遍历的左子树区间：[midL,midL+numl-1];
        前序遍历的右子树区间：[preL+numl+1,preR]，中序遍历的右子树区间：[mid+numl+1,midR];

/**
    给定中序遍历和另外一种遍历方法，可以得到一棵二叉树;
    原因是中序遍历的根节点可以把左右节点分成两半；而其他遍历方法都是给出子树头结点，不能把左右子树
    分开；因此另外三种遍历方法，任意给出两种遍历方法或者三种遍历方法一起都不能确定一棵二叉树；
*/

/**
    1)给出中序遍历和前序遍历确定一棵二叉树：
    假定前序遍历区间：[preL,preR]；中序遍历：[midL,midR]；
    k为中序遍历的二叉树的根节点；那么不难得知：
     左子树的个数：numl=k-midL；
        前序遍历的左子树区间：[preL+1,preL+numl]，中序遍历的左子树区间：[midL,midL+numl-1];
        前序遍历的右子树区间：[preL+numl+1,preR]，中序遍历的右子树区间：[mid+numl+1,midR];
    data:
    7
    4 1 3 2 6 5 7
    1 2 3 4 5 6 7
*/

/**
#include <iostream>

using namespace std;

typedef struct TNode* BinTree;
struct TNode
{
    int data;
    BinTree lchild,rchild;
    TNode()
    {
        lchild=rchild=NULL;
    }
};
BinTree CreateTree_with_Pre_and_Mid(int preL,int preR,int midL,int midR);
void BehTraver(BinTree BT);

const int maxn=20;
int pre[maxn],mid[maxn];
int main()
{
    int n;
    cout << "输入树的结点数目:\n";
    cin >> n;
    cout << "输入前序遍历数据\n";
    for(int i=0;i<n;++i)
        cin >> pre[i];
    cout << "输入中序遍历数据:\n";
    for(int i=0;i<n;++i)
        cin >> mid[i];
    BinTree BT=CreateTree_with_Pre_and_Mid(0,n-1,0,n-1);
    BehTraver(BT);
    return 0;
}

BinTree CreateTree_with_Pre_and_Mid(int preL,int preR,int midL,int midR)
{
    if(preL>preR)
        return NULL;
    BinTree BT=new TNode;
    BT->data=pre[preL];
    int k;
    for(k=midL;k<=midR;++k)
    {
        if(mid[k]==pre[preL])
            break;
    }
    int numl=k-midL;
    BT->lchild=CreateTree_with_Pre_and_Mid(preL+1,preL+numl,midL,midL+numl-1);
    BT->rchild=CreateTree_with_Pre_and_Mid(preL+numl+1,preR,midL+numl+1,midR);
    return BT;
}

void BehTraver(BinTree BT)
{
    if(BT)
    {
        BehTraver(BT->lchild);
        BehTraver(BT->rchild);
        printf("%d ",BT->data);
    }
}
*/

2)给出中序遍历和后序遍历确定一棵二叉树：
    假定后序遍历区间：[behL,behR]；中序遍历：[midL,midR]；
    k为中序遍历的二叉树的根节点；那么不难得知：
     右子树的个数：numr=midR-k；
      后序遍历的左子树区间：[behL,behR-numr-1]，中序遍历的左子树区间：[midL,midR-numr-1];
     后序遍历的右子树区间：[behR-numr,behR-1]，中序遍历的右子树区间：[midR-numr+1,midR];

/**
    2)给出中序遍历和后序遍历确定一棵二叉树：
    假定后序遍历区间：[behL,behR]；中序遍历：[midL,midR]；
    k为中序遍历的二叉树的根节点；那么不难得知：
     右子树的个数：numr=midR-k；
        后序遍历的左子树区间：[behL,behR-numr-1]，中序遍历的左子树区间：[midL,midR-numr-1];
        后序遍历的右子树区间：[behR-numr,behR-1]，中序遍历的右子树区间：[midR-numr+1,midR];

    data:
    7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7
*/

#include <iostream>

using namespace std;

typedef struct TNode* BinTree;
struct TNode
{
    int data;
    BinTree lchild,rchild;
    TNode()
    {
        lchild=rchild=NULL;
    }
};
BinTree CreateTree_with_Beh_and_Mid(int behL,int behR,int midL,int midR);
void PreTraver(BinTree BT);

const int maxn=20;
int beh[maxn],mid[maxn];
int main()
{
    int n;
    cout << "输入树的结点数目:\n";
    cin >> n;
    cout << "输入后序遍历数据\n";
    for(int i=0;i<n;++i)
        cin >> beh[i];
    cout << "输入中序遍历数据:\n";
    for(int i=0;i<n;++i)
        cin >> mid[i];
    BinTree BT=CreateTree_with_Beh_and_Mid(0,n-1,0,n-1);
    PreTraver(BT);
    return 0;
}

BinTree CreateTree_with_Beh_and_Mid(int behL,int behR,int midL,int midR)
{
    if(behL>behR)
        return NULL;
    BinTree BT=new TNode;
    BT->data=beh[behR];
    int k;
    for(k=midL;k<=midR;++k)
    {
        if(mid[k]==beh[behR])
            break;
    }
    int numr=midR-k;
    BT->lchild=CreateTree_with_Beh_and_Mid(behL,behR-numr-1,midL,midR-numr-1);
    BT->rchild=CreateTree_with_Beh_and_Mid(behR-numr,behR-1,midR-numr+1,midR);
    return BT;
}

void PreTraver(BinTree BT)
{
    if(BT)
    {
        printf("%d ",BT->data);
        PreTraver(BT->lchild);
        PreTraver(BT->rchild);
    }
}