在Dev-C++中先按先序遍历建立一棵二叉树,再编写交换左右子树和统计叶子结点个数的算法程序
时间: 2024-03-11 14:48:01 浏览: 80
由c++实现的二叉树的建立与遍历
4星 · 用户满意度95%
好的,以下是代码实现:
```c++
#include <iostream>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历建立二叉树
void createTree(TreeNode*& root) {
int val;
cin >> val;
if (val == -1) {
root = NULL;
} else {
root = new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
}
// 交换左右子树
void swapTree(TreeNode* root) {
if (root == NULL) {
return;
}
swap(root->left, root->right);
swapTree(root->left);
swapTree(root->right);
}
// 统计叶子结点个数
int countLeaf(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaf(root->left) + countLeaf(root->right);
}
int main() {
TreeNode* root;
cout << "请输入先序遍历序列(-1表示空结点):" << endl;
createTree(root);
cout << "交换左右子树后的先序遍历序列为:" << endl;
swapTree(root);
// 输出交换后的先序遍历序列
// 省略
cout << "叶子结点个数为:" << countLeaf(root) << endl;
return 0;
}
```
注意事项:
1. 代码中使用了指针的引用,方便在函数中修改指针的值;
2. 输入先序遍历序列时,-1 表示空结点;
3. 输出交换后的先序遍历序列可以在 `swapTree` 函数中实现,也可以在 `main` 函数中实现,这里省略了。
阅读全文