Determine a binary tree given inorder traversal and another traversal method

 Given an inorder traversal and another traversal method,A binary tree can be obtained;The reason is that the root node of an inorder traversal can split the left and right nodes in half;The other traversal methods are to give the subtree head node,The left and right subtrees cannot be separated;Hence the other three traversal methods,Any given two traversal methods or three traversal methods together cannot determine a binary tree;

    1)Determine a binary tree given inorder traversal and preorder traversal：
    Preorder traversal of the interval is assumed：[preL,preR];中序遍历：[midL,midR];
    kis the root node of the binary tree traversed in inorder;Then it is not difficult to know：
     左子树的个数：numl=k-midL;
        The left subtree interval for preorder traversal：[preL+1,preL+numl],The left subtree interval for inorder traversal：[midL,midL+numl-1];
        Right subtree interval for preorder traversal：[preL+numl+1,preR],Right subtree interval for inorder traversal：[mid+numl+1,midR];

/**
    Given an inorder traversal and another traversal method,A binary tree can be obtained;
    The reason is that the root node of an inorder traversal can split the left and right nodes in half;The other traversal methods are to give the subtree head node,You cannot put left and right subtrees
    分开;Hence the other three traversal methods,Any given two traversal methods or three traversal methods together cannot determine a binary tree;
*/

/**
    1)Determine a binary tree given inorder traversal and preorder traversal：
    Preorder traversal of the interval is assumed：[preL,preR];中序遍历：[midL,midR];
    kis the root node of the binary tree traversed in inorder;Then it is not difficult to know：
     左子树的个数：numl=k-midL;
        The left subtree interval for preorder traversal：[preL+1,preL+numl],The left subtree interval for inorder traversal：[midL,midL+numl-1];
        Right subtree interval for preorder traversal：[preL+numl+1,preR],Right subtree interval for inorder traversal：[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 << "Enter the number of nodes in the tree:\n";
    cin >> n;
    cout << "Enter the preorder traversal data\n";
    for(int i=0;i<n;++i)
        cin >> pre[i];
    cout << "Enter the inorder traversal data:\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)Determine a binary tree given in-order traversal and post-order traversal：
    A postorder traversal of the interval is assumed：[behL,behR];中序遍历：[midL,midR];
    kis the root node of the binary tree traversed in inorder;Then it is not difficult to know：
     右子树的个数：numr=midR-k;
      The left subtree interval for postorder traversal：[behL,behR-numr-1],The left subtree interval for inorder traversal：[midL,midR-numr-1];
     Right subtree interval for postorder traversal：[behR-numr,behR-1],Right subtree interval for inorder traversal：[midR-numr+1,midR];

/**
    2)Determine a binary tree given in-order traversal and post-order traversal：
    A postorder traversal of the interval is assumed：[behL,behR];中序遍历：[midL,midR];
    kis the root node of the binary tree traversed in inorder;Then it is not difficult to know：
     右子树的个数：numr=midR-k;
        The left subtree interval for postorder traversal：[behL,behR-numr-1],The left subtree interval for inorder traversal：[midL,midR-numr-1];
        Right subtree interval for postorder traversal：[behR-numr,behR-1],Right subtree interval for inorder traversal：[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 << "Enter the number of nodes in the tree:\n";
    cin >> n;
    cout << "输入后序遍历数据\n";
    for(int i=0;i<n;++i)
        cin >> beh[i];
    cout << "Enter the inorder traversal data:\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);
    }
}