用C++使用二叉链表的存储结构,构造一棵二叉树,实现两个算法(利用递归调用): (1) 求解二叉树的深度; (2) 求解二叉树叶子结点数;
时间: 2024-11-20 12:27:16 浏览: 30
在C++中,我们可以使用二叉链表来构建二叉树,每个节点包含一个值、指向左子节点的指针和指向右子节点的指针。为了实现这两个算法,首先需要定义一个二叉树节点的数据结构:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
接下来我们分别实现求解二叉树深度和叶子节点数的递归函数:
1. **求解二叉树深度** (Tree Depth)
```cpp
int maxDepth(TreeNode* root) {
if (!root) return 0; // 空树深度为0
else {
int leftDepth = maxDepth(root->left); // 左子树深度
int rightDepth = maxDepth(root->right); // 右子树深度
return std::max(leftDepth, rightDepth) + 1; // 返回较大深度加1(根节点也算一层)
}
}
```
2. **求解二叉树叶子结点数** (Number of Leaf Nodes)
```cpp
int countLeafNodes(TreeNode* root) {
if (!root) return 0; // 空树叶子节点数为0
else if (!root->left && !root->right) // 如果左右都没有子节点,则是叶子节点
return 1;
else
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
```
以上就是在C++中使用二叉链表存储结构实现求解二叉树深度和叶子结点数的示例。
阅读全文