C++ 编程实现二叉树的生成及遍历算法,要求: (1)编写创建二叉链表形式存储的二叉树程序并输出。 (2)编写递归实现二叉树的先序、中序、后序遍历、统计所有 叶子结点的个数的算法。 (3)编写主函数测试以上二叉树的创建和遍历以及输出统计所有叶子结点个数等函数。
时间: 2024-12-23 22:15:08 浏览: 11
在C++中,我们可以使用结构体和指针来实现二叉树。首先,我们定义一个表示二叉树节点的结构:
```cpp
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
接下来,我们可以分别创建二叉树的节点并构建整个树结构,这里以一个简单的例子如斐波那契树为例:
```cpp
TreeNode* createFibonacciTree(int n) {
if (n <= 0) return nullptr;
TreeNode* root = new TreeNode(n);
if (n == 1 || n == 2) return root;
TreeNode* temp = createFibonacciTree(n - 1);
root->left = temp;
temp = createFibonacciTree(n - 2);
root->right = temp;
return root;
}
```
为了遍历这个二叉树,我们需要实现递归的先序、中序和后序遍历:
1. 先序遍历(根-左-右):
```cpp
void preorderTraversal(TreeNode* node) {
if (node != nullptr) {
std::cout << node->val << " ";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
}
```
2. 中序遍历(左-根-右):
```cpp
void inorderTraversal(TreeNode* node) {
if (node != nullptr) {
inorderTraversal(node->left);
std::cout << node->val << " ";
inorderTraversal(node->right);
}
}
```
3. 后序遍历(左-右-根):
```cpp
void postorderTraversal(TreeNode* node) {
if (node != nullptr) {
postorderTraversal(node->left);
postorderTraversal(node->right);
std::cout << node->val << " ";
}
}
```
最后,计算并输出叶子节点的数量:
```cpp
int countLeaves(TreeNode* node) {
if (node == nullptr) return 0;
return (node->left == nullptr && node->right == nullptr) ? 1 : countLeaves(node->left) + countLeaves(node->right);
}
```
主函数测试示例:
```cpp
int main() {
int n = 5; // 示例输入,你可以更改此值构建不同大小的树
TreeNode* root = createFibonacciTree(n);
std::cout << "Preorder Traversal: ";
preorderTraversal(root);
std::cout << "\nInorder Traversal: ";
inorderTraversal(root);
std::cout << "\nPostorder Traversal: ";
postorderTraversal(root);
std::cout << "\nNumber of Leaves: " << countLeaves(root);
delete root; // 销毁节点
return 0;
}
```
记得在实际项目中添加错误处理和内存管理,例如释放动态分配的内存。以上代码展示了基本的二叉树操作,你可以根据需要修改以适应其他特定需求。
阅读全文