假设二叉树采用链接表示,请用C++设计一个算法按从左到右输出一棵二叉树中所有叶子结点值
时间: 2024-11-15 21:25:11 浏览: 37
在C++中,我们可以通过递归的方式来实现这个功能。首先,我们需要定义一个二叉树节点的数据结构,包含值、左右指针。下面是一个简单的`Node`类和遍历函数`printLeaves`:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点
struct Node {
int val;
Node* left;
Node* right;
Node(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 递归函数,用于打印左至右的所有叶子节点
void printLeaves(Node* root, vector<int>& leaves) {
if (!root) return; // 结束条件:空节点
// 如果当前节点是叶子节点,将其值添加到结果列表中
if (!root->left && !root->right) {
leaves.push_back(root->val);
}
// 递归遍历左子树和右子树
printLeaves(root->left, leaves);
printLeaves(root->right, leaves);
}
// 主函数示例
int main() {
Node* root = new Node(1); // 示例二叉树
// ... 构建二叉树 ...
vector<int> leaves;
printLeaves(root, leaves);
// 输出所有叶子节点的值
for (const auto& leaf : leaves) {
cout << leaf << " ";
}
cout << endl;
delete root; // 清理内存
return 0;
}
```
在这个程序中,`printLeaves`函数会持续检查每个节点是否为叶子节点,并将它们的值存入`leaves`向量中。主函数则创建一个二叉树实例并调用这个函数,最后打印出所有的叶子节点值。
阅读全文