数据结构 假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。 整体代码
时间: 2024-03-01 14:04:34 浏览: 44
下面是基于二叉链表存储结构的二叉树结点个数求解算法的代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_nodes(root: TreeNode) -> int:
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
```
上述代码定义了一个二叉树结点类 `TreeNode`,包含结点值和左右子结点的指针。然后定义了一个递归函数 `count_nodes`,用于计算二叉树的结点个数。如果当前结点为空,返回 0;否则返回 1(当前结点)加上左子树结点个数和右子树结点个数之和。
相关问题
数据结构 假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。
可以使用递归的方法求解二叉树的结点个数,具体算法如下:
1. 如果二叉树为空,结点个数为0,返回0。
2. 如果二叉树不为空,结点个数为:左子树的结点个数 + 右子树的结点个数 + 1(根节点)。
3. 分别递归计算左子树和右子树的结点个数,然后将它们加起来,再加上根节点,即为二叉树的结点个数。
下面是算法的实现代码(假设二叉树的节点结构体为Node,包含left、right两个指针,分别指向左子树和右子树):
```python
int countNodes(Node* root) {
if (root == NULL) {
return 0;
}
int leftCount = countNodes(root->left);
int rightCount = countNodes(root->right);
return leftCount + rightCount + 1;
}
```
时间复杂度为O(n),其中n为二叉树的结点个数。
假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。 完整代码
好的,以下是求二叉树结点个数的Python代码实现:
```python
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_nodes(root: TreeNode) -> int:
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
```
其中 `TreeNode` 是二叉树结点的类,包含了结点的值以及左右子节点;`count_nodes` 是求二叉树结点个数的函数,采用递归的思想,不断累加左右子树结点个数,最后加上根节点,即为整个二叉树的结点个数。
希望这个代码能够帮助您解决问题,如果您还有其他问题,请随时提出。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.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)