题解：P1305 新二叉树

~~我也不知道这二叉树哪里新了。~~

这是一道二叉树先序遍历模板。

dfs 顺序

对于每一层 dfs，要求包含一个参数

x

表示这一层 dfs 的父节点。接下来开始 dfs 遍历：

输出根节点 $x$ 。
如果 $x$ 没有子节点，返回上一层。
将根节点 $x$ 的左节点 $L_x$ 作为新的根节点，启动另一个 dfs，参数为 $L_x$ ，回到第 $1$ 步；
将根节点 $x$ 的右节点（如果有） $R_x$ 作为新的根节点，启动另一个 dfs，参数为 $R_x$ ，回到第 $1$ 步。

当所有节点遍历完毕，本题完。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 'z'+5;

int n, cnt;
char Lson[N], Rson[N];

void dfs(char u){
    // 空节点返回 
    if(u == '*') return;
    // 输出根节点 
    cout << u;
    // 遍历左子节点 
    dfs(Lson[u]);
    // 遍历右子节点 
    dfs(Rson[u]);
}

int main(){
    cin >> n; char father;
    for(int i=1; i<=n; i++){
        char f, L, R; cin >> f >> L >> R;
        // 题目保证第一行的节点是根节点  
        if(i == 1) father = f;
        // 保存左右子节点
        Lson[f] = L, Rson[f] = R;
    }
    
    // 从最大的根开始遍历 
    dfs(father);
}

题解：P1305 新二叉树

文章操作

dfs 顺序

代码

相关推荐

评论

题解：P1305 新二叉树