先按先序遍历建立一棵二叉树,下面图中的树只是例子。再编写交换左右子树和统计叶子结点个数的算法程序。
时间: 2024-03-11 16:47:16 浏览: 16
好的,我来编写这个程序。
首先,先按照先序遍历的顺序建立二叉树,可以使用递归的方式实现。具体过程如下:
1. 如果当前遍历到的字符是空格,则返回 NULL。
2. 创建一个新节点,并将其值设置为当前遍历到的字符。
3. 递归调用函数来构建左子树,并将其结果设置为新节点的左子树。
4. 递归调用函数来构建右子树,并将其结果设置为新节点的右子树。
5. 返回新节点。
接下来,编写交换左右子树的函数。同样可以使用递归的方式实现。具体过程如下:
1. 如果当前节点为空,则直接返回。
2. 递归调用该函数来交换当前节点的左子树和右子树。
3. 交换当前节点的左子树和右子树。
最后,编写统计叶子结点个数的函数。同样可以使用递归的方式实现。具体过程如下:
1. 如果当前节点为空,则返回 0。
2. 如果当前节点没有左子树和右子树,即为叶子结点,则返回 1。
3. 递归调用该函数来统计当前节点的左子树中叶子结点的个数,并将其结果赋值给变量 leftCount。
4. 递归调用该函数来统计当前节点的右子树中叶子结点的个数,并将其结果赋值给变量 rightCount。
5. 返回 leftCount + rightCount,即为当前节点下叶子结点的个数。
下面是示例代码(使用 C++ 语言实现):
```cpp
#include <iostream>
using namespace std;
// 定义二叉树结点
struct Node {
char data;
Node* left;
Node* right;
};
// 先序遍历建立二叉树
Node* CreateTree() {
char c;
cin >> c;
if (c == ' ') {
return NULL;
}
Node* root = new Node();
root->data = c;
root->left = CreateTree();
root->right = CreateTree();
return root;
}
// 交换左右子树
void SwapTree(Node* root) {
if (root == NULL) {
return;
}
SwapTree(root->left);
SwapTree(root->right);
Node* tmp = root->left;
root->left = root->right;
root->right = tmp;
}
// 统计叶子结点个数
int CountLeaf(Node* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
int leftCount = CountLeaf(root->left);
int rightCount = CountLeaf(root->right);
return leftCount + rightCount;
}
int main() {
Node* root = CreateTree();
cout << "叶子结点个数:" << CountLeaf(root) << endl;
SwapTree(root);
cout << "交换左右子树后的先序遍历结果:";
// 先序遍历交换左右子树后的二叉树
// 此处仅为展示结果,并不是题目要求的部分
cout << root->data << " ";
if (root->left != NULL) {
cout << root->left->data << " ";
}
if (root->right != NULL) {
cout << root->right->data << " ";
}
cout << endl;
return 0;
}
```
注意,上述代码中只展示了交换左右子树的结果,而不是按要求输出完整的交换后的二叉树,读者可以自行完成。