如何用C++实现二叉树的数据结构,包括计算叶子节点的数量、每个节点的深度以及总节点数?
时间: 2024-11-15 19:29:45 浏览: 30
在C++中,我们可以使用结构体或者类来实现二叉树的数据结构。这里我们首先定义一个简单的二叉树节点类,包含左孩子指针、右孩子指针和值:
```cpp
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
// 构造函数和默认构造函数
TreeNode(int val = 0) : val(val), left(nullptr), right(nullptr) {}
};
```
接下来,我们可以创建一个二叉树类,包含计算叶子节点、节点深度和总数的方法:
```cpp
class BinaryTree {
private:
TreeNode* root;
public:
BinaryTree(TreeNode* root = nullptr) : root(root) {}
// 计算叶子节点数量
int countLeaves() const {
return countLeavesHelper(root);
}
private:
int countLeavesHelper(TreeNode* node) const {
if (!node) return 0; // 空节点无叶子
if (!node->left && !node->right) return 1; // 非空叶节点计数
else return countLeavesHelper(node->left) + countLeavesHelper(node->right);
}
// 计算节点深度 (假设根节点深度为1)
int depth(TreeNode* node) const {
if (!node) return 0;
return 1 + std::max(depth(node->left), depth(node->right));
}
// 总节点数
int totalNodes() const {
return totalNodesHelper(root);
}
private:
int totalNodesHelper(TreeNode* node) const {
if (!node) return 0;
return 1 + totalNodesHelper(node->left) + totalNodesHelper(node->right);
}
};
```
现在你可以创建一个`BinaryTree`实例并调用上述方法来获取你需要的信息。例如:
```cpp
int main() {
// 创建二叉树...
BinaryTree tree;
int leafCount = tree.countLeaves();
int maxDepth = tree.depth(tree.root);
int totalNodes = tree.totalNodes();
std::cout << "Leaf nodes: " << leafCount << std::endl;
std::cout << "Max depth: " << maxDepth << std::endl;
std::cout << "Total nodes: " << totalNodes << std::endl;
return 0;
}
```
阅读全文