Найти максимальное и минимальное значение 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

Чтобы найти минимальное значение в BST, вы следуете цепочке левых детей из корня, пока не достигнете узла без левого дочернего элемента. Этот узел содержит минимальное значение (даже если у него есть правильный ребенок).

Алгоритм поиска максимума - это именно зеркальное изображение: следуйте цепочке правильных детей, пока не достигнете узла без права ребенка. Этот узел содержит максимальное значение.

Не имеет смысла пытаться выполнять оба обхода одновременно, поскольку они следуют совершенно другим путям. Если вы хотите, чтобы одна функция обнаруживала как минимальное, так и максимальное значение, тогда сама идея не имеет особого смысла быть рекурсивной. Тем не менее, он может обернуть вызовы двум разным рекурсивным функциям, одним из которых является поиск минимума, а другой - для нахождения максимума.

Answer 2

Это не очень просто/интуитивно понятно, чтобы рекурсивно вычислять max и min одновременно в одной и той же функции. Я бы даже сказал, что это невозможно, потому что это два совершенно разных пути.

У вас должна быть функция для получения минимума, функция для получения максимального значения и вызов каждого из них внутри 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() может быть рекурсивным, но итеративный подход имеет желательное свойство использования постоянной памяти (и, следовательно, позволяет избежать переполнения стека).