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