Solutions CS101

Appearance

M27928: 遍历树 ​

dfs + sortings, http://cs101.openjudge.cn/practice/27928/

请你对输入的树做遍历。遍历的规则是：遍历到每个节点时，按照该节点和所有子节点的值从小到大进行遍历，例如：

        7
    /   |   \
  10    3     6

对于这个树，你应该先遍历值为3的子节点，然后是值为6的子节点，然后是父节点7，最后是值为10的子节点。

本题中每个节点的值为互不相同的正整数，最大不超过9999999。

输入

第一行：节点个数n (n<500)

接下来的n行：第一个数是此节点的值，之后的数分别表示它的所有子节点的值。每个数之间用空格隔开。如果没有子节点，该行便只有一个数。

输出

输出遍历结果，一行一个节点的值。

样例输入

sample1 input:
4
7 10 3 6
10
6
3

sample1 output:
3
6
7
10

样例输出

sample2 input:
6
10 3 1
7
9 2 
2 10
3 7
1

sample2 output:
2
1
3
7
10
9

来源

2024spring zht

思路：

  • 读入节点个数 n，然后依次读入 n 行，每一行的第一个数为该节点的值，后续数为它的所有直接孩子的值。
  • 使用字典存储各节点与它们子节点的关系。同时记录所有出现在“孩子”位置的节点，这样可以通过集合差运算找到根节点（根节点不会作为孩子出现）。
  • 如果某个元素等于当前节点，则直接输出该节点的值；如果某个元素是子节点，则递归地遍历该子节点。

递归天然是深度优先

python
def traverse(x, tree):
    # 当前节点及其所有子节点值
    group = [x] + tree[x]
    # 从小到大排序
    for val in sorted(group):
        if val == x:
            print(x)
        else:
            traverse(val, tree)


n = int(input())
tree = {}
all_children = set()

for _ in range(n):
    line = list(map(int, input().split()))
    val = line[0]
    tree[val] = line[1:]
    all_children.update(line[1:])

# 根节点 = 未作为子节点出现的节点
root = (set(tree.keys()) - all_children).pop()

traverse(root, tree)
python
# 李思哲 物理学院
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []


def traverse_print(root, nodes):
    if root.children == []:
        print(root.value)
        return
    pac = {root.value: root}
    for child in root.children:
        pac[child] = nodes[child]
    for value in sorted(pac.keys()):
        if value in root.children:
            traverse_print(pac[value], nodes)
        else:
            print(root.value)


n = int(input())
nodes = {}
children_list = []
for i in range(n):
    info = list(map(int, input().split()))
    nodes[info[0]] = TreeNode(info[0])
    for child_value in info[1:]:
        nodes[info[0]].children.append(child_value)
        children_list.append(child_value)
root = nodes[[value for value in nodes.keys() if value not in children_list][0]]
traverse_print(root, nodes)

总体思路分为三步：1.通过字典建立输入数据的父子关系；2.找到树的根（这里我将父节点和子节点分别用两个列表记录，最后使用集合减法）；3.通过递归实现要求的从小到大遍历。

感觉这种题目用字典写会更简洁，而且不再需要考虑如何将输入的值全部归入TreeNode类并建立父子关系的问题。

python
# 王铭健，工学院 2300011118
from collections import defaultdict
n = int(input())
tree = defaultdict(list)
parents = []
children = []
for i in range(n):
    t = list(map(int, input().split()))
    parents.append(t[0])
    if len(t) > 1:
        ch = t[1::]
        children.extend(ch)
        tree[t[0]].extend(ch)


def traversal(node):
    seq = sorted(tree[node] + [node])
    for x in seq:
        if x == node:
            print(node)
        else:
            traversal(x)


traversal((set(parents) - set(children)).pop())
python
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)

def main():
    n = int(sys.stdin.readline())
    tree = defaultdict(list)
    all_nodes = set()
    child_nodes = set()
    
    for _ in range(n):
        parts = list(map(int, sys.stdin.readline().split()))
        parent, *children = parts
        tree[parent].extend(children)
        all_nodes.add(parent)
        all_nodes.update(children)
        child_nodes.update(children)
    
    # 根节点 = 出现在 all_nodes 但没出现在 child_nodes 的那个
    root = (all_nodes - child_nodes).pop()
    
    def traverse(u):
        # 把 u 自己和它的所有直接孩子放一起排序
        group = tree[u] + [u]
        group.sort()
        for x in group:
            if x == u:
                print(u)
            else:
                traverse(x)
    
    traverse(root)

if __name__ == "__main__":
    main()
python
# 刘华君 物理学院
class Tree:
    def __init__(self, val):
        self.val = val
        self.children = []
        self.parent = None

    def add_child(self, child):
        self.children.append(child)
        child.parent = self

    def traverse(self):
        if self.children == []:
            print(self.val)
        else:
            tmp_nodes = self.children + [self]
            tmp_nodes.sort(key=lambda x: x.val)
            for node in tmp_nodes:
                if node.val != self.val:
                    node.traverse()
                else:
                    print(node.val)

def build_tree(n, nodes):
    for _ in range(n):
        values = list(map(int, input().split()))
        root_val = values[0]
        if root_val not in nodes:
            nodes[root_val] = Tree(root_val)
        t = nodes[root_val]
        for child_val in values[1:]:
            if child_val not in nodes:
                nodes[child_val] = Tree(child_val)
            child = nodes[child_val]
            t.add_child(child)
            child.parent = t

    root = None
    for root_val in nodes:
        if not nodes[root_val].parent:
            root = nodes[root_val]
            break

    return root

if __name__ == "__main__":
    nodes = {}
    n = int(input())
    root = build_tree(n, nodes)
    if root:
        root.traverse()
python
def dfs(node, graph, result):
    if node not in graph:  # 如果节点没有子节点
        result.append(node)
        return
    children = graph[node]
    temp = [node] + children
    temp.sort()
    for child in temp:
        if child == node:
            result.append(node)
        elif child in graph:  # 仅当子节点存在于图中时才进行递归
            dfs(child, graph, result)

def main():
    n = int(input())  # 节点个数
    graph = {}
    all_nodes = set()
    child_nodes = set()

    for _ in range(n):
        line = list(map(int, input().split()))
        node = line[0]
        all_nodes.add(node)
        if len(line) > 1:
            children = line[1:]
            graph[node] = children
            child_nodes.update(children)
        else:
            graph[node] = []  # 确保没有子节点的情况也在图中表示出来

    # 可能不只有一个根节点，找到所有顶层节点
    top_level_nodes = list(all_nodes - child_nodes)
    top_level_nodes.sort()

    result = []
    for node in top_level_nodes:
        dfs(node, graph, result)

    for node in result:
        print(node)

if __name__ == "__main__":
    main()