当前位置：首页 > news >正文

SCAU18924--二叉树的宽度多解

news 2025/5/20 6:54:51

18924 二叉树的宽度

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题语言: G++;GCC

Description

二叉树的宽度指的是具有节点数目最多的那一层的节点个数。1/ \2   3/     4     
答案为2, 第二层节点数最多，为2个节点。

输入格式

共n行。
第一行一个整数n，表示有n个结点，编号为1至n,结点1为树根。（1<=n<=50）
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子

输出格式

输出二叉树的宽度。

输入样例

输出样例

方法一

#include <iostream>      // 输入输出流（cin, cout）
#include <vector>        // 动态数组容器（vector）
#include <queue>         // 队列容器（queue）
#include <utility>       // 工具库（pair）
#include <algorithm>     // 算法库（max）using namespace std;int main() {// 关闭同步，提高cin/cout速度（但在多线程环境下慎用）ios::sync_with_stdio(false);// 解除cin和cout的绑定，进一步提升速度cin.tie(nullptr);int n;  // 树的节点总数cin >> n;// lchild[u] 表示节点u的左孩子，rchild[u] 表示节点u的右孩子vector<int> lchild(n + 1, 0), rchild(n + 1, 0);// appear[u] 记录节点u作为父节点出现的次数（用于判断左右孩子）vector<int> appear(n + 1, 0);// 读入n-1条父子关系，构建树结构for (int i = 1; i < n; ++i) {int x, y;  // x是父节点，y是子节点cin >> x >> y;// 如果x第一次出现，y作为左孩子；否则作为右孩子if (appear[x] == 0) {lchild[x] = y;} else {rchild[x] = y;}appear[x]++;  // 记录x作为父节点的次数}// BFS队列，存储（节点编号，当前层号）queue<pair<int, int>> q;q.push({1, 1});  // 根节点是1，层号初始为1// cnt[d] 记录第d层的节点数量vector<int> cnt(n + 2, 0);// 开始BFS层次遍历while (!q.empty()) {// 取出队首元素pair<int, int> front = q.front();int u = front.first;   // 当前节点编号int d = front.second;  // 当前层号q.pop();cnt[d]++;  // 当前层的节点数+1// 如果左孩子存在，加入队列，层号+1if (lchild[u] != 0) {q.push({lchild[u], d + 1});}// 如果右孩子存在，加入队列，层号+1if (rchild[u] != 0) {q.push({rchild[u], d + 1});}}// 遍历所有层，找到最宽的层（即节点数最多的层）int max_width = 0;for (int i = 1; i <= n; ++i) {max_width = max(max_width, cnt[i]);}// 输出结果cout << max_width << "\n";return 0;
}

方法二

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义二叉树节点结构
typedef struct BiTNode {int data;                // 节点存储的数据struct BiTNode *lchild;  // 左孩子指针struct BiTNode *rchild;  // 右孩子指针
} BiTNode, *BiTree;          // BiTree是指向BiTNode的指针类型int main() {int n;  // 节点总数scanf("%d", &n);  // 读取节点数量// 动态分配节点指针数组（索引从1到n）// nodes是一个指针数组，每个元素指向一个BiTNode结构体BiTree *nodes = (BiTree *)malloc((n + 1) * sizeof(BiTree));// 初始化所有节点for (int i = 1; i <= n; i++) {nodes[i] = (BiTree)malloc(sizeof(BiTNode));  // 为每个节点分配内存nodes[i]->data = i;     // 设置节点数据（这里直接用节点编号作为数据）nodes[i]->lchild = NULL;  // 初始化左孩子为空nodes[i]->rchild = NULL;  // 初始化右孩子为空}// 构建二叉树结构for (int i = 1; i < n; i++) {int x, y;  // x是父节点，y是子节点scanf("%d %d", &x, &y);  // 读取父子关系// 将y挂到x的下面if (nodes[x]->lchild == NULL) {  // 如果x还没有左孩子nodes[x]->lchild = nodes[y];  // y作为x的左孩子} else {  // 如果x已经有左孩子nodes[x]->rchild = nodes[y];  // y作为x的右孩子}}// 开始层次遍历（BFS）计算二叉树宽度BiTree queue[100];  // 用数组模拟队列，存储待处理的节点int front = 0;      // 队列头指针int rear = 0;       // 队列尾指针int max_width = 0;  // 记录最大宽度// 将根节点（nodes[1]）加入队列if (n >= 1) {queue[rear++] = nodes[1];}// BFS主循环while (front < rear) {  // 当队列不为空时int level_size = rear - front;  // 当前层的节点数// 更新最大宽度if (level_size > max_width) {max_width = level_size;}// 处理当前层的所有节点for (int i = 0; i < level_size; i++) {BiTree node = queue[front++];  // 取出队首节点// 将左孩子加入队列（如果存在）if (node->lchild != NULL) {queue[rear++] = node->lchild;}// 将右孩子加入队列（如果存在）if (node->rchild != NULL) {queue[rear++] = node->rchild;}}}// 输出最大宽度printf("%d\n", max_width);// 释放动态分配的内存for (int i = 1; i <= n; i++) {free(nodes[i]);  // 释放每个节点}free(nodes);         // 释放节点指针数组return 0;
}

查看全文

http://www.xdnf.cn/news/531757.html