目录😋
计算二叉树的结点个数、叶子结点个数、某结点的层次和二叉树的宽度
本关任务
编写一个程序验证二叉树的性质。
相关知识
为了完成本关任务，你需要掌握：
- 根据二叉树的括号表示串，创建二叉树b。
- 计算二叉树的结点个数、叶子结点个数、某结点的层次和二叉树的宽度。
根据二叉树的括号表示串，创建二叉树
1. 定义二叉树节点结构体
首先，需要定义二叉树节点的结构体，它包含节点的值、左子节点指针和右子节点指针:
using namespace std; // 二叉树节点结构体定义 struct TreeNode { int val; TreeNode* left; TreeNode* left() const { return left; } void setLeft(TreeNode* node) { left = node; } TreeNode* right; TreeNode* right() const { return right; } void setRight(TreeNode* node) { right = node; } TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
2. 实现构建二叉树的函数
下面的函数
buildTree用于根据给定的括号表示串来构建二叉树，思路是通过解析字符串，递归地构建各个节点及其子树
class Solution { public: TreeNode* buildTree(string s) { if (s.empty()) return nullptr; int idx = 1; // 跳过最外层括号，从下一个字符开始 int val = 0; bool isNegative = false; // 解析出根节点的值 if (s[idx] == '-') { isNegative = true; idx++; } while (idx < s.size() && isdigit(s[idx])) { val = val * 10 + (s[idx] - '0'); idx++; } if (isNegative) val = -val; TreeNode* root = new TreeNode(val); int count = 0; // 用于记录括号的匹配情况 string leftSubtree = ""; // 寻找左子树对应的括号表示部分 for (int i = idx; i < s.size(); ++i) { if (s[i] == '(') count++; else if (s[i] == ')') count--; leftSubtree += s[i]; if (count == 0 && leftSubtree!= "") break; } root->left = buildTree(leftSubtree); string rightSubtree = ""; // 提取右子树对应的括号表示部分 for (int i = leftSubtree.size() + idx + 1; i < s.size() - 1; ++i) { rightSubtree += s[i]; } root->right = buildTree(rightSubtree); return root; } };
上述代码中：
- 首先判断输入的字符串是否为空，如果为空则直接返回
nullptr，表示构建空二叉树。- 接着解析出根节点的值：跳过最外层括号后，处理可能存在的负号，然后按顺序读取数字字符并转换为对应的整数值，创建根节点对象。
- 之后通过遍历字符串来确定左子树对应的括号表示部分：使用一个计数器
count来跟踪括号的匹配情况（遇到(就加 1，遇到)就减 1），当count再次变为 0 时，表示找到了左子树对应的完整括号表示，然后递归调用buildTree函数来构建左子树，并将其赋值给根节点的左子节点指针。- 最后，类似地提取右子树对应的括号表示部分，并递归构建右子树，将其赋值给根节点的右子节点指针，最终返回构建好的二叉树的根节点。
3. 使用示例
以下是一个简单的使用示例，展示如何调用
buildTree函数来构建二叉树并进行简单验证
int main() { Solution solution; string s = "(1(2)(3))"; TreeNode* root = solution.buildTree(s); // 可以在这里添加代码进一步验证构建好的二叉树，比如简单打印节点值等 cout << "根节点的值为: " << root->val << endl; return 0; }
在实际应用中，你可以根据具体需求进一步扩展功能，比如添加更多的错误处理逻辑，在构建过程中如果输入字符串不符合二叉树括号表示规范（如括号不匹配、节点值格式错误等）进行相应的报错提示；或者实现二叉树的遍历函数（如前序遍历、中序遍历、后序遍历等）来更全面地查看构建好的二叉树的结构情况等。
计算二叉树的结点个数、叶子结点个数、某结点的层次和二叉树的宽度
以下是使用 C++ 语言实现计算二叉树的节点个数、叶子节点个数、某节点的层次以及二叉
树的宽度的代码示例及详细解释。这里假设已经定义好了二叉树的节点结构体，如下所示：
// 二叉树节点结构体定义 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
1. 计算二叉树节点个数
可以通过递归的方式来计算二叉树的节点个数，思路是节点个数等于 1（根节点）加上左子树节点个数加上右子树节点个数。
// 计算二叉树节点个数的函数 int countNodes(TreeNode* root) { if (root == NULL) return 0; return 1 + countNodes(root->left) + countNodes(root->right); }
在上述函数中：
- 首先判断根节点是否为空，如果为空，说明二叉树为空树，节点个数为 0，直接返回 0。
- 否则，递归地计算左子树和右子树的节点个数，并加上 1（代表根节点）后返回，以此来得到整棵二叉树的节点个数。
2. 计算二叉树叶子节点个数
叶子节点是指没有子节点（左子节点和右子节点都为
NULL）的节点，同样可以使用递归方式来统计。
// 计算二叉树叶子节点个数的函数 int countLeafNodes(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return countLeafNodes(root->left) + countLeafNodes(root->right); }
在这个函数里：
- 先判断根节点是否为空，为空则返回 0，因为空树没有叶子节点。
- 接着判断根节点是否为叶子节点（即左、右子节点都为空），若是则返回 1。
- 如果根节点不是叶子节点，就递归地分别统计左子树和右子树中的叶子节点个数，然后相加返回，得到整棵树的叶子节点个数。
3. 计算某节点的层次
可以通过从根节点开始进行层次遍历（例如使用队列来辅助实现广度优先搜索）来确定某节点所在的层次，根节点层次为 1，每向下一层层次数加 1。
// 计算某节点在二叉树中的层次的函数 int getLevel(TreeNode* root, TreeNode* target) { if (root == NULL) return 0; std::queue<TreeNode*> q; q.push(root); int level = 1; while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { TreeNode* node = q.front(); q.pop(); if (node == target) return level; if (node->left!= NULL) q.push(node->left); if (node->right!= NULL) q.push(node->right); } level++; } return 0; // 没找到目标节点则返回0 }
在上述函数中：
- 首先判断根节点是否为空，如果为空则直接返回 0，因为不存在层次一说。
- 然后创建一个队列用于层次遍历，将根节点入队，并初始化层次数为 1。
- 在循环中，每次取出队列中当前层的所有节点（通过
size控制循环次数），检查是否为目标节点，如果是则返回当前层次数。对于当前层的每个节点，将其左、右子节点（如果存在）入队，以便后续遍历下一层，每处理完一层层次数加 1。- 如果遍历完整个树都没找到目标节点，则返回 0。
4. 计算二叉树的宽度
二叉树的宽度可以理解为各层节点数最多的那一层的节点个数，通过层次遍历并记录每层的节点个数来找到最大宽度。
// 计算二叉树宽度的函数 int getWidth(TreeNode* root) { if (root == NULL) return 0; std::queue<TreeNode*> q; q.push(root); int maxWidth = 0; while (!q.empty()) { int size = q.size(); maxWidth = std::max(maxWidth, size); for (int i = 0; i < size; i++) { TreeNode* node = q.front(); q.pop(); if (node->left!= NULL) q.push(node->left); if (node->right!= NULL) q.push(node->right); } } return maxWidth; }
在这个函数中：
- 同样先判断根节点是否为空，为空则返回 0，因为空树宽度为 0。
- 接着使用队列进行层次遍历，每次循环开始时记录当前层的节点个数
size，并更新最大宽度maxWidth（取当前最大宽度和当前层节点个数中的较大值）。- 然后将当前层的每个节点的左、右子节点（如果存在）入队，以便遍历下一层。
- 遍历完整个二叉树后，返回最大宽度值，即二叉树各层中节点数最多的那一层的节点个数。
以下是一个简单的使用示例，展示如何调用这些函数：
int main() { TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); std::cout << "节点个数: " << countNodes(root) << std::endl; std::cout << "叶子节点个数: " << countLeafNodes(root) << std::endl; TreeNode* target = root->left->right; // 以节点值为5的节点为例 std::cout << "节点5所在层次: " << getLevel(root, target) << std::endl; std::cout << "二叉树宽度: " << getWidth(root) << std::endl; return 0; }
测试说明
平台会对你编写的代码进行测试：
测试输入：
A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
K
预期输出：
输出二叉树b:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
二叉树b的结点个数:14
二叉树b的叶子结点个数:6
二叉树b中值为K结点的层次:5
二叉树b的宽度:4
开始你的任务吧，祝你成功！
通关代码
using namespace std; typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; } BTNode; void CreateBTree(BTNode *&b, char *str) { BTNode *St[Maxsize], *p; int top = -1, k, j = 0; char ch; b = NULL; ch = str[j]; while (ch != '\0') { switch (ch) { case '(': top++; St[top] = p; k = 1; break; case ')': top--; break; case ',': k = 2; break; default: p = new BTNode; p->data = ch; p->lchild = p->rchild = NULL; if (b == NULL) b = p; else { switch (k) { case 1: St[top]->lchild = p; break; case 2: St[top]->rchild = p; break; } } } j++; ch = str[j]; } } void DestroyBtree(BTNode *&b) { if (b != NULL) { DestroyBtree(b->lchild); DestroyBtree(b->rchild); delete b; } } BTNode *FindNode(BTNode *b, ElemType x) { BTNode *p; if (b == NULL) return NULL; else if (b->data == x) return b; else { p = FindNode(b->lchild, x); if (p != NULL) return p; else return FindNode(b->rchild, x); } } BTNode *LchildNode(BTNode *p) { return p ? p->lchild : NULL; } BTNode *RchildNode(BTNode *p) { return p ? p->rchild : NULL; } int BTHeight(BTNode *b) { if (b == NULL) return 0; int lchildh = BTHeight(b->lchild); int rchildh = BTHeight(b->rchild); return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1); } int CountNodes(BTNode *b) { if (b == NULL) return 0; return 1 + CountNodes(b->lchild) + CountNodes(b->rchild); } int CountLeafNodes(BTNode *b) { if (b == NULL) return 0; if (b->lchild == NULL && b->rchild == NULL) return 1; return CountLeafNodes(b->lchild) + CountLeafNodes(b->rchild); } int FindLevel(BTNode *b, ElemType x, int level) { if (b == NULL) return 0; if (b->data == x) return level; int leftLevel = FindLevel(b->lchild, x, level + 1); if (leftLevel) return leftLevel; return FindLevel(b->rchild, x, level + 1); } int TreeWidth(BTNode *root) { if (!root) return 0; int maxWidth = 0; queue<BTNode *> q; q.push(root); while (!q.empty()) { int count = q.size(); maxWidth = max(maxWidth, count); for (int i = 0; i < count; i++) { BTNode *node = q.front(); q.pop(); if (node->lchild) q.push(node->lchild); if (node->rchild) q.push(node->rchild); } } return maxWidth; } void DispBTree(BTNode *b) { if (b != NULL) { cout << b->data; if (b->lchild != NULL || b->rchild != NULL) { cout << "("; DispBTree(b->lchild); if (b->rchild != NULL) cout << ","; DispBTree(b->rchild); cout << ")"; } } } int main() { BTNode *b; char str[Maxsize]; char c; cin.getline(str, Maxsize); cin >> c; CreateBTree(b, str);
测试结果
