Определить, на каком уровне находится элемент в дереве

ProgramBox

Определить, на каком уровне находится элемент в дереве

Post author:admin
Запись опубликована:14 апреля, 2023
Post category:Вопросы по программированию

#c #recursion #tree #binary-search-tree #function-definition

#c #рекурсия #дерево #двоичный файл-дерево поиска #функция-определение

Вопрос:

Итак, у меня возникла проблема, когда я должен найти уровень элемента в дереве. Кажется, ничего не получается, поэтому я обращаюсь сюда за помощью.

Это то, что у меня пока есть. Проблема здесь в том, что 4-е утверждение, где возвращаемый уровень должен быть равен 2, не работает, и утверждение получает предупреждение. Я думал о том, чтобы, возможно, попытаться не делать это рекурсивно, но как это можно сделать?

 int findElementLevel(const BSTree tree, const int element) {

    int level = 0;

    if (tree == NULL) {
        return -1;
    }

    if (tree->data == element) {
        return level;
    }

    if (element < (tree)->data) {
        level  ;
        findElementLevel(tree->left, element);
        return level;
    }

    if (element > (tree)->data) {
        level  ;
        findElementLevel(tree->right, element);
        return level;
    }
}

void testNewTree(void) {

    BSTree tree = emptyTree();
    assert(isEmpty(tree));

    int arr[5] = {3,2,5,1,4}, i;

    for (i = 0; i < 5; i  )
    {
        insertSorted(amp;tree, arr[i]);
    }

    assert(findElementLevel(tree, 3) == 0);

    assert(findElementLevel(tree, 2) == 1);

    assert(findElementLevel(tree, 5) == 1);

    assert(findElementLevel(tree, 1) == 2);

    assert(findElementLevel(tree, 4) == 2);

}

1. level является локальной переменной. При возврате функции верхнего уровня всегда будет 0 или 1.

2.Вы сбрасываете локальную переменную level при каждой рекурсии. Возможно, так и должно быть static int level = 0; и тогда вам также нужно уменьшить значение при возврате (чтобы это сработало в следующий раз).

3. Уровень должен начинаться с 0, но не сбрасываться при возврате функции. Но у меня закончились идеи о том, как это исправить. Не допускается, чтобы level был статической или глобальной переменной

4. Почему это не разрешено?

5. Это может быть параметр функции.

Ответ №1:

Функция всегда начинается с объявления локальной переменной level, для которой установлено значение 0.

 int findElementLevel(const BSTree tree, const int element) {

    int level = 0;

Это значение, равное 0 (или 1 из-за его увеличения при текущем вызове рекурсивной функции) ), возвращается в случае, когда целевой элемент найден на любом фактическом уровне

 if (tree->data == element) {
    return level;
}

Вы должны накапливать уровни.

Рекурсивная функция может быть определена, например, следующим образом

 int findElementLevel(const BSTree tree, const int element) {
    if (tree == NULL) {
        return -1;
    }
    else  if ( element < tree->data ) {
        int level = findElementLevel(tree->left, element);
        return level == -1 ? level : level   1;
    }
    else if ( tree->data < element ) {
        int level = findElementLevel(tree->right, element);
        return level == -1 ? level : level   1;
    }
    else {
        return 0;
    } 
}

Обратите внимание на то, что квалификатор const для второго параметра не имеет большого смысла, поскольку функция имеет дело с копией значения предоставленного аргумента. Функция может быть объявлена точно так же, как

 int findElementLevel(const BSTree tree, int element);

1. Я должен вернуть, на каком уровне элемент находится в дереве. Я также не понимаю, что здесь происходит «? уровень: level;»

2. @JohnJohn: Если вы замените его return level == -1 ? level : level; на return level < 0 ? -1 : level 1; , это сделает то же самое, и вы, возможно, поймете это лучше. Выражение a ? b : c проверяет a и использует, b если a это true и c если a это false. (Этот троичный оператор ? : также можно использовать для выбора ветви дерева для изучения и устранения избыточного кода; нам не нужны отдельные предложения и вызовы для левой и правой сторон.)

3. @JohnJohn Если следующий рекурсивный вызов возвращает значение -1 (это означает, что элемент не найден), то он возвращается дальше. В противном случае, если он найден при следующем вызове, он возвращается увеличенным.

4. @JohnJohn На самом деле эта конструкция возвращает level == -1 ? level: уровень ; эквивалентно уровню возврата if ( level == -1 ); else возвращает уровень ;

5. Хорошо, я думаю, теперь все получилось. Просто нужно провести еще некоторое тестирование перед отправкой, спасибо за всю помощь. Свяжется, если возникнут дополнительные проблемы.

Ответ №2:

Эту функцию проще и короче писать итеративно, чем рекурсивно. Код просто:

 int findElementLevel(const BSTree tree, const int element)
{
    for (int level = 0; tree;   level)
    {
        if (tree->data == element)
            return level;
        tree = tree->data < element ? tree->left : tree->right;
    }
    return -1;
}

С пояснением, это:

 int findElementLevel(const BSTree tree, const int element)
{
    /*  Use a loop to process each level.  We start counting levels at zero and
        increment on each iteration.  We continue as long as there is more of
        the tree to explore ("tree" evaluates as true, i.e., non-null), or jump
        out of the loop with a return if the target element is found.
    */
    for (int level = 0; tree;   level)
    {
        //  If we found the target, return the level it is on.
        if (tree->data == element)
            return level;

        /*  Otherwise, descend to the left or the right according to which
            side the target element must be on.
        */
        tree = tree->data < element ? tree->left : tree->right;
    }

    /*  If we reached the end of the tree without finding the element, return
        -1.
    */
    return -1;
}