计算二叉树的高度、总节点个数和叶子节点个数
时间: 2023-04-24 19:01:54 浏览: 353
计算二叉树的高度,可以使用递归的方法,从根节点开始,分别计算左子树和右子树的高度,取较大值加1即可。总节点个数也可以使用递归的方法,从根节点开始,分别计算左子树和右子树的节点个数,加上根节点即可。叶子节点个数可以使用递归的方法,从根节点开始,如果当前节点为叶子节点,则计数器加1,否则分别计算左子树和右子树的叶子节点个数,相加即可。
相关问题
计算二叉树的高度、总节点个数和叶子节点个数代码
好的,下面是计算二叉树高度、总节点个数和叶子节点个数的 Python 代码:
```
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def get_height(root):
if not root:
return 0
return max(get_height(root.left), get_height(root.right)) + 1
def get_node_count(root):
if not root:
return 0
return 1 + get_node_count(root.left) + get_node_count(root.right)
def get_leaf_count(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return get_leaf_count(root.left) + get_leaf_count(root.right)
# 测试代码
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(get_height(root)) # 输出 3
print(get_node_count(root)) # 输出 7
print(get_leaf_count(root)) # 输出 4
```
这里我们定义了一个 `TreeNode` 类来表示二叉树的节点,然后分别实现了 `get_height`、`get_node_count` 和 `get_leaf_count` 函数来计算二叉树的高度、总节点个数和叶子节点个数。测试代码中创建了一个简单的二叉树,并输出了计算结果。
二叉树通过节点个数计算叶子节点公式
对于一个二叉树,可以通过节点个数来计算叶子节点的数量。假设二叉树中共有 `n` 个节点,其中叶子节点的数量记为 `m`。
根据二叉树的性质,每个节点都有最多两个子节点(左子节点和右子节点),因此可以得出以下关系:
- 如果二叉树只有一个节点(即 `n=1`),那么它是一个叶子节点,即 `m=1`。
- 如果二叉树有多个节点(即 `n>1`),那么除了根节点以外的每个节点都会增加两个子节点。因此,可以得出以下关系:`m = n / 2`。
请注意,这个公式假设二叉树是完全二叉树,即除了最后一层外,每一层都是满的。对于非完全二叉树,这个公式可能不适用。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)