Минимальное значение элемента в двоичном дереве поиска

Question

Итак, я читал книгу - Упрощенные структуры данных и алгоритмы, Нарасимха Каруманчи, и в ней дано нижнее значение bst сниппета - проблема 61 в главе BST. Фрагмент меня очень смутил, и теперь я просто хочу знать, как он работает: Фрагмент, как следует:

node* floorValue(node* root, node* prev ,int k)
{
    if(!root){
        return NULL;
    }

    if( !(floorValue(root->left , prev ,k))
    {
        return 0;
    }
    if(root->data == k)
    {
        return root;
    }
    if(root->data > k)
    {
        return prev;
    }
    prev = root;
    return floorValue(root->right , prev , k);
}

В этом node* prev, который инициируется с помощью NULL, хранит предыдущий узел и int k - это целое число, для которого мы находим минимальное значение.

Может кто-нибудь, пожалуйста, помогите мне понять его рекурсию. Я запутался, потому что:

1. Код: if( !(floorValue(root->left , prev ,k)) { return 0; } вернет 0 при попадании в самый левый элемент дерева. Но это приведет к тому, что все рекурсивные вызовы вернут 0.

Почему он возвращает 0, когда мы возвращаем node*, а не int

Помощь будет очень признательна. Я решил этот вопрос, но он использовал не этот метод, а более простой (на мой взгляд). Я хочу знать, что я делаю не так или чего мне не хватает в этом коде.

Входные данные: Первыми входными данными будет количество узлов: следующие n строк будут данными узлов. Первый ввод после n будет значением root.

ПОЛНЫЙ КОД:

#include<bits/stdc++.h>
using namespace std;

struct node
{
  int data;
  node* left;
  node* right;
};

node* insertBST(node* root , int x)
{

    if(root==NULL)
    {
        node* root= new node;
        root->data = x;
        root->left = root->right = NULL;
        return root;
    }
    else
    {
        if(x <root->data)
        {
            root->left = insertBST(root->left , x);
        }
        else
        {
            root->right = insertBST(root->right , x);
        }

    }
}

void inorder(node* root)
{
    if(root)
    {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

node* floorValue(node* root, node* prev ,int k)
{
    if(!root){
        return NULL;
    }

    if( !(floorValue(root->left , prev ,k))
    {
        return 0;
    }
    if(root->data == k)
    {
        return root;
    }
    if(root->data > k)
    {
        return prev;
    }
    prev = root;
    return floorValue(root->right , prev , k);
}
int main()
{
    int n;
    cin>>n;
    node *root = new node;
    root = NULL;
    for(int i = 0 ;i<n;i++)
    {
        int k;
        cin>>k;
        root= insertBST(root , k);
    }

    inorder(root);
    
    cout<<"\nEnter the Value for which floor has to be searched : ";
    int k;
    cin>>k;
    
    node* prev = NULL;
    cout<<floorValue(root , prev, k);
    return 0;
}

Код в точности такой же, как и в книге, за исключением некоторых имен переменных.

Спасибо и заранее спасибо.

Answer 1

Фрагмент, который вы нашли, ужасен, но ответ на ваши вопросы таков: return 0 то же самое, что return NULL - это не целое число, это нулевой указатель. Код должен возвращать null, если в дереве нет узла <= значение поиска. </p>

Вот гораздо лучшая реализация:

Node* floorNode(Node* tree, int k) {
    Node *flr = NULL;
    while(tree) {
        if (tree -> data <= k) {
            flr = tree;
            tree = tree->right;
        } else {
            tree = tree->left;
        }
    }
    return flr;
}

Answer 2

Классный c Алгоритм двоичного поиска. Я всегда рекомендую вам разобраться в проблеме, которую вы разместили. Если вы разберетесь с алгоритмом, вы узнаете, как на самом деле работает двоичный поиск, а также как работает Backtrack с использованием StackTrace в вашей системе / памяти компьютера.

Давайте погрузимся в это. :)

if(!root){
    return NULL;
}

приведенный выше фрагмент кода, если вы дойдете сюда, гарантируется, что вы просмотрели все возможности, но не нашли нужный вам «ключ». : (

if( !(floorValue(root->left , prev ,k))
{
    return NULL; 
}

Помните, что вы должны возвращать NULL вместо возврата 0, поскольку возвращаемое значение вашей функции на самом деле NULL (хотя оба значения 0 / NULL определяют ложный случай в c / c ++, вы преждевременно вы можете использовать любой из них.

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

if(root->data == k)
{
    return root;
}

Если вы дойдете сюда, поздравляю, вы наконец достигли пункта назначения: D, другими словами, вы нашли свой результат в огромных (или маленьких, любых) элементах ввода .

if(root->data > k)
{
    return prev;
}

Приведенный выше фрагмент будет таким же, когда ваши средние элементы больше, чем ваш ключ, поэтому вы знаете, что вам нужно go левую сторону ваших входов. (Движение вправо всегда вызывает у вас печаль, вы закончится ничем).

 prev = root;
return floorValue(root->right , prev , k);

Приведенный выше код говорит вам, что вы пошли влево, но получили 0 (в итоге вы не смогли найти результат), поэтому вам нужно go вправо сторона сейчас.

Теперь самое главное, поймите эти два следующих фрагмента:

if(root->data > k)
{
    return prev;
}

и

 prev = root;
 return floorValue(root->right , prev , k);

Два приведенных выше фрагмента не только погружают вас в левую или правую часть вашего дерево (или входы), но также проверяет каждый левый и правый узел вашего левого Дерева, а также правый и левый узел вашего правого Дерева.

Когда ему не удалось получить нужный ключ, он возвращается на ваше место где вы начали go в LEFT (это своего рода ТЕМНАЯ серия, давайте предположим, что left - ПРОШЛОЕ здесь,: D right ?? ) теперь вам нужно go to future, это ПРАВИЛЬНО, чтобы узнать ключ.

вы получили ключ? верните его слева (прошлое) или go снова направо (будущее).

вы обязательно придете к выводу, либо УСПЕХ, либо НЕУДАЧА.

наслаждайтесь.