C++例题小葱的树2

Question

原题如下：
小葱有一颗树，这棵树有n个节点，n−1
条边，点的编号是1,2,⋯,n。
小葱对树很熟悉了，树的深度、树的各种遍历，她都会求。
现在小葱想知道树的宽度是多少！
小葱对宽度的定义是：树的的节点数最多的那一层的节点数。

输入描述
第一行一个数字n。 随后n−1行，每行一对数字，代表一条边。 最后一行一个数字，代表根节点的编号。

输出描述
一行一个数字，代表树的宽度。

输入样例
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2

输出样例
8

我的原来写的代码（一直崩溃而且还错）：

#include<bits/stdc++.h>

using namespace std;

typedef struct Bitree {
    int ch;
    Bitree* chs[151];
};

int treeWidth(Bitree *root){
  if(!root){
    return 0;
  }
  int width = 0;
  int maxWidth = 0;
  queue<Bitree *> Q;
  Bitree *p = 0;
  Q.push(root);
  while(!Q.empty()){
    width = Q.size();
    if(maxWidth < width){
      maxWidth = width;
    }
    for(int i=0; i<width; i++){
      p = Q.front();
      Q.pop();
      for (int i = 0; i < p->ch; i++)
        Q.push(p->chs[i]);
    }
  }
  return maxWidth;
}

int n;
Bitree tr[101];
int root,N;

int main() {
    int n;
    vector<int> e[N];
    cin >>n;
    for(int i=1;i< n; i++){
        int x,y;
        cin >>x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    cin >>root;
    cout <<treeWidth(tr + root);
    return 0;
}

能看看出什么问题了吗？

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

你的代码确实存在一些问题，我会逐一指出并提供修改建议：

1. Bitree结构体定义错误：确实，如果树是二叉树，chs数组的大小应该是2。但是，根据题目描述，这棵树不一定是二叉树，因此chs数组的大小应该足够大以容纳所有可能的子节点。可以使用vector代替固定大小的数组。

2. treeWidth函数中for循环变量重复使用：你已经注意到了这个问题，应该声明两个不同的循环变量。

3. treeWidth函数中未初始化Bitree结构体成员：在main函数中构建树时，需要初始化每个节点的ch和chs。

4. e数组大小错误：e数组的大小应该是n+1，因为节点编号从1开始，数组索引从0开始。

5. 根节点编号未转换：读取根节点编号后，需要减去1以转换为从0开始的索引。

6. treeWidth函数调用参数错误：调用treeWidth时，应该传入&tr[root]。

7. Bitree数组未初始化和树结构未构建：需要在main函数中初始化Bitree数组，并根据输入构建树结构。

以下是修改后的代码示例：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Bitree {
    vector<Bitree*> chs; // 使用vector代替固定大小的数组
    int ch; // 子节点数量
};

Bitree* buildTree(vector<vector<int>>& edges, int root) {
    Bitree* trees = new Bitree[edges.size() + 1]; // 假设树的大小为edges.size() + 1
    for (int i = 0; i <= edges.size(); ++i) {
        trees[i].chs = vector<Bitree*>();
        trees[i].ch = 0;
    }
    for (auto& edge : edges) {
        trees[edge[0] - 1].chs.push_back(&trees[edge[1] - 1]);
        trees[edge[1] - 1].chs.push_back(&trees[edge[0] - 1]);
        trees[edge[0] - 1].ch++;
        trees[edge[1] - 1].ch++;
    }
    return &trees[root - 1]; // 转换为从0开始的索引
}

int treeWidth(Bitree* root) {
    if (!root) return 0;
    queue<Bitree*> Q;
    int width = 0, maxWidth = 0;
    Q.push(root);
    while (!Q.empty()) {
        width = Q.size();
        if (maxWidth < width) {
            maxWidth = width;
        }
        for (int i = 0; i < width; ++i) {
            Bitree* p = Q.front();
            Q.pop();
            for (auto ch : p->chs) {
                Q.push(ch);
            }
        }
    }
    return maxWidth;
}

int main() {
    int n, root;
    cin >> n;
    vector<vector<int>> edges(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        edges[i] = {x, y};
    }
    cin >> root;
    Bitree* tr = buildTree(edges, root);
    cout << treeWidth(tr) << endl;
    delete[] tr; // 释放树内存
    return 0;
}

请注意，这个代码示例假设了树的大小足够大，并且已经根据输入构建了树结构。此外，我添加了buildTree函数来构建树，并在main函数中调用它。最后，不要忘记释放分配的内存。