假设二叉树中每个结点值为单个字符,采用二叉链存储结构存储。试设计一个 算法采用先序遍历方式求一棵给定二叉树 b 中的所有大于 x 的结点个数;并用相关数据 进行测试。
时间: 2024-02-18 09:04:54 浏览: 45
算法如下:
```
int countGreater(Node* root, char x) {
if (root == NULL) {
return 0;
}
int count = 0;
if (root->data > x) {
count = 1;
}
return count + countGreater(root->left, x) + countGreater(root->right, x);
}
```
其中,`Node` 表示二叉树结点,`data` 表示结点的值,`left` 和 `right` 分别表示左子树和右子树。
该算法使用递归的方式进行先序遍历,如果当前结点的值大于 x,则计数器加 1。然后递归遍历左子树和右子树,将计数器相加并返回。
测试数据如下:
```
A
/ \
B C
/ \ / \
D E F G
```
使用如下代码进行测试:
```
Node* root = new Node('A');
root->left = new Node('B');
root->right = new Node('C');
root->left->left = new Node('D');
root->left->right = new Node('E');
root->right->left = new Node('F');
root->right->right = new Node('G');
cout << countGreater(root, 'D') << endl; // 4
```
结果为 4,说明有 4 个结点的值大于 D。
阅读全文