查找BST的最大值和最小值

Hello *ers, i am facing a problem with my function in C, i want to create a function that give me the min and max value in BST. The problem is when i use this function it returns the same value for min and max:

你好*ers,我在C中遇到了我的函数问题,我想创建一个函数,它给出了BST中的最小值和最大值。问题是,当我使用此函数时,它返回min和max的相同值:

void Find_Min_Max(node *bt,int* maxint,int* minint)
{
    node *tmp = bt;
    if( bt == NULL)
    {
        *maxint = 0;  // Only if the tree contains nothing at all
        *minint = 0;  // Only if the tree contains nothing at all
    }
   if( bt->left)
       return Find_Min_Max(bt->left,&(*maxint),&(*minint));
   *minint = bt->data;
   if( tmp->right)
       return Find_Min_Max(tmp->right,&(*maxint),&(*minint));
   *maxint = tmp->data;
}

But when i use it to give me just one result max/min, i delete this part of code, everything work perfectly:

但是,当我使用它给我一个最大/最小的结果时,我删除了这部分代码,一切都很完美:

if( tmp->right)
    return Find_Min_Max(tmp->right,&(*maxint),&(*minint));
*maxint = tmp->data;

Any idea how this will work?. Thank you in advance.

知道这将如何工作吗?先谢谢你。

2 个解决方案

#1

It's not really easy / intuitive to recursively compute max and min at the same time in the same function. I would even say it's not possible, because those are two completely different traversals.

在同一个函数中同时递归计算max和min并不是那么容易/直观。我甚至会说这是不可能的,因为这是两个完全不同的遍历。

You should have a function to get the minimum, a function to get the maximum, and call each of them inside Find_Min_Max.

你应该有一个函数来获得最小值,一个函数来获得最大值,并在Find_Min_Max中调用它们中的每一个。

This would be a possible approach:

这可能是一种方法:

int find_min(node *n) {
    if (n == NULL) {
        return 0;

    }
    while (n->left != NULL) {
        n = n->left;
    }
    return n->data;
}

find_max is similar, but traverses right links only:

find_max类似,但仅遍历右链接:

int find_max(node *n) {
    if (n == NULL) {
        return 0;
    }
    while (n->right != NULL) {
        n = n->right;
    }
    return n->data;
}

Then, find_min_max() is easy to code:

然后,find_min_max()很容易编码:

void find_min_max(node *bt, int *min, int *right) {
    *min = find_min(bt);
    *max = find_max(bt);
}

find_min() and find_max() could be recursive, but the iterative approach has the desirable property of using constant memory (and consequently avoids stack overflows).

find_min()和find_max()可以是递归的,但迭代方法具有使用常量内存的理想属性(因此避免了堆栈溢出)。

#2

To find the minimum value in a BST, you follow the chain of left children from the root until you reach a node with no left child. That node contains the minimum value (even if it does have a right child).

要在BST中找到最小值,请从根目录开始跟随左子项链,直到到达没有左子项的节点。该节点包含最小值(即使它确实有一个正确的子节点)。

The algorithm to find the maximum is exactly the mirror image: follow the chain of right children until you reach a node with no right child. That node contains the maximum value.

找到最大值的算法恰好是镜像:跟随正确的子项链,直到到达没有右子的节点。该节点包含最大值。

It does not make sense to try to perform both traversals at the same time, because they follow completely different paths. If you want a single function to discover both the minimum and the maximum value, then it doesn't make much sense for that function itself to be recursive. It could, however, wrap calls to two separate recursive functions, one to find the minimum, and the other to find the maximum.

尝试同时执行两次遍历是没有意义的,因为它们遵循完全不同的路径。如果您希望单个函数同时发现最小值和最大值,那么该函数本身的递归就没有多大意义。但是,它可以将调用包装到两个单独的递归函数中,一个用于查找最小值,另一个用于查找最大值。

#1