从二叉搜索树的根结点一直沿右儿子向下找不一定能找到树中值最大的结点。
时间: 2024-04-01 10:36:55 浏览: 18
这是正确的。二叉搜索树的特点是,对于每个结点,其左子树中的所有结点的值都小于该结点的值,而其右子树中的所有结点的值都大于该结点的值。因此,从根结点开始一直沿右儿子向下找,会找到最右边的结点,但不一定是树中值最大的结点。因为在左子树中可能存在比该结点的值更大的结点。要找到树中值最大的结点,需要一直沿右儿子向下找到最右边的叶子结点。
相关问题
用先根遍历法,找树中值最大的结点C语言
实现代码如下:
```
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode;
// 定义先根遍历函数
void preorder(TreeNode* root, int* maxVal) {
if (root == NULL) {
return;
}
// 对比当前结点值和最大值,如果大于则更新最大值
if (root->val > *maxVal) {
*maxVal = root->val;
}
// 递归遍历左子树
preorder(root->left, maxVal);
// 递归遍历右子树
preorder(root->right, maxVal);
}
// 找树中值最大的结点
int findMaxNode(TreeNode* root) {
if (root == NULL) {
return -1;
}
// 初始化最大值为根结点的值
int maxVal = root->val;
// 先根遍历查找最大值
preorder(root, &maxVal);
return maxVal;
}
```
调用函数 `findMaxNode`,传入根结点即可找到树中值最大的结点。
找树中值最大的结点c语言
实现代码如下:
```c
#include <stdio.h>
struct node {
int value;
struct node *left;
struct node *right;
};
int findMaxValue(struct node *root) {
if (!root) {
return 0;
}
int maxValue = root->value;
int leftValue = findMaxValue(root->left);
int rightValue = findMaxValue(root->right);
if (leftValue > maxValue) {
maxValue = leftValue;
}
if (rightValue > maxValue) {
maxValue = rightValue;
}
return maxValue;
}
int main() {
struct node n7 = {10, NULL, NULL};
struct node n6 = {7, NULL, NULL};
struct node n5 = {9, NULL, NULL};
struct node n4 = {15, NULL, NULL};
struct node n3 = {8, &n6, &n7};
struct node n2 = {12, &n4, &n5};
struct node n1 = {13, &n2, &n3};
int maxValue = findMaxValue(&n1);
printf("The maximum value in the tree is %d\n", maxValue);
return 0;
}
```
在这里,我们定义了一个结构体 `node`,它表示树中的每个节点,包括值以及左右子节点的指针。然后我们定义了一个 `findMaxValue` 函数,该函数在树中查找并返回最大值。在递归算法中,首先检查当前节点是否为空,然后将当前值与左右子节点的值进行比较,更新最大值并返回。在 `main` 函数中,我们创建一个树,然后调用 `findMaxValue` 函数并打印结果。