给定前序或后序的序列，判断该序列是否能构成一颗二叉搜索树（或镜像的二叉搜索树）

假设能构成一颗二叉搜索树，那么这棵树的中序遍历必定为有序的序列

此时已知前（后）序遍历和中序遍历

根据二叉树的性质，已知前（后）序遍历和中序遍历可以唯一的确定一颗二叉树
思路

递归思想，首先找到前序遍历中的根节点（第一个节点），再找出该值对应在中序遍历序列中的位置，分界后分别对左右子树进行递归。
注意：由于可能存在数值相同的节点，根据原树和镜像树的不同需要找到中序遍历中第一次出现或是最后一次出现对应的节点，具体见代码
此算法也可用于已知前（后）序遍历和中序遍历求后（前）序遍历
代码实现
//此算法假定中序遍历为升序且已知前序遍历
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, cnt;
int preorder[N], inorder[N], postorder[N]; //分别表示前、中、后序遍历

bool build(int il, int ir, int pl, int pr, int t) //是否能建树
{
    int root = preorder[pl]; //当前根节点的数值
    int k; //中序遍历的根节点的位置
    
    if (t == 0) //表示为原二叉搜索树
    {
        for (k = il; k <= ir; k ++ ) //找出中序遍历中第一次出现的位置
            if (root == inorder[k])
                break;
    }
    else //镜像
    {
        for (k = ir; k >= il; k -- ) //找出中序遍历中最后一次出现的位置
            if (root == inorder[k])
                break;
    }
    
    if (k > ir || k < il) return false; //不能在中序遍历对应的位置找出根节点的值，说明无法建树
    
    bool f = true;
    if (il < k && !build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, t)) f = false; //左子树存在
    if (k < ir && !build(k + 1, ir, pr - (ir - k - 1), pr, t)) f = false; //右子树存在
    
    postorder[cnt ++ ] = root; //递归后记录的即为后序遍历
    //若是记录前序遍历，需在递归前记录
    
    return f;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> preorder[i];
        inorder[i] = preorder[i];
    }
    
    sort(inorder, inorder + n); //升序排列
    
    if (build(0, n - 1, 0, n - 1, 0))
    {
        cout << "YES\n";
        cout << postorder[0];
        for (int i = 1; i < n; i ++ )
            cout << ' ' << postorder[i];
    }
    else
    {
    	//判断镜像能否建树
        reverse(inorder, inorder + n);
        cnt = 0;
        if (build(0, n - 1, 0, n - 1, 1))
        {
            cout << "YES\n";
            cout << postorder[0];
            for (int i = 1; i < n; i ++ )
                cout << ' ' << postorder[i];
        }
        else
            cout << "NO";
    }
    return 0;
}


题目来源：PAT甲级1043 Is It a Binary Search Tree

树和森林的遍历
@(数据结构)
不要带着二叉树的遍历来限制了对树的遍历的理解。

树的遍历的定义：以某种方式访问树中的每一个结点，且仅访问一次。

树的遍历主要有先根遍历和后根遍历。

先根遍历：若树非空，则先访问根结点，再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。


后根遍历：若树非空，则按照从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。


根据这幅图：

树的先根遍历：A-B-E-F-G-C-H-D-I-J

对应的二叉树的先序遍历：A-B-E-F-G-C-H-D-I-J
二者是一致的。
树的后根遍历：E-F-G-B-H-C-I-J-D-A

对应的二叉树的后序遍历：G-F-E-H-J-I-D-C-B-A

对应的二叉树的中序遍历：E-F-G-B-H-C-I-J-D-A(与树的后根遍历相一致)
注意到我们并没有定义一般树的中根遍历，因为子结点该怎么分两部分并没有定义，所以只定义先、后根。
以上只是模拟证实。
森林的遍历：需要澄清的是，只有二叉树森林才有中序遍历与完整二叉树中序遍历对应

先序遍历森林。
若森林非空，访问森林的第一棵树的根结点。
先序遍历第一棵树中根结点的子树
先序遍历除去掉遍历过的树的森林
中序遍历森林：普通的树构成的森林是不存在中序遍历的，这里的中序遍历必然指代的是化成二叉树的森林。
后序遍历也可以相似定义。

我们看这个森林和二叉树的各种遍历。
森林的先根遍历：A-B-C-D-E-F-G-H-J-I

二叉树森林的先序遍历：A-B-C-D-E-F-G-H-J-I(相同)

完整二叉树的先序遍历：A-B-C-D-E-F-G-H-J-I (相同)
森林的后根遍历：B-C-D-A-F-E-J-H-I-G

二叉树森林的后序遍历：D-C-B-A-F-E-J-I-H-G

完整二叉树的后序遍历：D-C-B-F-J-I-H-G-E-A(不同于二叉树森林的后序遍历)

二叉树森林的中序遍历：B-C-D-A-F-E-J-H-I-G(与森林的后根遍历相同)

完整二叉树的中序遍历：B-C-D-A-F-E-J-H-I-G(与森林的后根遍历相同，自然也与二叉树森林的中序遍历相同)
2019.10 Update:
第一届PAT算法直播课培训班招募帖，欢迎点击查看详情、
END.

这个题是利用树的基础，来模拟人为通过后中重构树的过程

有个小技巧在于，前中后遍历中，虽然所得结果的排序不同，但是子树所在的区域近乎相同，相差不大于1

对于后中重构中，我们很容易得到右子树的根，却难得到左子树的根，利用上述结论，可以间接求出右子树的长度，进而确定中序遍历中，左子树的位置，进而找到后序中，左子树的根具体在哪

L2-006 树的遍历 (25分)

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

输入格式：

输入第一行给出一个正整数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

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define MAXN 50
int hind[MAXN];
int mid[MAXN];
int n;
int index,lnum,rnum;
struct node
{
    int value;
    node *left;
    node *right;
}*T = NULL;
void Create(node *&R,int l,int r,int index)
{
    if(l>r) return;
    int p;
    R = new node;
    R->value = hind[index];
    R->left = NULL;
    R->right = NULL;
    for(int i = l; i <= r; i++) if(mid[i] == hind[index]) {p = i;break;};
    Create(R->right,p+1,r,index-1);
    Create(R->left,l,p-1,index+p-r-1);
}
void bfs()
{
    queue<node*> q;
    q.push(T);
    bool flag = false;
    while(!q.empty())
    {
       node* temp = q.front();
       q.pop();
       if(!flag)
       {
           flag = true;
           printf("%d",temp->value);
       }
       else printf(" %d",temp->value);
       if(temp->left) q.push(temp->left);
       if(temp->right) q.push(temp->right);
    }
}
int main()
{
    cin>>n;
    for(int i = 0; i < n; i++) scanf("%d",&hind[i]);
    for(int i = 0; i < n; i++) scanf("%d",&mid[i]);
    Create(T,0,n-1,n-1);
    bfs();
    return 0;
}


 

树的遍历
树的遍历主要有先根遍历和后根遍历。
先根遍历：若树非空，则先访问根结点，再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。
后根遍历：若树非空，则按照从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。
森林的遍历
森林的遍历包括先序遍历和中序遍历。
若森林非空：
先序遍历

访问森林的第一棵树的根结点
先序遍历第一棵树中根结点的子树
先序遍历除去掉遍历过的树的森林

中序遍历

中序遍历第一棵树中根结点的子树
访问第一棵树的根结点
中序遍历除去掉遍历过的树的森林

总结
树、森林、二叉树之间的遍历有对应的关系




树
森林
二叉树




先根遍历
先序遍历
先序遍历


后根遍历
中序遍历
中序遍历


参考
王道2021数据结构
树和森林的遍历