重构二叉树 + 输出 （层序遍历、其他遍历）

一、题型

　　输入是两个一维数组，分别表示树的前/中/后序遍历和前/中/后序遍历结果，输出是输出二叉树或层序遍历或其他。

二、分类

　　1. 输入：前序+中序   输出

　　2. 输入：前序+后序   输出

　　3. 输入：中序+后序   输出

三、重构二叉树

　　1. 重构二叉树思路：前序遍历的第一个节点即为根节点，在前序遍历中找到根节点后，再在中序遍历中找到根节点的位置，根节点的左边所有点就是它的左子树，右边所有节点就是它的右子树。统计左子树有几个点，然后在前序遍历数组中根节点的后面找几个点，右子树也一样。然后再在左子树和右子树中寻找下一个根节点，重复上面操作。结合下面例子来理解一下。

　　2.举例（前序 + 中序）

给出前序遍历数组：前序： A B D E H I C F K G

给出中序遍历数组：中序： D B H E I A F K C G

首先前序遍历的第一个节点A就是根节点，在中序遍历中找到A的位置，下标为5，则A的左边5个节点即为左子树，右边4个节点即为右子树。

先递归A的左子树，A的左子树有5个，则在前序遍历A的后面5个范围内找，第一个点是B，则B是左子树的第一个根节点，又在中序中找到B的位置，为1，

B的左边只有D，则D是B的左节点，B的右边有三个，则递归B的右子树。B的右边有3个，则在前序遍历中找E H I 三个点，E先，则E是B的右节点。继续重复。。。。

如下图中的操作。

　　3. 重构二叉树的代码框架

前序 + 中序：

#include 
using namespace std;


int Pre[31],In[31];
typedef struct BinaryTree{
    int key;
    BinaryTree *left;
    BinaryTree *right;
}BinaryTree,*Tree;
//注：另外命名一个*Tree，后面队列那里要用到

//找到后序遍历的根节点在中序遍历的位置，记为r
int FindRootInInoder(int begin,int end,int key){
    for(int i=begin;i){
        if(key==In[i])
            return i;
    }
}

/**
   重构二叉树：前序+中序
**/
BinaryTree *GetBinaryTree(int pbegin,int pend,int ibegin,int iend){
//     if(pbegin>=pend || ibegin>=iend){
//         return NULL;
//     }
    BinaryTree *Root = new struct BinaryTree;//新建一颗树
    *Root = {Pre[pbegin],NULL,NULL};   //前序遍历的第一个值即为根节点。注意：Root前要有*否则报错
    int r = FindRootInInoder(ibegin,iend,Pre[pbegin]);
    //递归求左子树、右子树
    int count=r-ibegin;    //左子树节点的个数，有几个就在前序遍历中从pbegin开始找几个
    if(r!=ibegin)
        Root->left = GetBinaryTree(pbegin+1, (r-ibegin)+pbegin+1, ibegin, r);
    if(r!=iend)
        Root->right = GetBinaryTree((r-ibegin)+pbegin+1, pend, r+1, iend);
    return Root;
}


int main(){
    int n;
    cin>>n;
    for(int i=0;i)
        cin>>Pre[i];
    for(int i=0;i)
        cin>>In[i];
    Tree root = GetBinaryTree(0,n-1,0,n-1);//注意：此处是n-1索引
    Sequence(root);
    return 0;
}

中序 + 后序：

思路、代码框架都一样，只不过需要改掉下面①②③④个部分

#include 
using namespace std;

int Post[31],In[31];
typedef struct BinaryTree{
    int key;
    BinaryTree *left;
    BinaryTree *right;
}BinaryTree,*Tree;
//注：另外命名一个*Tree，后面队列那里要用到

//找到后序遍历的根节点在中序遍历的位置，记为r
int FindRootInInoder(int begin,int end,int key){
    for(int i=begin;i){
        if(key==In[i])
            return i;
    }
}

/**
   重构二叉树：后序+中序
**/
BinaryTree *GetBinaryTree(int pbegin,int pend,int ibegin,int iend){
//     if(pbegin>=pend || ibegin>=iend){
//         return NULL;
//     }
    BinaryTree *Root = new struct BinaryTree;//新建一颗树
    *Root = {Post[pend],NULL,NULL};   //后序遍历的最后一个值即为根节点。注意：Root前要有*否则报错   ①
    int r = FindRootInInoder(ibegin,iend,Post[pend]);     ②
    //递归求左子树、右子树
    int count=r-ibegin;    //左子树节点的个数，有几个就在后序遍历中从pbegin开始找几个
    if(r!=ibegin)
        Root->left = GetBinaryTree(pbegin,pbegin+count-1,ibegin,r-1);    ③
    if(r!=iend)
        Root->right = GetBinaryTree(pbegin+count,pend-1,r+1,iend);       ④
    return Root;
}


int main(){
    int n;
    cin>>n;
    for(int i=0;i)
        cin>>Post[i];
    for(int i=0;i)
        cin>>In[i];
    Tree root = GetBinaryTree(0,n-1,0,n-1);//注意：此处是n-1索引
    Sequence(root);
    return 0;
}

前序 + 后序：也一样，略。

四、例子

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

AC代码：

#include 
using namespace std;

int Post[31],In[31];
typedef struct BinaryTree{
    int key;
    BinaryTree *left;
    BinaryTree *right;
}BinaryTree,*Tree;
//注：另外命名一个*Tree，后面队列那里要用到

//找到后序遍历的根节点在中序遍历的位置，记为r
int FindRootInInoder(int begin,int end,int key){
    for(int i=begin;i){
        if(key==In[i])
            return i;
    }
}

/**
   重构二叉树：后序+中序
**/
BinaryTree *GetBinaryTree(int pbegin,int pend,int ibegin,int iend){
//     if(pbegin>=pend || ibegin>=iend){
//         return NULL;
//     }
    BinaryTree *Root = new struct BinaryTree;//新建一颗树
    *Root = {Post[pend],NULL,NULL};   //后序遍历的最后一个值即为根节点。注意：Root前要有*否则报错
    int r = FindRootInInoder(ibegin,iend,Post[pend]);
    //递归求左子树、右子树
    int count=r-ibegin;    //左子树节点的个数，有几个就在后序遍历中从pbegin开始找几个
    if(r!=ibegin)
        Root->left = GetBinaryTree(pbegin,pbegin+count-1,ibegin,r-1);
    if(r!=iend)
        Root->right = GetBinaryTree(pbegin+count,pend-1,r+1,iend);
    return Root;
}

/**
   输出层序遍历（常用队列实现）
**/
void Sequence(Tree root)
{
    queue t;
    if(root)
        t.push(root);
    while(!t.empty())
    {
        root=t.front();
        t.pop();
        cout<key;
        if(root->left)
            t.push(root->left);
        if(root->right)
            t.push(root->right);
        if(!t.empty())
            cout<<" ";    
    }
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i)
        cin>>Post[i];
    for(int i=0;i)
        cin>>In[i];
    Tree root = GetBinaryTree(0,n-1,0,n-1);//注意：此处是n-1索引
    Sequence(root);
    return 0;
}

写得有点匆忙，有错误欢迎指正。