假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数
时间: 2024-03-01 14:04:29 浏览: 45
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
好的,针对你的问题,我可以提供以下算法:
1. 先判断二叉树是否为空,如果为空则返回0。
2. 如果二叉树不为空,则递归计算左子树的结点个数,递归计算右子树的结点个数,最后加上根节点,即可得到整棵树的结点个数。
以下是具体的实现代码:
```
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
} else {
int leftCount = countNodes(root->left);
int rightCount = countNodes(root->right);
return leftCount + rightCount + 1;
}
}
```
其中,TreeNode 是二叉树结点的数据结构,包含左右子树指针和结点值等信息。以上算法的时间复杂度为 O(n),其中 n 是二叉树的结点个数。
阅读全文