用c++编写出以先序遍历的顺序建立二叉树,并输出度为2 的结点数。
时间: 2024-02-23 20:59:28 浏览: 59
好的,根据您的要求,我来为您解答。
首先,先给出二叉树的结构体定义:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
然后,给出以先序遍历的顺序建立二叉树的函数:
```c++
TreeNode* buildTree(vector<int>& preorder) {
if (preorder.empty()) {
return nullptr;
}
int val = preorder[0];
TreeNode* root = new TreeNode(val);
vector<int> left_preorder, right_preorder;
for (int i = 1; i < preorder.size(); i++) {
if (preorder[i] < val) {
left_preorder.push_back(preorder[i]);
} else {
right_preorder.push_back(preorder[i]);
}
}
root->left = buildTree(left_preorder);
root->right = buildTree(right_preorder);
return root;
}
```
最后,给出统计度为2的节点数的函数:
```c++
int countDegree2(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int count = 0;
if (root->left != nullptr && root->right != nullptr) {
count++;
}
count += countDegree2(root->left);
count += countDegree2(root->right);
return count;
}
```
完整代码如下:
```c++
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& preorder) {
if (preorder.empty()) {
return nullptr;
}
int val = preorder[0];
TreeNode* root = new TreeNode(val);
vector<int> left_preorder, right_preorder;
for (int i = 1; i < preorder.size(); i++) {
if (preorder[i] < val) {
left_preorder.push_back(preorder[i]);
} else {
right_preorder.push_back(preorder[i]);
}
}
root->left = buildTree(left_preorder);
root->right = buildTree(right_preorder);
return root;
}
int countDegree2(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int count = 0;
if (root->left != nullptr && root->right != nullptr) {
count++;
}
count += countDegree2(root->left);
count += countDegree2(root->right);
return count;
}
int main() {
vector<int> preorder = {5, 3, 2, 4, 7, 6, 8};
TreeNode* root = buildTree(preorder);
int count = countDegree2(root);
cout << "度为2的结点数为:" << count << endl;
return 0;
}
```
希望能够帮到您!
阅读全文