用c++创建一棵二叉树,计算二叉树结点个数、叶子结点个数、二叉树深度
时间: 2024-11-21 14:21:25 浏览: 8
在C++中创建一棵二叉树并计算节点个数、叶子结点个数以及二叉树的深度通常需要使用结构体来表示二叉树节点,并实现递归算法。这里是一个简单的示例:
首先,我们定义一个二叉树节点的结构体(Node):
```cpp
struct TreeNode {
int val; // 节点值
TreeNode* left; // 左子节点指针
TreeNode* right; // 右子节点指针
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数
};
```
接下来,我们可以创建一个函数来添加节点,计算节点总数、叶子节点数以及树的深度:
```cpp
size_t countNodes(TreeNode* root) {
if (root == nullptr)
return 0;
else
return 1 + countNodes(root->left) + countNodes(root->right);
}
int leafCount(TreeNode* root) {
if (root == nullptr)
return 0;
else if (root->left == nullptr && root->right == nullptr)
return 1;
else
return leafCount(root->left) + leafCount(root->right);
}
int treeDepth(TreeNode* root) {
if (root == nullptr)
return 0;
else
return 1 + std::max(treeDepth(root->left), treeDepth(root->right));
}
```
在这里,`countNodes`函数通过递归遍历所有节点;`leafCount`函数检查当前节点是否有左右子节点为空,如果有则是叶子节点;而`treeDepth`函数同样采用递归,计算左子树和右子树的最大深度。
你可以按照这个模板,实例化一个具体的二叉树结构,并调用这三个函数来进行计算。如果需要实际操作,记得为每个节点分配内存并设置相应的指针链接。
阅读全文