HugeYlh

奔赴山海，保持热爱

0%

二叉树练习（基础 1）

发表于 分类于 阅读次数： Valine：
本文字数： 7.5k 阅读时长 ≈ 14 分钟
本文主要讲解了二叉树的一些基础练习题，包括树的深度，高度，最短路径，三种遍历的转换，树结构等，并附带完整代码与详细解释，后序是出二叉树的进阶练习题

文章首发于：My Blog 欢迎大佬们前来逛逛

P4715 【深基16.例1】淘汰赛

P4715 【深基16.例1】淘汰赛

根据输入的n便可以得知：共有 2^n 个节点。

我们需要求得亚军是谁，那么我们就是要求第二个是谁。

冠军是谁？

1
4 2 3 1 10 5 9 7

假如把这个序列左右部分切开，那么冠军是一定是左边最大，右边最大的最大的那一个。

这样我们就可以看出一个树的结构：

依次比较两个节点的值，求出两个节点的较大者为他们两个的“父节点”

这样依次往上，从叶子节点到根节点，最终还剩两个节点，则较小的就是亚军。

注意我们得到的是节点的值，但是我们需要得到这个节点的编号，因此使用一个节点体记录每个节点的编号与值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//TODO: Write code here
int n,m;
const int N=1e5+10;
struct Node
{
    int num,val;
}node[N];
signed main()
{
    cin>>n;
    int ans=0;
    int len=pow(2,n);
    for (int i=1;i<=len;i++){
        cin>>node[i].val;
        node[i].num=i;
    }
    while (len!=1){
        if (len==2){//直到最后还剩两个节点
            if (node[1].val>=node[2].val){
                ans=node[2].num;
            }else{
                ans=node[1].num;
            }
            break;
        }
        for (int i=1,j=1;i<=len;i+=2,j++){
            if (node[i].val>=node[i+1].val){
                node[j]=node[i];
            }
            else{
                node[j]=node[i+1];
            }
        }
        len>>=1;
    }
    cout<<ans;
#define one 1
	return 0;
}

P4913 【深基16.例3】二叉树深度

P4913 【深基16.例3】二叉树深度

直接递归遍历这棵二叉树，同时统计一个cnt，每进入一次递归，则cnt+1，最后到达null节点，则ans统计这个时候的 cnt的最大值。

还有没有另外的做法？

扩展：求深度也可以使用最短路径来求，例如 使用 floyd算法得到 根节点到每个节点 的距离，规定根节点到与之相邻孩子节点的距离是1，则如果这个 dp[1] [i] 的值是存在的，则统计 1 -> i的距离的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//TODO: Write code here
int n,m;
const int N=1e5+10;
int nums[N],ans;
struct Node
{
    int l,r;
}node[N];
void dfs(int i,int cnt){
    if (node[i].l==0 && node[i].r==0){
        ans=max(ans,cnt);
        return;
    }
    dfs(node[i].l,cnt+1);
    dfs(node[i].r,cnt+1);
}
signed main()
{
	cin>>n;
    for (int i=1;i<=n;i++){
        cin>>node[i].l>>node[i].r;
    }
    dfs(1,1);
    cout<<ans;
#define one 1
	return 0;
}

P1827 中序与前序，求出后序

P1827 [USACO3.4] 美国血统 American Heritage

前序遍历：根左右

中序遍历：左根右

如果得到了 根节点，则我们就能推出一个分治的过程，根节点的左边是左孩子部分，根节点的右边是右孩子部分，其中每个左右孩子部分又可以得到根节点，然后重复这一过程：

这里介绍STL的方法：

1
2
3
4
find(root);	//返回root的位置，返回值是 size_t 的值，从0开始，如果在头部找到，则返回0
erase(xxx);//删除某一个位置
substr(beg,len)//从beg开始，截取len个元素
substr(beg);	//只有一个beg位置，则截取beg到end的后面的所有元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs1(string mid,string pre){
    /*
    前序中序 -> 后序
    */
    if (mid.size()==0 || pre.size()==0){
        return;
    }
    char root=pre.front();//前序遍历的根节点
    pre.erase(pre.begin());//删除pre的根节点
    auto root_it=mid.find(root);	//中序遍历寻找此根节点
    //寻找中序遍历的left部分和right部分
    string mid_left=mid.substr(0,root_it);
    string mid_right=mid.substr(root_it+1);
    //寻找前序遍历的left部分和right部分
    string pre_left=pre.substr(0,root_it);
    string pre_right=pre.substr(root_it);
    //后序：左右根形式输出
    dfs1(mid_left,pre_left);//左
    dfs1(mid_right,pre_right);//右
    cout<<root;//根
}

P1030 中序与后序，求出前序

P1030 [NOIP2001 普及组] 求先序排列

后序遍历：左右根

中序遍历：左根右

只要知道了前序遍历或者后序遍历，再加上中序遍历，就可以推出另一种形式。

但是请注意：后序遍历和前序遍历是无法得到一个唯一的中序遍历的。

这里使用STL的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs2(string mid,string last){
    /*
    后序中序 -> 前序
    */
    if (mid.size()==0 || last.size()==0){
        return;
    }
    char root=last.back();//后序遍历的根节点
    last.pop_back();      //删除last的根节点
    auto root_it=mid.find(root);
    //中序的left部分和right部分
    string center_left=mid.substr(0,root_it);
    string center_right=mid.substr(root_it+1);
    //后序的left部分和right部分
    string last_left=last.substr(0,root_it);
    string last_right=last.substr(root_it);
    //前序形式输出：根左右
    cout<<root;//根
    dfs2(center_left,last_left);//左
    dfs2(center_right,last_right);//右
}

P1229 前序和后序，求出所有中序的次数

P1229 遍历问题

前面我们说过：由前序遍历和后序遍历无法确定一个唯一的中序遍历

这道题就是让我们求中序遍历的所有可能的数量

假如一个节点A只有一个孩子节点B，则思考一下：无论B是A的左孩子还是右孩子，它的前序遍历和后序遍历都是一致的。

因此如果要找到不同的中序遍历的情况，则一定是存在上述的情况。

A的孩子节点B只存在一个，这样就能确定两种情况；

如果A也是它的父亲节点 X 的唯一的孩子，那么A的左右改变又可以确定两种情况，加上A自己的，一共有四种情况。

  • 一颗树存在两个单孩子节点，则这棵树就具有四种中序，即具有 2^ n个 中序的情况，n表示单孩子节点的个数

如何确定一个单孩子节点？

前序遍历：ABC

后序遍历：CBA

假设它是一个一条直线，左斜的形状

  • 则A的孩子节点B在前序中呈：AB，在后序中呈：BA
  • 则B的孩子节点C在前序中呈：BC，在后序中呈：CB

则仅需判断在中序遍历中A的后继是B，如果在后序遍历中A的前驱是B，则说明为一个情况，n++

最后 2^n即为中序的所有次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//TODO: Write code here
int n,m;
const int N=1e5+10;
int nums[N];
signed main()
{
	string q,h;
    cin>>q>>h;
    int ans=0;
    for (int i=0;i<q.length();i++){
        for (int j=0;j<h.length();j++){
            //q[i]==h[j] && q[i+1]==h[j-1] 
            if (i+1<q.length() && j-1>=0 && q[i]==h[j] && q[i+1]==h[j-1]){
                ++ans;
            }
        }
    }
    cout<<(1<<ans);
#define one 1
	return 0;
}

P1364 医院设置

P1364 医院设置

这道题的是一个典型的求段路径问题。

要使得在一个节点处建立医院，使得其他节点到这个节点的最短路径最小，不就是求最短路径？

每两个节点的距离是1，因此求出这个最短距离后再乘以节点本身的值然后相加即可

最短路径的求法： floyd算法，dijkstra算法，spfa算法；

这里附上floyd算法：floyd使用三重循环，求得任何两个点的最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//TODO: Write code here
int n,m;
const int N=5e2+10;
int nums[N],dp[N][N];
void floyd(){
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
}
signed main()
{
	cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for (int i=1;i<=n;i++){
        int b,c;
        cin>>nums[i]>>b>>c;
        //两点之间距离的初始化
        dp[i][b]=dp[i][c]=dp[b][i]=dp[c][i]=1;
        dp[b][b]=dp[i][i]=dp[c][c]=0;
    }
    //计算两点之间的最短路径
    floyd();
    int ans=INF;
    for (int i=1;i<=n;i++){
        int ones=0;
        //以顶点 i 为起点，到某一点的最小距离和
        for (int j=1;j<=n;j++){
            ones+=dp[i][j]*nums[j];
        }
        ans=min(ans,ones);
    }
    cout<<ans;
#define one 1
	return 0;
}

* P1305 新二叉树

P1305 新二叉树

这道题的关键是选择合适的数据结构来存储这棵树，输出树的前序遍历很简单

如果选择合适的数据结构？

  • 由于树的节点不会有重复的，n<=26，则我们使用ASCII码来表示下标，因为ASCII码也是唯一的 ，而且很小，我们可以借助ASCII码当作数组的下标来轻松访问其相应的左右孩子节点，使用结构体存储left与right孩子，pair也行。

1. Ascii码用作数组的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//TODO: Write code here
int n,m;
const int N=1e5+10;
int nums[N];
struct Tree
{
    char left,right;
}tree[N];
char cur,root;
void dfs(char i){
    if (i=='*'){
        return;
    }
    cout<<i;
    dfs(tree[i].left);
    dfs(tree[i].right);
}
signed main()
{
	cin>>n;
    string in;
    //便于在dfs时确定root的位置
    cin>>root;
    cin>>tree[root].left>>tree[root].right;
    //正常遍历
    for (int i=2;i<=n;i++){
        cin>>cur;
        cin>>tree[cur].left>>tree[cur].right;
    }
    dfs(root);
#define one 1
	return 0;
}

2. 寻找根节点

方法二：

  • 使用一个 n维3列的char数组来表示这棵树，[0]表示根节点的字符，[1] [2]分别表示左右孩子；我们便可以每次dfs的时候，直接寻找每一层的所有节点，如果这个节点的父亲为当前的root，则进入此节点的递归。

为什么遍历每一层寻找父亲节点等于root的节点就是当前需要dfs的节点？

  • 因为是前序遍历，根在前，所有当前层的所有节点都是一个根，即从根开始dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//TODO: Write code here
int n,m;
const int N=1e5+10;
int nums[N];
char arr[50][3];
void dfs(char root){
    if (root=='*'){
        return;
    }
    cout<<root;
    for (int i=1;i<=n;i++){
        if (arr[i][0]==root){
            dfs(arr[i][1]);
            dfs(arr[i][2]);
        }
    }
    
}
signed main()
{
	cin>>n;
    string in;
    for (int i=1;i<=n;i++){
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }
    dfs(arr[1][0]);
#define one 1
	return 0;
}

* P3884 求二叉树深度，宽度，uv距离

P3884 [JLOI2009]二叉树问题

深度如何求？

  • dfs遍历树，然后记录一个cnt，更新最大深度 deep_max？可以，但是没有必要

宽度如何求？

  • 使用bfs层序遍历，维护一个queue，然后记录每一层的queue的元素数量（left入，right入），queue存储的就是每一层的元素个数就是宽度，然后不断的循环，直到queue为0，则遍历完成，kuan_max每次取得 queue.size()与它的最大值? 没有必要

两个节点之间的距离？

  • 最短路径，三种随便选择一个即可，我选择 floyd

如果我们知道了 这个最短距离不就知道了 宽度与深度了吗，那我们就没有必要写两个算法求了。

深度如何知道？

  • 根节点 1 到任意一点的最短距离的长度的最大值，就是深度的最大值（两个节点之间dis=1）

宽度如何知道？

  • 根节点到 两个点 i j 的最短距离都是 n，则这 i j 属于同一层，属于同一层的最短距离一定相同，记录每一层的最短距离相同的元素的数量即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//TODO: Write code here
int n,m;
const int N=1e2+10;
int nums[N],dp[N][N];
signed main()
{
	cin>>n;
    int a,b;
    memset(dp,0x3f,sizeof(dp));
    for (int i=1;i<=n-1;i++){
        cin>>a>>b;
        dp[a][b]=1; //父亲到孩子的距离是1
        dp[b][a]=2; //孩子到父亲的距离是2
        dp[a][a]=dp[b][b]=0;
    }
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
    int deep=0;
    //深度
    for (int i=1;i<=n;i++){
        deep=max(deep,dp[1][i]);
    }
    //宽度
    int kuan[N]{};
    int kuan_dis=0;
    for (int i=1;i<=n;i++){
        ++kuan[dp[1][i]];//每一层到根节点的距离都是一样的
        kuan_dis=max(kuan_dis,kuan[dp[1][i]]);
    }
    
    int u,v;
    cin>>u>>v;
    cout<<deep+1<<endl;
    cout<<kuan_dis<<endl;
    //uv之间的距离
    cout<<dp[u][v]<<endl; 
#define one 1
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！

欢迎关注我的其它发布渠道