E卷-刷题笔记合集🔗

树状结构查询

问题描述

在树状结构中，我们经常使用节点和父节点的关系来表示一棵树。现在，给定一系列节点和其父节点的关系，以及一个查询节点，请找出并输出该查询节点的所有下层节点。

输入格式

第一行输入一个正整数 ，表示节点关系的数量。

接下来的 行，每行包含两个由空格分隔的字符串，分别表示节点和其父节点。

最后一行输入一个字符串，表示要查询的节点。

输出格式

按字典序输出查询节点的所有下层节点，每个节点占一行。

样例输入1

5
b a
c a
d c
e c
f d
c

样例输出1

d
e
f

样例解释

数据范围

• 
• 节点名称为非空字符串，长度不超过 50
• 树中的节点名称是唯一的

题解

哈希表+模拟

这道题目本质上是在处理一个树结构，需要找出给定节点的所有子孙节点。解决这个问题的关键在于如何有效地构建树结构并进行查询。

首先，需要选择一个合适的数据结构来表示这棵树。考虑到需要快速查找一个节点的所有子节点，使用哈希表（在Java中是HashMap，在Python中是dict）是一个很好的选择。可以用节点名作为键，其直接子节点列表作为值。

构建树的过程如下：

1. 遍历输入的每一对节点关系。
2. 对于每一对关系，将子节点添加到父节点的子节点列表中。

查询过程可以使用广度优先搜索（BFS）或深度优先搜索（DFS）。这里选择使用BFS，因为它能够按层次遍历节点，更符合题目要求的"下层节点"概念。

BFS的过程如下：

1. 将查询节点加入队列。
2. 当队列不为空时，取出队首节点。
3. 将该节点的所有子节点加入结果集和队列。
4. 重复步骤2-3，直到队列为空。

参考代码

• Python

from collections import defaultdict, deque

def find_descendants(tree, query):
    # 使用BFS查找所有后代节点
    queue = deque([query])
    descendants = set()
    
    while queue:
        node = queue.popleft()
        for child in tree[node]:
            if child not in descendants:
                descendants.add(child)
                queue.append(child)
    
    # 将结果转换为排序后的列表
    return sorted(list(descendants))

# 读取输入
n = int(input())  # 读取节点关系的数量
tree = defaultdict(list)  # 使用defaultdict来存储树结构

# 构建树结构
for _ in range(n):
    child, parent = input().split()
    tree[parent].append(child)

# 读取查询节点
query = input().strip()

# 查找并输出结果
result = find_descendants(tree, query)
for node in result:
    print(node)

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 1001
#define MAX_NAME_LENGTH 51

// 定义树节点结构
typedef struct TreeNode {
    char name[MAX_NAME_LENGTH];
    struct TreeNode* children[MAX_NODES];
    int childCount;
} TreeNode;

// 定义队列结构
typedef struct Queue {
    TreeNode* data[MAX_NODES];
    int front, rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

// 入队
void enqueue(Queue* q, TreeNode* node) {
    q->data[q->rear++] = node;
}

// 出队
TreeNode* dequeue(Queue* q) {
    return q->data[q->front++];
}

// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->front == q->rear;
}

// 比较函数，用于qsort
int compare(const void* a, const void* b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

// 查找节点
TreeNode* findNode(TreeNode* nodes[], int nodeCount, const char* name) {
    for (int i = 0; i < nodeCount; i++) {
        if (strcmp(nodes[i]->name, name) == 0) {
            return nodes[i];
        }
    }
    return NULL;
}

int main() {
    int n;
    scanf("%d", &n);

    TreeNode* nodes[MAX_NODES];
    int nodeCount = 0;

    // 读取输入并构建树
    for (int i = 0; i < n; i++) {
        char childName[MAX_NAME_LENGTH], parentName[MAX_NAME_LENGTH];
        scanf("%s %s", childName, parentName);

        TreeNode* childNode = findNode(nodes, nodeCount, childName);
        if (childNode == NULL) {
            childNode = (TreeNode*)malloc(sizeof(TreeNode));
            strcpy(childNode->name, childName);
            childNode->childCount = 0;
            nodes[nodeCount++] = childNode;
        }

        TreeNode* parentNode = findNode(nodes, nodeCount, parentName);
        if (parentNode == NULL) {
            parentNode = (TreeNode*)malloc(sizeof(TreeNode));
            strcpy(parentNode->name, parentName);
            parentNode->childCount = 0;
            nodes[nodeCount++] = parentNode;
        }

        parentNode-