(B卷,200分)- 树状结构查询（Java & JS & Python）

题目描述

通常使用多行的节点、父节点表示一棵树，比如

西安 陕西
陕西 中国
江西 中国
中国 亚洲
泰国 亚洲

输入一个节点之后，请打印出来树中他的所有下层节点

输入描述

第一行输入行数，下面是多行数据，每行以空格区分节点和父节点

接着是查询节点

输出描述

输出查询节点的所有下层节点。以字典序排序

备注

树中的节点是唯一的，不会出现两个节点，是同一个名字

用例

题目解析

用例图示如下

需要打印c下面的所有子节点，即d,e,f节点，按照字典序输出后是d,e,f。 

本题其实就是让我们遍历树结构，可以使用深搜或者广搜。下面代码使用广搜。

关于本题树结构，可以使用Map结构实现，即key为父节点，value为子节点集合。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 1) {
    n = parseInt(lines[0]);
  }

  if (n && lines.length === n + 2) {
    lines.shift();

    const target = lines.pop();

    const tree = {};
    for (let str of lines) {
      const [ch, fa] = str.split(" ");
      if (!tree[fa]) tree[fa] = new Set();
      tree[fa].add(ch);
    }

    getResult(tree, target);

    lines.length = 0;
  }
});

function getResult(tree, target) {
  if (!tree[target]) return console.log("");

  const queue = [...tree[target]];

  const ans = [];
  while (queue.length > 0) {
    const node = queue.shift();
    ans.push(node);

    if (tree[node]) {
      queue.push(...tree[node]);
    }
  }

  ans.sort().forEach((v) => console.log(v));
}

Java算法源码

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    HashMap<String, HashSet<String>> tree = new HashMap<>();
    for (int i = 0; i < n; i++) {
      String ch = sc.next();
      String fa = sc.next();

      tree.putIfAbsent(fa, new HashSet<>());
      tree.get(fa).add(ch);
    }

    String target = sc.next();

    getResult(tree, target);
  }

  public static void getResult(HashMap<String, HashSet<String>> tree, String target) {
    if (!tree.containsKey(target)) {
      System.out.println("");
      return;
    }

    LinkedList<String> queue = new LinkedList<>(tree.get(target));

    ArrayList<String> ans = new ArrayList<>();

    while (queue.size() > 0) {
      String node = queue.removeFirst();
      ans.add(node);

      if (tree.containsKey(node)) queue.addAll(tree.get(node));
    }

    ans.sort(String::compareTo);

    ans.forEach(System.out::println);
  }
}

Python算法源码

# 输入获取
n = int(input())

tree = {}
for _ in range(n):
    ch, fa = input().split()
    tree.setdefault(fa, set())
    tree[fa].add(ch)

target = input()


# 算法入口
def getResult():
    if tree.get(target) is None:
        print("")
        return

    queue = list(tree[target])
    ans = []

    while len(queue) > 0:
        node = queue.pop(0)
        ans.append(node)

        if tree.get(node) is not None:
            queue.extend(list(tree[node]))

    ans.sort()
    for v in ans:
        print(v)


# 算法调用
getResult()