二叉树遍历

本题要求的是根据层次遍历和中序遍历求出树的前序遍历，思路–>根据层次遍历和中序遍历建树

1.中序遍历和层次遍历的关系？

我们以题目样例举例，中序遍历为DBEAC，层次遍历为ABCDE。

1.1 首先、根据层次遍历和中序遍历，我们可以得出如下先验结论：

1. 层次遍历的第一个点是根节点，故该样例下根节点为 A
2. 根据节点在中序遍历的位置找出其左右子树的元素集合，例如根节点A的左子树节点包括[D,B,E],右子树包括[C]
3. 层次遍历的元素顺序代表了树中元素作为根节点的先后顺序。我们可以使用一个child指针来指示第一个可能是其子节点的元素在层次遍历中的位置，其子节点最多出现在[child,child+1]（PS.child指针初始值为2）。

1.2 根据上述结论，我们要怎么判断谁是叶子节点，谁不是叶子节点呢？

我们可以通过节点在中序遍历的前后节点状态得知。栗子如下：

Round1

Step1. 从层次遍历找到根节点A，其左右节点可能是[B,C]
Step2. 从中序遍历找到A，B和C分别位于其左右两端，所以B和C分别为其左节点和右节点
Step3. child指针往后挪两位，指向D

Round2

Step1. 从层次遍历找到节点B，其左右节点可能是[D,E]
Step2. 从中序遍历找到节点B，（D，E）两个点分别在其左右两端，所以D为其左节点，E为其右节点
Step3. child指针继续往后挪两位，越界了

Round3

Step1. 从层次遍历找到节点C，其左右节点分别为A和NULL，其左右节点可能为[A]
Step2. 从中序遍历找到节点C，但是因为A已经被访问过了，不可能在作为叶子节点了，所以排除可能，即C本身即为叶子节点。

依次类推......

综上所述，判断叶子节点还是根节点一共有两种方式：
1. 若分析该节点时，child指针越界了，说明该节点必然为叶子节点
2. 若child指针没有越界，但是该节点在中序遍历的相邻左右节点均被遍历过了，或者一边被遍历过，另一边为空，那么此时该节点为叶子节点

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100;

//hm(m指mid),hl(l指lay) 记录的是每个字母分别在中序遍历和层次遍历中的下标
//vm记录的是当前节点有没有被当作子节点遍历过
//qr记录的是从字母和结构体数组之间的映射
int hm[N], hl[N], vm[N], qr[N];

//l,r分别表示的是遍历序列的起点和终点
//posm表示的是当前访问到的节点在中序遍历中的位置，用于判断其左右节点内容
//child表示的是当前分析到层次遍历中的哪个节点
//rq表示的是当前结构体数组的下标
int l, r, posm, child = 2, rq = 0;

//root为当前的根节点，lay数组记录的是层次遍历序列，mid数组记录的是中序遍历序列
char root, lay[N], mid[N];

struct Node
{
    Node *l, *r;
    char op;
}q[N];

void pre(Node *m)
{
    if(m)
    {
        cout<<m->op;
        pre(m->l);
        pre(m->r);
    }
    else
        return ;
}

int main()
{
    scanf("%s%s", mid+1, lay+1);
    l = 1, r = strlen(mid+1);
    //记录每一个字母所在中序遍历的位置
    for(int i = 1; i <= strlen(mid+1); i ++)
        hm[mid[i]] = i;
    //记录每一个字母所在层次遍历的位置
    for(int i = 1; i <= strlen(lay+1); i ++)
        hl[lay[i]] = i;
    for(int i = 1; i <= strlen(mid+1); i ++)
    {
        //找出层次遍历当前的节点是哪个
        root = lay[i], posm = hm[root], vm[posm] = 1;

        if(rq == 0)
            q[0].op = root;

        //根据root的值求出其在q数组中的下标是多少
        if(qr[root] == 0)
        {
            qr[root] =  rq++;
        }

        //x记录的是当前root在q数组的下标
        int x = qr[root];

        //如果child指针没有越界，则存在叶节点没被用完的情况
        if(child <= r)
        {
            //如果存在左节点,且左节点没有被访问过，找到左儿子
            if(posm > l && !vm[posm - 1])
            {
                //左子节点的内容记录以及哈希映射记录下来
                q[rq].op = lay[child];
                qr[lay[child++]] = rq; 

                //建立根节点到左节点的连接
                q[x].l = &q[rq++];
            }   
            //如果存在右节点,且右节点没有被访问过，找到右儿子
            if(posm < r && !vm[posm + 1])
            {
                //右子节点的内容记录以及哈希映射记录下来
                q[rq].op = lay[child];
                qr[lay[child++]] = rq; 

                //建立根节点到右节点的连接
                q[x].r = &q[rq++];
            }
        }
    }

    //从根节点开始前序遍历
    pre(&q[0]);

    return 0;
}