C-查找BST的最大值和最小值

Question

你好stackoverflowers，我在C中的功能面临问题，我想创建一个功能，使我在BST中的最小值和最大值。问题是当我使用此功能时，它返回了最小值的相同值，最大值：

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;
}

但是，当我用它给我最大一个结果时，我删除了代码的这一部分，一切都可以完美地工作：

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

知道这将如何工作吗？预先感谢您。

Answer 1

在同一函数中同时递归计算最大和最小并不真正容易/直观。我什至会说这是不可能的，因为这是两个完全不同的遍历。

您应该有一个函数以获取最低限度，一个函数以获取最大值，并在Find_Min_Max中调用每个功能。

这将是一种可能的方法：

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

find_max是相似的，但仅遍历正确的链接：

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

然后， find_min_max()易于编码：

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

find_min()和 find_max()可能是递归的，但是迭代方法具有使用恒定内存的理想属性（因此避免了堆栈溢出）。

Answer 2

要在BST中找到最小值，您从根部遵循左子女的链条，直到到达没有左子女的节点为止。该节点包含最小值（即使它确实有合适的孩子）。

找到最大值的算法完全是镜像：遵循正确的孩子的链条，直到到达没有正确的孩子的节点为止。该节点包含最大值。

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

Answer 3

在BST中查找最小值和最大值非常容易。请检查下面的两个代码段，我说明这些代码的工作方式。

public int minValueInBST(Node node){
    if (node == null) throw new IllegalStateException();
    Node current = node;
    while (current.leftChild != null) {
        current = node.leftChild;
    }
    return current.value;
}

要找到BST中的最小值，我们必须找到最左的叶节点，因为该节点包含最小值。因此，首先，我们检查根节点是null是否为null是否为null，我们投掷IllegalStateException，否则我们找到了左节点，终于，我们返回左节点值。

。

public int maxValueInBST(Node node){
    if (node == null) throw new IllegalStateException();
    Node current = node;
    while (current.rightChild != null) {
        current = node.rightChild;
    }
    return current.value;
}

要找到BST中的最大值，我们必须找到最右侧的叶节点，因为该节点包含最大值。因此，首先，我们检查根节点是null是否为null，是否为null我们投掷illegalstateexception，否则我们找到了正确的节点，终于，我们返回正确的节点值。

Answer 4

// try this
tree_node *min(tree_node *root)
{
    if (!root)
    {
        printf("Tree is empty");
        exit(1);
    }
    tree_node *ret_val;
    if (root->left == NULL)
    {
        ret_val = root;
    }
    else
    {
        ret_val = min(root->left);
    }
    return ret_val;
}
tree_node *max(tree_node *root)
{
    if (!root)
    {
        printf("Tree is empty");
        exit(1);
    }
    tree_node *ret_val;
    if (root->right == NULL)
    {
        ret_val = root;
    }
    else
    {
        ret_val = max(root->right);
    }
    return ret_val;
}

完成代码