【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 100
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);
测试结果
