题解：P1305 新二叉树

· · 题解

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

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

dfs 顺序

对于每一层 dfs，要求包含一个参数 x 表示这一层 dfs 的父节点。接下来开始 dfs 遍历：

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

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

代码

#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);
}