洛谷P1160 队列安排 P1040 加分二叉树-------树的遍历

遍历的分类

前序遍历：621 43 8

中序遍历：1 23 46 8

后序遍历：1 34 28 6

层序遍历：6 28 14 3

 

突然发现

这个坑一直留到了现在

那么先从遍历说起

前序遍历：根节点-左子树-右子树

中序遍历：左子树-根节点-右子树

后序遍历：左子树-右子树-根节点

每个子树里依然遵循先前的遍历顺序

用dfs可以实现

来看一道中序遍历的题，很好玩

洛谷P1160

这一题说白了就是最简单的插入操作

用stl和结构体都是一样的

另外 还记得上学期复习链表的时候 插入操作是什么样的嘛

比如现在有链表A->C

要在ac之间插入一个b

那么操作就是：

A->B

B->C

这道题我的思路是一样的

就是一个插入的过程

 

这图有点大

定义一个结构体

struct node{
    int ls = -1, rs = -1, v = 0;
} a[maxn];//总共是要有n个小同学的，a的下标就是小同学的编号

 

每个节点的左边那个箭头，就是ls 右边的箭头 就是rs

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 100;
struct node{
    int ls = -1, rs = -1, v = 0;
} a[maxn];//总共是要有n个小同学的，a的下标就是小同学的编号
void dfs(int x){
    if(x==-1)return;
    dfs(a[x].ls);
    if(a[x].v!=1)
        printf("%lld ", x);
    dfs(a[x].rs);
}
int32_t main(){
    int n, m,x,p;
    cin >> n;
    for (int i = 2; i <= n;i++){//i是现在入队的同学的编号
        scanf("%lld%lld", &x, &p);
        if (p == 0){ //left
            if(a[x].ls!=-1){
                int t = a[x].ls;
                a[x].ls = i;
                a[i].ls = t;
            }
            else
                a[x].ls = i;
        }
        if(p==1){//right
            if(a[x].rs!=-1){
                int t = a[x].rs;
                a[x].rs = i;
                a[i].rs = t;
            }
            else
                a[x].rs = i;
        }
    }
    scanf("%lld", &m);
    for (int i = 1; i <= m;i++){
        scanf("%lld", &x);
        a[x].v = 1;
    }
    dfs(1);
    system("pause");
    return 0;
}

 我的天哪

我这是什么记性

一个题解写了两遍..........................................

记性太好了

 

 

P1040 加分二叉树

还有一题，这个题目在dfs的训练块里面，但其实是dp的题目，遍历在这里只是很小的一个部分

这个是一道很经典很棒的题，和之前做过的一道题很像，应该是在kuangbin专题的简单dp里面做的

这个题目描述我觉得有一点点不太好理解，但是很明显是一道dp，那就能猜出这题其实想要问的是什么啦

题解里说这个是区间dp/树形dp

其实我觉得，也算是一个正常的dp的分析吧，不提前学这类知识也是可以做的

代码：

#include<bits/stdc++.h>
#define int long long
#define sys system("pause");
using namespace std;
#define N 32
int dp[N][N], ans,n,root[N][N],v[N];
void build(int n){
    for (int i = 1; i <= n;i++){
        dp[i][i-1] = 1;//*****这个地方我本来写的是dp[i-1][i],但是这样是错的，可以想到原因，这个地方是将空树的节点设为1，如果是i-1~i那是不对的
        dp[i][i] = v[i];//根节点的赋值
    }
}
void dfs(int l,int r){//这是一个前序遍历
    if(l>r)
        return;
    if(l==r){
        printf("%lld ",l);
        return;
    }
    printf("%lld ", root[l][r]);
    dfs(l, root[l][r]-1);
    dfs(root[l][r] + 1, r);
}
void init(){
     scanf("%lld", &n);
    for (int i = 1; i <= n;i++)
        scanf("%lld", &v[i]);
}
int32_t main(){
    init();
    build(n);
    for (int i = n; i >= 1;i--)
        for (int j = i + 1; j <= n;j++)
            for (int k = i; k <= j;k++)//这三个循环是不是似曾相识？
                if(dp[i][j]<dp[i][k - 1] * dp[k + 1][j] + dp[k][k]){
                    dp[i][j] = dp[i][k - 1] * dp[k + 1][j] + dp[k][k];
                    root[i][j] = k;//要重新选取谁作为根节点
                }
    printf("%lld\n", dp[1][n]);
    dfs(1, n);
    sys return 0;
}