用c++实现以下功能 输入格式:第一行一串字符 , 这串字符表示扩展二叉树的前序序列,其中空结点用#表示 • 输出格式: 一个整数代表二叉树的仅有一个孩子的节点的个数。
时间: 2024-02-27 17:54:39 浏览: 28
以下是用 C++ 实现输入扩展二叉树的前序序列,并计算二叉树的仅有一个孩子的节点个数的代码:
```c++
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
int countSingleChildNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
int count = 0;
if (root->left == NULL && root->right != NULL) {
count = 1 + countSingleChildNodes(root->right);
} else if (root->left != NULL && root->right == NULL) {
count = 1 + countSingleChildNodes(root->left);
} else {
count = countSingleChildNodes(root->left) + countSingleChildNodes(root->right);
}
return count;
}
TreeNode* buildTree(string s) {
if (s.empty()) {
return NULL;
}
stack<TreeNode*> st;
TreeNode* root = new TreeNode(s[0]);
st.push(root);
for (int i = 1; i < s.size(); i += 2) {
TreeNode* node = NULL;
if (s[i] != '#') {
node = new TreeNode(s[i]);
}
if (s[i-1] == '(') {
st.top()->left = node;
} else {
st.top()->right = node;
st.pop();
}
if (node != NULL) {
st.push(node);
}
}
return root;
}
int main() {
string s;
cin >> s;
TreeNode* root = buildTree(s);
int count = countSingleChildNodes(root);
cout << count << endl;
return 0;
}
```
代码中的 `countSingleChildNodes` 函数用于计算二叉树的仅有一个孩子的节点个数。函数中使用递归的方式遍历二叉树,对于每个节点,分别判断其左右子树是否为空。如果左子树为空且右子树非空,或者右子树为空且左子树非空,说明该节点有且仅有一个孩子,计数器加 1,并继续递归遍历其孩子节点。如果左右子树均非空,则继续递归遍历其孩子节点。
另外,代码中的 `buildTree` 函数用于根据输入的扩展二叉树前序序列构建二叉树,并返回根节点。函数中使用栈来辅助构建二叉树。从前往后遍历输入字符串,将左括号压入栈中,如果当前字符不是空节点,则创建一个节点,并根据栈顶元素的左右子树情况,将该节点插入到二叉树中。如果当前字符是右括号,则弹出栈顶元素。最后返回根节点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)