3 树的遍历 7题

sy345: 树的先根遍历

现有一棵个结点的树（结点编号为从0到n-1，根结点为0号结点），求这棵树的先根遍历序列。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示树的结点个数；

接下来行，每行一个结点的子结点信息，格式如下：

text

k child_1 child_2 ... child_k

其中k表示该结点的子结点个数，child1、child2、...、childk表示子结点的编号。

输出

输出个整数，表示先根遍历序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

输出

0 2 1 6 4 5 3

解释

对应的树如下图所示，先根遍历序列为0 2 1 6 4 5 3。

树的先根遍历.png

python

class Node():
    def __init__(self, val, children=None):
        self.val = val
        self.children = children if children is not None else []

def pre_order(node):
    if node is None:
        return []
    result = [node.val]
    for child in node.children:
        result.extend(pre_order(child))
    return result

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    children = list(map(int, input().split()))[1:]
    nodes[i].children = [nodes[child] for child in children]

print(*pre_order(nodes[0]))

sy346: 树的后根遍历

https://sunnywhy.com/sfbj/9/3/346

现有一棵个结点的树（结点编号为从0到n-1，根结点为0号结点），求这棵树的后根遍历序列。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示树的结点个数；

接下来行，每行一个结点的子结点信息，格式如下：

text

k child_1 child_2 ... child_k

其中k表示该结点的子结点个数，child1、child2、...、childk表示子结点的编号。

输出

输出个整数，表示后根遍历序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

输出

1 6 2 4 3 5 0

解释

对应的树如下图所示，后根遍历序列为1 6 2 4 3 5 0。

树的先根遍历.png

python

class Node():
    def __init__(self, val, children=None):
        self.val = val
        self.children = children if children is not None else []

def post_order(node):
    if node is None:
        return []
    result = []
    for child in node.children:
        result.extend(post_order(child))
    result.append(node.val)
    return result

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    children = list(map(int, input().split()))[1:]
    nodes[i].children = [nodes[child] for child in children]

print(*post_order(nodes[0]))

sy347: 树的层序遍历

https://sunnywhy.com/sfbj/9/3/347

现有一棵个结点的树（结点编号为从0到n-1，根结点为0号结点），求这棵树的层序遍历序列。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示树的结点个数；

接下来行，每行一个结点的子结点信息，格式如下：

text

k child_1 child_2 ... child_k

其中k表示该结点的子结点个数，child1、child2、...、childk表示子结点的编号。

输出

输出个整数，表示层序遍历序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

输出

0 2 4 5 1 6 3

解释

对应的树如下图所示，层序遍历序列为0 2 4 5 1 6 3。

树的先根遍历.png

python

class Node():
    def __init__(self, val, children=None):
        self.val = val
        self.children = children if children is not None else []

def level_order(root):
    if root is None:
        return []
    queue = [root]
    traversal = []
    while queue:
        node = queue.pop(0)
        traversal.append(node.val)
        queue.extend(node.children)
    return traversal

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    children = list(map(int, input().split()))[1:]
    nodes[i].children = [nodes[child] for child in children]

print(*level_order(nodes[0]))

sy348: 树的高度

https://sunnywhy.com/sfbj/9/3/348

现有一棵个结点的树（结点编号为从0到n-1，根结点为0号结点），求这棵树的高度。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示树的结点个数；

接下来行，每行一个结点的子结点信息，格式如下：

text

k child_1 child_2 ... child_k

其中k表示该结点的子结点个数，child1、child2、...、childk表示子结点的编号。

输出

输出一个整数，表示树的高度。

样例1

输入

输出

解释

对应的树如下图所示，高度为3。

树的先根遍历.png

python

class Node():
    def __init__(self, val, children=None):
        self.val = val
        self.children = children if children is not None else []

def height(node):
    if node is None:
        return 0
    if not node.children:
        return 1
    return max(height(child) for child in node.children) + 1

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    children = list(map(int, input().split()))[1:]
    nodes[i].children = [nodes[child] for child in children]

print(height(nodes[0]))

sy349: 树的结点层号

https://sunnywhy.com/sfbj/9/3/349

现有一棵个结点的树（结点编号为从0到n-1，根结点为0号结点），求这棵树的所有结点的层号（假设根结点的层号为1）。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示树的结点个数；

接下来行，每行一个结点的子结点信息，格式如下：

text

k child_1 child_2 ... child_k

其中k表示该结点的子结点个数，child1、child2、...、childk表示子结点的编号。

输出

输出个整数，分别表示编号从0到n-1的结点的层号，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

输出

1 3 2 3 2 2 3

解释

对应的树如下图所示，层号为1的结点编号为0，层号为2的结点编号为2、4、5，层号为3的结点编号为1、6、3。

树的先根遍历.png

python

n = int(input().strip())
tree = [[] for _ in range(n)]
levels = [0 for _ in range(n)]

for i in range(n):
    line = list(map(int, input().strip().split()))
    k = line[0]
    for j in range(1, k + 1):
        tree[i].append(line[j])

q = [(0, 1)]
while q:
    node, level = q.pop(0)
    levels[node] = level
    for child in tree[node]:
        q.append((child, level + 1))

print(' '.join(map(str, levels)))

python

class Tree:
    def __init__(self, n):
        self.n = n
        self.tree = [[] for _ in range(n)]
        self.levels = [0 for _ in range(n)]

    def add_node(self, node, children):
        self.tree[node] = children

    def bfs(self):
        q = [(0, 1)]
        while q:
            node, level = q.pop(0)
            self.levels[node] = level
            for child in self.tree[node]:
                q.append((child, level + 1))

    def print_levels(self):
        print(' '.join(map(str, self.levels)))


n = int(input().strip())
tree = Tree(n)

for i in range(n):
    line = list(map(int, input().strip().split()))
    k = line[0]
    children = line[1:k+1]
    tree.add_node(i, children)

tree.bfs()
tree.print_levels()

sy350: 树的路径和

https://sunnywhy.com/sfbj/9/3/350

现有一棵个结点的树（结点编号为从0到n-1，根结点为0号结点），每个结点有各自的权值。

结点的路径和是指，从根结点到该结点的路径上所有结点的权值之和；
树的路径和是指，树所有叶结点的路径和之和。

求这棵树的路径和。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示树的结点个数；

第二行个整数，分别给出编号从0到n-1的个结点的权值 $w (1 \leq w \leq 100)$ ，；

接下来行，每行一个结点的子结点信息，格式如下：

text

k child_1 child_2 ... child_k

其中k表示该结点的子结点个数，child1、child2、...、childk表示子结点的编号。

输出

输出一个整数，表示树的路径和。

样例1

输入

7
3 5 1 1 2 4 2
3 2 4 5
0
2 1 6
0
0
1 3
0

输出

解释

对应的树如下图所示，其中黑色数字为结点编号，编号右下角的灰色数字为结点权值。由此可得叶结点1的路径和为，叶结点6的路径和为，叶结点4的路径和为，叶结点3的路径和为，因此二叉树的路径和为。

树的路径和.png

python

n = int(input().strip())
weights = list(map(int, input().strip().split()))
tree = [[] for _ in range(n)]

for i in range(n):
    line = list(map(int, input().strip().split()))
    k = line[0]
    for j in range(1, k + 1):
        tree[i].append(line[j])

def dfs(node, path_sum):
    path_sum += weights[node]
    if not tree[node]:  # if the node is a leaf node
        return path_sum
    return sum(dfs(child, path_sum) for child in tree[node])

result = dfs(0, 0)
print(result)

sy351: 树的带权路径长度

https://sunnywhy.com/sfbj/9/3/351

现有一棵个结点的树（结点编号为从0到n-1，根结点为0号结点），每个结点有各自的权值。

结点的路径长度是指，从根结点到该结点的边数；
结点的带权路径长度是指，结点权值乘以结点的路径长度；
树的带权路径长度是指，树的所有叶结点的带权路径长度之和。

求这棵树的带权路径长度。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示树的结点个数；

第二行个整数，分别给出编号从0到n-1的个结点的权值（）；

接下来行，每行一个结点的子结点信息，格式如下：

text

k child_1 child_2 ... child_k

其中k表示该结点的子结点个数，child1、child2、...、childk表示子结点的编号。

输出

输出一个整数，表示树的带权路径长度。

样例1

输入

7
3 5 1 1 2 4 2
3 2 4 5
0
2 1 6
0
0
1 3
0

输出

解释

对应的树如下图所示，其中黑色数字为结点编号，编号右下角的格式为结点权值*结点路径长度=结点带权路径长度。由此可得树的带权路径长度为。

树的带权路径长度.png

python

class TreeNode:
    def __init__(self, weight=0):
        self.weight = weight
        self.children = []

def build_tree(weights, edges):
    nodes = [TreeNode(weight=w) for w in weights]
    for i, children in enumerate(edges):
        for child in children:
            nodes[i].children.append(nodes[child])
    return nodes[0]  # 返回根节点

def dfs(node, depth):
    # 如果当前节点是叶子节点，则返回其带权路径长度
    if not node.children:
        return node.weight * depth
    # 否则，递归遍历其子节点
    total_weight_path_length = 0
    for child in node.children:
        total_weight_path_length += dfs(child, depth + 1)
    return total_weight_path_length

def weighted_path_length(n, weights, edges):
    # 构建树
    root = build_tree(weights, edges)
    # 从根节点开始深度优先搜索
    return dfs(root, 0)

# 输入处理
n = int(input().strip())
weights = list(map(int, input().strip().split()))
edges = []
for _ in range(n):
    line = list(map(int, input().strip().split()))
    if line[0] != 0:  # 忽略没有子节点的情况
        edges.append(line[1:])
    else:
        edges.append([])

# 计算带权路径长度
print(weighted_path_length(n, weights, edges))

3 树的遍历 7题 ​

sy345: 树的先根遍历 ​

sy346: 树的后根遍历 ​

sy347: 树的层序遍历 ​

sy348: 树的高度 ​

sy349: 树的结点层号 ​

sy350: 树的路径和 ​

sy351: 树的带权路径长度 ​

3 树的遍历 7题

sy345: 树的先根遍历

sy346: 树的后根遍历

sy347: 树的层序遍历

sy348: 树的高度

sy349: 树的结点层号

sy350: 树的路径和

sy351: 树的带权路径长度