用C语言求二叉树中的结点个数叶子结点个数某结点层次和二叉树宽度

在C语言中，我们可以使用递归的方式来求解二叉树的相关信息：

1. **节点总数**：对于每个节点，它可能是叶节点、左子节点、右子节点或者是根节点。计算节点总数时，需要对每个节点都计数一次。可以定义一个函数，例如`countNodes(node *root)`，该函数接收根节点作为参数，返回整个树的节点数。初始化为0，然后递归遍历所有子节点。

int countNodes(node* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

2. **叶节点个数**：同样递归处理，如果节点没有孩子，则它是叶节点。在`countNodes`函数中添加一个检查条件即可。

int leafCount(node* root) {
    if (root == NULL || (root->left == NULL && root->right == NULL)) return 1;
    return countNodes(root->left) + countNodes(root->right);
}

3. **某结点层次**：使用队列（广度优先搜索）可以帮助我们按层遍历二叉树，同时记录当前层的节点数量。当访问到目标节点时，它的层次就是队列长度减一。这里需要一个辅助函数`getNodeLevel(node *root, int targetNode, int level)`。

4. **二叉树宽度**（最大宽度）：每次从上一层移向下一层时，记录当前层的最大节点数，因为宽度通常是指每一层的最大节点数。可以使用类似深度优先搜索的方法，每遇到新的一层就更新最大宽度。

int maxWidth(node* root) {
    int maxWidth = 0, levelWidth[100] = {0}; // 假设最多有100层
    queue<int> q;

    if (root != NULL) {
        q.push(1); // 根节点的层级为1
        levelWidth[1] = 1; // 第1层只有一个节点

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                node* node = tree[q.front()];
                q.pop();

                if (node->left) q.push(node->left->level + 1);
                if (node->right) q.push(node->right->level + 1);

                levelWidth[node->level]++;
                maxWidth = MAX(maxWidth, levelWidth[node->level]);
            }
        }
    }

    return maxWidth;
}