二叉树总结点数算法

二叉树是计算机科学中的一种常见数据结构。其中，节点是树形结构中最基本的单元。计算二叉树中的总结点数是一道经典问题，在这里，我们将从多个角度进行分析。

定义

首先，让我们明确一下什么是二叉树。在计算机科学中，二叉树是一种关键字为二元组的树形结构。具体来说，该结构包含节点和边两个基本元素。节点可以包含一个关键字，同时，每个节点最多有两个子节点。左子节点的关键字值小于当前节点，右子节点的关键字值大于当前节点。

递归算法

一种常见的解决总节点数的方法是采用递归算法。该算法非常简单，适用于所有类型的二叉树（包括非完全二叉树）。首先，我们需要遍历树的每一个节点。然后，我们统计树中所有节点的总数，包括根节点、左子树中的节点数量和右子树中的节点数量。总的节点数量即为根节点数量加上两个子树节点数量之和。递归代码如下：

```

// 返回二叉树的节点总数

int countNodes(TreeNode* root) {

if (root == nullptr) {

return 0;

}

return 1 + countNodes(root->left) + countNodes(root->right);

}

```

时间复杂度 O(nlogn)

该递归算法的时间复杂度为O(nlogn)。其原因在于，算法需要递归遍历整棵树，并计算出每个子树的节点数。由于树是一种递归结构，计算每个子树所需的时间复杂度与树的高度成正比。因此，总时间复杂度为树的高度乘以遍历每个节点所需的时间复杂度，即为O(nlogn)。

完全二叉树的算法

下面，我们来看看如何计算完全二叉树的节点数量。完全二叉树是指深度为k的二叉树，其中除第k层外的每一层都有最大节点数。同时，第k层上的所有节点都集中在该层最左侧。

我们可以通过遍历子树的方式计算节点数量。对于左子树，如果其高度比右子树高，则说明右子树为满二叉树，可以通过公式计算出右子树节点数量。然后，我们可以继续遍历左子树，直到遍历到最后一层，即为叶子节点所在层。此时，若左子树高度等于右子树，则说明左子树为满二叉树，可以通过公式计算出左子树节点数量。反之，右子树为满二叉树，我们继续遍历右子树，直到遍历到叶子节点所在层。

完全二叉树的节点数可以通过如下代码计算：

```

// 返回完全二叉树的节点总数

int countNodes(TreeNode* root) {

if (root == nullptr) {

return 0;

}

int leftHeight = getHeight(root->left);

int rightHeight = getHeight(root->right);

if (leftHeight == rightHeight) {

return (1 << leftHeight) + countNodes(root->right);

} else {

return (1 << rightHeight) + countNodes(root->left);

}

}

// 返回一棵二叉树的高度

int getHeight(TreeNode* root) {

int height = 0;

while (root != nullptr) {

root = root->left;

height++;

}

return height;

}

```

时间复杂度 O(logn * logn)

该算法的时间复杂度为O(logn * logn)，其中n为二叉树的节点数量。其过程在递归调用中取决于获取树高、计算子树节点数量以及寻找叶子节点所在层数等操作。