假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数

好的，针对你的问题，我给出以下算法来求二叉树的结点个数：

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$为二叉树的结点个数。

相关问题

二叉树采用二叉链表存储结构，编写算法，求二叉树中叶子结点的数量，以及右子树的高度

二叉树中叶子节点的数量可以通过递归实现，具体算法如下：

1.如果根节点为空，则叶子节点数为0；

2.如果根节点的左右子树均为空，则叶子节点数为1；

3.否则，递归计算左右子树的叶子节点数之和。

算法实现代码：

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

二叉树右子树的高度可以通过递归实现，具体算法如下：

1.如果根节点为空，则右子树高度为0；

2.如果根节点的右子树为空，则右子树高度为0；

3.否则，递归计算右子树的高度，并加上本身的高度。

算法实现代码：

int rightSubtreeHeight(TreeNode* root){
if(root == NULL){
return 0;
}
if(root->right == NULL){
return 0;
}
return 1 + rightSubtreeHeight(root->right);
}

笑话：为什么巨人总是好心情？因为他们从不把小事放在心上！

已知二叉树采用二叉链表存储结构，编写算法统计二叉树中的叶子结点树

在二叉链表存储结构中，二叉树的每个节点由一个数据域和两个分别指向左右子树的指针域组成。叶子节点是指没有子节点的节点。统计二叉树中叶子节点的数量可以通过递归遍历的方式实现。下面是一个统计叶子节点数量的算法示例：

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

def countLeaves(node):
    # 如果当前节点为空，返回叶子节点数为0
    if node is None:
        return 0
    # 如果当前节点是叶子节点，返回叶子节点数为1
    if node.left is None and node.right is None:
        return 1
    # 否则，递归计算左右子树的叶子节点数量，并返回它们的和
    return countLeaves(node.left) + countLeaves(node.right)

# 示例使用：
# 创建一个二叉树的节点
#        1
#       / \
#      2   3
#     /   / \
#    4   5   6
#   /
#  7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.left.left.left = TreeNode(7)

# 统计叶子节点数量
leaf_count = countLeaves(root)
print("叶子节点的数量是:", leaf_count)

在这个示例中，`countLeaves` 函数递归地遍历二叉树的每个节点，并统计叶子节点的数量。如果当前节点为空，则返回0，表示没有找到叶子节点；如果当前节点没有子节点，则返回1，表示找到了一个叶子节点；如果当前节点有子节点，则递归地对其左右子树调用 `countLeaves` 函数，并将结果相加，最后返回叶子节点的总数。