假设某二叉树采用二叉链存储结构,请设计递归算法计算该二叉树中结点值为x的结点个数。
时间: 2024-12-11 07:27:07 浏览: 9
题目:编写递归算法,将二叉树中所有结点的左右子树相互交换 - READ.doc
5星 · 资源好评率100%
在二叉链表(Binary Search Tree, BST)中,我们可以使用递归的方式来查找所有值为 `x` 的节点。这里的关键在于我们需要遍历左子树、当前节点以及右子树。当找到一个节点时,如果它的值等于 `x`,就计数加一;否则,继续在左子树或右子树中递归地寻找。
下面是计算二叉树中结点值为 `x` 的结点个数的递归算法:
```c
// 假设树的节点结构体定义为:
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// 函数声明
int countNodes(Node* root, int x);
// 递归函数实现
int countNodes(Node* node, int x) {
// 如果节点为空,则返回0
if (node == NULL)
return 0;
// 如果节点的值等于x,计数加一
if (node->data == x)
return 1 + countNodes(node->left, x) + countNodes(node->right, x);
// 不等于x时,只检查左子树或右子树,根据情况选择递归
else if (node->data < x)
return countNodes(node->right, x); // 如果x大于当前节点,去右边找
else
return countNodes(node->left, x); // 如果x小于当前节点,去左边找
}
// 使用时,从根节点开始调用countNodes
int main() {
// 初始化你的二叉树并获取根节点
Node* root = ...; // 根据实际二叉树创建
int targetValue = x; // 想要查找的目标值
int count = countNodes(root, targetValue);
printf("The number of nodes with value %d is %d.\n", targetValue, count);
return 0;
}
```
阅读全文