二叉树采用链接存储结构，试设计一个算法计算一棵给定二叉树的所有结点数。

对于给定的二叉树，我们可以使用递归的方式来计算所有节点的数量。这里是一个基本的算法步骤：

1. 定义一个函数`countNodes(node)`，它接受一个二叉树节点作为参数，返回该节点及其所有后代节点的总数。

2. 如果节点 `node` 为空，则说明这是一个叶子节点，其节点数为 0，返回 0。

3. 否则，如果节点不为空：
a. 计算左子树的节点数，即 `leftCount = countNodes(node.left)`
b. 计算右子树的节点数，即 `rightCount = countNodes(node.right)`
c. 返回当前节点加上左右子树的节点数，即 `return 1 + leftCount + rightCount`

4. 最终，根节点 `root` 的所有节点数就是 `countNodes(root)`。

下面是这个算法的伪代码示例：

function countNodes(node):
    if node is null:
        return 0
    else:
        leftCount = countNodes(node.left)
        rightCount = countNodes(node.right)
        return 1 + leftCount + rightCount

相关问题

设二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树中叶子结点的数目。

### 回答1：
算法如下：

1. 如果二叉树为空，则叶子结点数目为0，返回0。

2. 如果二叉树非空，则分别计算左子树和右子树中叶子结点的数目。

3. 如果当前结点的左子树和右子树都为空，则当前结点为叶子结点，叶子结点数目加1。

4. 最后返回左子树中叶子结点数目加上右子树中叶子结点数目加上当前结点是否为叶子结点的结果。

代码如下：

int countLeafNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftCount = countLeafNodes(root->left);
    int rightCount = countLeafNodes(root->right);
    if (root->left == NULL && root->right == NULL) {
        return leftCount + rightCount + 1;
    } else {
        return leftCount + rightCount;
    }
}

### 回答2：
二叉树是一种重要的数据结构，在计算机科学中具有广泛的应用。叶子结点是指没有子节点的节点。计算一棵二叉树中叶子结点的数目是一个常见的问题。本文将介绍如何设计一个算法计算一棵给定二叉树中叶子结点的数目。

首先，我们需要了解二叉树的链式存储结构。在链式存储结构中，每个节点包含两个指针，一个指向左子节点，另一个指向右子节点。如果一个节点没有子节点，那么它就是叶子节点。

算法的实现过程如下：

1.如果二叉树为空，则返回0。

2.如果当前节点没有子节点，则返回1。

3.如果当前节点有左子节点和右子节点，则计算左子树和右子树中叶子结点的数目，并将它们相加。

4.返回计算结果。

算法分为递归版和非递归版，下面分别简要介绍。

递归版：

int countLeaves(TreeNode *root) {
    if (root == nullptr)
        return 0;
    if (root->left == nullptr && root->right == nullptr)
        return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

非递归版：

int countLeaves(TreeNode *root) {
    if (root == nullptr)
        return 0;
    int count = 0;
    stack<TreeNode *> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode *node = s.top();
        s.pop();
        if (node->left == nullptr && node->right == nullptr)
            count++;
        if (node->left != nullptr)
            s.push(node->left);
        if (node->right != nullptr)
            s.push(node->right);
    }
    return count;
}

非递归版的算法采用了栈来保存遍历过的节点，因此不需要递归调用，效率更高。

综上所述，计算一棵给定二叉树中叶子结点的数目是一道比较简单的算法题。可以采用递归或者非递归方式来实现，在实际开发中应该根据具体情况选择合适的算法。

### 回答3：
二叉树是一种常见的数据结构，在树的节点中，有两个指针分别指向该节点的左子树和右子树。在二叉树的节点中，有三种类型的节点：根节点、中间节点和叶子节点。叶子节点指的是没有子节点的节点，也就是说它们是二叉树的最底层节点。

给定一个二叉树，我们要计算二叉树中叶子节点的数量。首先我们需要遍历整个二叉树。采用先序遍历、中序遍历或后序遍历方法都可以，因为对于每个节点，我们都只需要知道它是否是叶子节点。

如果该节点的左子树和右子树都为空，那么该节点就是叶子节点，我们将叶子节点数量加1。如果左子树不为空，就继续遍历左子树。如果右子树不为空，就继续遍历右子树。当遍历完整个二叉树时，叶子节点的数量就是累加器中的数值。

我们可以采用递归来实现以上算法，递归函数的参数为当前节点的指针及叶子节点数量的累加器。递归函数流程如下：

1. 如果当前节点为空，直接返回
2. 如果当前节点的左子树和右子树都为空，说明该节点是叶子节点，将叶子节点数量加1
3. 如果当前节点的左子树不为空，递归遍历左子树
4. 如果当前节点的右子树不为空，递归遍历右子树
5. 返回叶子节点数量

代码实现如下：

int count_leaf_node(node* p, int& count) {
  if (!p) return 0;  // 如果当前节点为空，直接返回
  if (!p->left && !p->right) count++;  // 如果当前节点是叶子节点，将叶子节点数量加1
  count_leaf_node(p->left, count);  // 递归遍历左子树
  count_leaf_node(p->right, count);  // 递归遍历右子树
  return count;  // 返回叶子节点数量
}

调用该函数时，第一个参数为二叉树的根节点，第二个参数为叶子节点数量的累加器：

int count = 0;
count_leaf_node(root, count);

以上算法的时间复杂度是O(n)，其中n是二叉树中节点的数量。空间复杂度是O(h)，其中h是二叉树的高度，因为递归的深度不会超过二叉树的高度。

假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有单分支节点个数。

算法思路：

1. 从根节点开始递归遍历二叉树；
2. 对于每个节点，判断它是否为单分支节点；
3. 如果是单分支节点，则计数器加一；
4. 遍历完整棵二叉树后，返回计数器的值。

具体实现如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_single_branch_nodes(root):
    """
    计算二叉树的所有单分支节点个数
    """
    if not root:
        return 0
    if not root.left and not root.right:
        return 0
    left_single = count_single_branch_nodes(root.left)
    right_single = count_single_branch_nodes(root.right)
    if (root.left and not root.right) or (not root.left and root.right):
        return 1 + left_single + right_single
    return left_single + right_single

其中，`TreeNode` 是二叉树节点的定义，包含值、左右子节点。`count_single_branch_nodes` 函数即为计算单分支节点个数的算法实现，其中：

- 如果当前节点为空，则返回 0；
- 如果当前节点为叶子节点，则返回 0；
- 否则，分别递归计算左右子树中的单分支节点个数；
- 如果当前节点只有左子树或只有右子树，则当前节点为单分支节点，计数器加一，并将左右子树中的单分支节点个数加起来返回；
- 否则，返回左右子树中的单分支节点个数之和。