#include <bits/stdc++.h>
using namespace std;
const int N = 100;
struct Node
{
    int left, right;
} tree[N];
int n, zhong[N], qian[N], gen;
queue<int> q;
//建树 已知中序和后序
// int build(int l1, int r1, int l2, int r2) // l1,r1是中序遍历当前树的数组范围
// {
//  if (l1 > r1) //遍历到叶子节点儿子 结束 返回-1
//      return -1;
//  int root = hou[r2]; //找根 后序的最后一个是根
//  int p = l1;
//  while (zhong[p] != root) //从中序遍历中找到根 然后递归左右子树
//  {
//      p++;
//  }
//  int cnt = p - l1;                                      //左子树截取长度
//  tree[root].left = build(l1, p - 1, l2, l2 + cnt - 1);  //左子树的中序后序
//  tree[root].right = build(p + 1, r1, l2 + cnt, r2 - 1); //右子树的中序后序
//  return root;
// }

//已知前序和中序建树
int build(int l1, int r1, int l2, int r2) // l1,r1是中序遍历当前树的数组范围
{
    if (l1 > r1)
        return -1;
    int root = qian[l2];
    int p = l1;
    while (zhong[p] != root)
    {
        p++;
    }
    int cnt = p - l1;
    tree[root].left = build(l1, p - 1, l2 + 1, l2 + 1 + cnt - 1);
    tree[root].right = build(p + 1, r1, l2 + 1 + cnt, r2);
    return root;
}
//层序遍历
void bfs()
{
    q.push(gen);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        cout << now << " ";
        if (tree[now].left != -1)
        {
            q.push(tree[now].left);
        }
        if (tree[now].right != -1)
        {
            q.push(tree[now].right);
        }
    }
}
// 先序遍历
void xianxu(int root)
{
    if (root == -1)
        return;
    cout << root << " ";
    xianxu(tree[root].left);
    xianxu(tree[root].right);
}
//中序遍历
void zhongxu(int root)
{
    if (root == -1)
        return;
    zhongxu(tree[root].left);
    cout << root << " ";
    zhongxu(tree[root].right);
}
//后序遍历
void houxu(int root)
{
    if (root == -1)
        return;
    houxu(tree[root].left);
    houxu(tree[root].right);
    cout << root << " ";
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> qian[i];
    for (int i = 0; i < n; i++)
        cin >> zhong[i];
    gen = build(0, n - 1, 0, n - 1);
    cout << "层序" << endl;
    bfs();
    cout << endl;
    cout << "先序" << endl;
    xianxu(gen);
    cout << endl;
    cout << "中序" << endl;
    zhongxu(gen);
    cout << endl;
    cout << "后序" << endl;
    houxu(gen);
    cout << endl;

    return 0;
}

二叉搜索树

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N];
int n;
int flag; //判断镜像
vector<int> q;
void dfs(int l, int r) //先序遍历第一个结点是根节点
{
    if (l > r)
        return;
    int l1 = l + 1, r1 = r; //去掉根节点，去判断儿子节点是否都符合条件
    if (flag == false)
    {
        while (l1 <= r && a[l1] < a[l])
            l1++;
        while (r1 >= l + 1 && a[r1] >= a[l])
            r1--;
    }
    else //判断镜像
    {

        while (l1 <= r && a[l1] >= a[l])
            l1++;
        while (r1 >= l + 1 && a[r1] < a[l])
            r1--;
    }

    if (l1 - r1 != 1)
        return;
    dfs(l + 1, r1);
    dfs(l1, r);
    q.push_back(a[l]);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    dfs(0, n - 1);
    if (q.size() != n)
    {
        flag = 1;
        q.clear();
        dfs(0, n - 1);
    }
    if (q.size() != n)
        cout << "NO" << endl;
    else
    {
        cout << "YES" << endl;
        for (int i = 0; i < q.size() - 1; i++)
            cout << q[i] << " ";
        cout << q[q.size() - 1] << endl;
    }
    return 0;
}

关于一些二叉树的题目

新二叉树 https://www.luogu.com.cn/problem/P1305

由于输入每行都是先是根节点，然后是左右儿子，正好符合前序遍历

所以就直接遇见根节点就递归，是根节点就输出

#include<bits/stdc++.h>
using namespace std;
char a[30][4];
int n;
void tree(char c)
{
    if(c!='*')
    {
        cout<<c;
        for(int i=0;i<n;i++)
        {
            if(a[i][0]==c)
                {
                    tree(a[i][1]);
                    tree(a[i][2]);
                }
        }
    }
}
int main()
{  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
   cin>>n;
   for(int i=0;i<n;i++)
    cin>>a[i][0]>>a[i][1]>>a[i][2];
    tree(a[0][0]);

    return 0;
}

求后序排列 https://www.luogu.com.cn/problem/P1827

#include<bits/stdc++.h>
using namespace std;
string start,middle;
void tree(string middle,string start)
{  if(middle.size()>0)  //递归必须有终止条件，否则程序会错误，别问我怎么知道的
{
    char c;
    c=start[0];
int k=middle.find(c);
tree(middle.substr(0,k),start.substr(1,k));
tree(middle.substr(k+1),start.substr(k+1));
cout<<c; //输出放在后面
 //因为要输出后序序列，所以是左右根
    //先遍历左子树，再右子树，再根节点
}

}
int main()
{  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>middle>>start;
tree(middle,start);

    return 0;
}

【深基16.例3】二叉树深度 https://www.luogu.com.cn/problem/P4913

不用建树，直接用dfs搜索深度

#include<bits/stdc++.h>
using namespace std;
int t;
const int N=1e6+10;
int ans=-1;
struct node
{
    int l,r;
}a[N];
void dfs(int root,int step)
{
    if(!root) //切记！！！ 一定要有终止条件
        return;
    dfs(a[root].l,step+1);//搜索左儿子
    dfs(a[root].r,step+1);//搜索右儿子
    ans=max(ans,step);
}
int main()
{  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
       cin>>t;
    for(int i=1;i<=t;i++)
        cin>>a[i].l>>a[i].r;
dfs(1,1);
cout<<ans<<endl;
    return 0;
}

更新第二种方法 2022/4/22

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int dist[N];
vector<int> son[N];
queue<int> q;
int n;
void bfs()
{
    q.push(1);
    dist[1] = 1;
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < son[now].size(); i++)
        {
            int temp = son[now][i];
            if (temp != 0)
            {
                dist[temp] = dist[now] + 1;
                q.push(temp);
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int left, right;
        cin >> left >> right;
        son[i].push_back(left);
        son[i].push_back(right);
    }
    bfs();
    int maxn = -1;
    for (int i = 1; i <= n; i++)
    {
        maxn = max(maxn, dist[i]);
    }
    cout << maxn << endl;
    return 0;
}

FBI树 https://www.luogu.com.cn/problem/P1087

由于本题最终求后续排列，而在递归输出时恰好是从后往前的，所以直接就得到了所要求的

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
void tree(int x,int y)
{
    if(y>x)
    {
        tree(x,(x+y)/2); //递归左右字符串
        tree((x+y+1)/2,y);
    }
    int B=1,I=1;
    for(int i=x;i<=y;i++)  //判断输出什么
    {
        if(s[i]=='1')
            B=0;
        else if(s[i]=='0')
            I=0;
    }
    if(B)
        cout<<'B';
    else if(I)
        cout<<'I';
    else
        cout<<'F';
}
int main()
{  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>s;
tree(0,s.size()-1);
    return 0;
}

求先序序列 https://www.luogu.com.cn/problem/P1030

法一对于如果输入的不是字符串而是数字，稍加修改也是适用的

而法二只能是处理输入字符串的时候

题目描述

法一：

#include <bits/stdc++.h>
using namespace std;
string hou, zhong;
void build(int l1, int r1, int l2, int r2) // l1,r1是中序遍历数组范围
{
    if (l1 > r1)
        return;
    char root = hou[r2];
    cout << root;
    int p = l1;
    while (zhong[p] != root)
    {
        p++;
    }
    int cnt = p - l1;                   //截取长度
    build(l1, p - 1, l2, l2 + cnt - 1); //递归中序后序的左子树
    build(p + 1, r1, l2 + cnt, r2 - 1);
}
int main()
{
    cin >> zhong >> hou;
    build(0, zhong.size() - 1, 0, hou.size() - 1);

    return 0;
}

法二：

来自洛谷第一篇题解

首先，一点基本常识，给你一个后序遍历，那么最后一个就是根（如ABCD，则根为D）。

因为题目求先序，意味着要不断找根。

那么我们来看这道题方法：（示例）

中序ACGDBHZKX，后序CDGAHXKZB，首先可找到主根B；

那么我们找到中序遍历中的B，由这种遍历的性质，可将中序遍历分为ACGD和HZKX两棵子树，

那么对应可找到后序遍历CDGA和HXKZ（从头找即可）

从而问题就变成求1.中序遍历ACGD，后序遍历CDGA的树 2.中序遍历HZKX，后序遍历HXKZ的树；

接着递归，按照原先方法，找到1.子根A，再分为两棵子树2.子根Z，再分为两棵子树。

就按这样一直做下去（先输出根，再递归）；

模板概括为step1:找到根并输出

step2:将中序，后序各分为左右两棵子树；

step3:递归，重复step1,2；

代码如下

#include<bits/stdc++.h>
using namespace std;
void tree(string middle,string endd)
{  if(middle.size()>0)
{
     char c=endd[endd.size()-1]; //找根输出
     cout<<c;
     int k=middle.find(c);
     tree(middle.substr(0,k),endd.substr(0,k)); //递归左右子树
     tree(middle.substr(k+1),endd.substr(k,middle.size()-k-1));


}

}
int main()
{
    string a,b;
    ios::sync_with_stdio(false);
    cin>>a>>b;
    tree(a,b);
    cout<<endl;

    return 0;
}