已知以二叉链表作存储结构,使用C++语言创建二叉树,并实现二叉树的树的高度以及统计二叉树叶节点数量的功能
时间: 2024-10-17 15:01:43 浏览: 33
在C++中,我们可以使用结构体表示二叉树的节点,每个节点包含一个值、指向左孩子的指针和指向右孩子的指针。创建二叉树可以递归地完成,通过插入新节点的方式来构建。以下是基本的步骤:
```cpp
// 定义二叉树节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 插入节点到二叉树
TreeNode* insertIntoTree(TreeNode*& root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
if (val < root->val) {
root->left = insertIntoTree(root->left, val);
} else {
root->right = insertIntoTree(root->right, val);
}
return root;
}
// 计算二叉树高度
int height(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return std::max(leftHeight, rightHeight) + 1;
}
// 统计二叉树叶子节点数量
int countLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) { // 如果节点无左右孩子,它是叶子节点
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
```
阅读全文