【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
目录😋
本关任务
相关知识
根据二叉树的括号表示串，创建二叉树
1. 定义二叉树节点结构体
2. 实现构建二叉树的函数
3. 使用示例
计算二叉树的结点个数、叶子结点个数、某结点的层次和二叉树的宽度
1. 计算二叉树节点个数
2. 计算二叉树叶子节点个数
3. 计算某节点的层次
4. 计算二叉树的宽度
测试说明
通关代码
测试结果
本关任务
编写一个程序验证二叉树的性质。
相关知识
为了完成本关任务，你需要掌握：
- 根据二叉树的括号表示串，创建二叉树b。
- 计算二叉树的结点个数、叶子结点个数、某结点的层次和二叉树的宽度。
根据二叉树的括号表示串，创建二叉树
1. 定义二叉树节点结构体
首先，需要定义二叉树节点的结构体，它包含节点的值、左子节点指针和右子节点指针:
#include <iostream> #include <string>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。
#include <queue>// 计算某节点在二叉树中的层次的函数 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
开始你的任务吧，祝你成功！
通关代码
#include <iostream>
#include <queue>
#include <string>#define Maxsize 100using 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;elsereturn 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);
测试结果
