数据结构 假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。
时间: 2024-02-27 22:57:47 浏览: 18
好的,以下是求二叉树结点个数的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` 是求二叉树结点个数的函数,采用递归的思想,不断累加左右子树结点个数,最后加上根节点,即为整个二叉树的结点个数。
希望这个代码能够帮助您解决问题,如果您还有其他问题,请随时提出。
相关问题
数据结构 假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。 整体代码
下面是基于二叉链表存储结构的二叉树结点个数求解算法的代码实现:
```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. 如果二叉树非空,则递归计算左子树和右子树的结点个数,加上根节点,即可得到整个二叉树的结点个数。
实现代码如下(假设二叉树的结构体为`struct TreeNode`,其中`left`和`right`分别指向左右子树):
```
int countNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int left_count = countNodes(root->left);
int right_count = countNodes(root->right);
return left_count + right_count + 1;
}
```
以上算法的时间复杂度为$O(n)$,其中$n$为二叉树的结点个数。