Рекурсия и поиск по дереву в C?

Вид нового для деревьев и рекурсивных функций....

Я знаю основы создания стека и создания рекурсивных функций.

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

У меня проблемы с возвратной частью... Я пробовал кое-что читать в стеках вызовов... но не понимаю, как это реализовать. Это уже есть или мне нужно сделать этот стек? Как мне сделать этот стек, если я должен это сделать? Я читал, что он должен быть пропорционален высоте дерева... Является ли лучший способ найти высоту дерева, чтобы сделать другую функцию, которая делает это?

Вот некоторый код, который я написал до сих пор: Tree и NodePtr - это указатель на узел...

NodePtr SearchTree(int v, Tree T)
{
    //printf(" %i \n", T->value);

    if(T->value == v) 
    {
        return T;
    }
    else
    {
        if(T->Left != NULL) SearchTree(value, T->Left);
        if(T->Right != NULL) SearchTree(value, T->Right);
    }

    return NULL;
}

c tree binary-tree callstack
person Bri    schedule 07.11.2010    source источник

Ответы (4)


arrow_upward
7
arrow_downward

Прежде всего, см. рекурсия.

Теперь вы хотите вернуть то, что возвращают рекурсивные вызовы SearchTree(), потому что вы используете рекурсию для делегирования проблемы двум экземплярам самого себя, поэтому, если вы не получите возвращаемое значение вверх по течению, ничто не может работать:

NodePtr SearchTree(int v, Tree t)
{
    printf(" %i \n", t->value);
    if (t->value == v) {
        return t;
    } else {
        if (t->Left != NULL) {
            NodePtr left = SearchTree(v, t->Left);
            if (left != NULL) {
                return left;
            }
        }
        if (t->Right != NULL) {
            return SearchTree(v, t->Right);
        }
    }

    return NULL;
}
person Frédéric Hamidi    schedule 07.11.2010
comment
Если левое поддерево не равно нулю, и поиск не может найти в нем значение, он не ищет в правом поддереве. Иногда он не находит нужный узел. - person Ira Baxter; 07.11.2010
comment
@ Ира, да, я тоже это видел, но ошибка в коде спрашивающего ... мы должны решить все его ошибки или ответить на его вопрос? ;) Тем не менее ответ превентивно обновлен. - person Frédéric Hamidi; 07.11.2010
comment
Правда, вы не можете ответить на все подразумеваемые вопросы или решить все невысказанные проблемы. Но для рекурсии людям обычно нужна помощь с базовым случаем, рекурсией и обработкой ответа от рекурсивного вызова. - person Ira Baxter; 07.11.2010
comment
@ Ира, я понимаю твою точку зрения, и в нашем случае она верна. Спасибо :) - person Frédéric Hamidi; 07.11.2010

arrow_upward
3
arrow_downward

Вам не нужно беспокоиться о стеке вызовов; то, как это работает, скрыто компилятором C, и если вы не ищете невероятно глубокие деревья, это не будет вас беспокоить.

Ваш алгоритм более или менее верен, но вам нужно проверить возвращаемое значение из рекурсивного вызова, чтобы увидеть, является ли оно нулевым, прежде чем вы посетите другое поддерево. Что-то типа:

    if(T->Left != NULL) { NodePtr temp=SearchTree(value, T->Left); 
                          if (temp !=NULL)  return temp; 
                        } 
    if(T->Right != NULL) return SearchTree(value, T->Right);
person Ira Baxter    schedule 07.11.2010

arrow_upward
1
arrow_downward

Вам не нужно создавать стек вызовов самостоятельно. Это структура данных, поддерживаемая средой выполнения, в которой выполняется ваша программа, такой как ваша операционная система или виртуальная машина Java, если вы используете Java. Всякий раз, когда вызывается функция, ее аргументы и локальные переменные помещаются в стек. Когда функция существует, они выталкиваются.

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

person Dima    schedule 07.11.2010

arrow_upward
0
arrow_downward

Все специальные корпуса в ответе Иры Бакстер и ответе Фредерика Хамиди предполагают, что дизайн не совсем правильный:

NodePtr SearchTree(int v, NodePtr T)
{
    if (T == NULL || T->value == v)
        return T;
    NodePtr R = SearchTree(v, T->Left);
    if (R == NULL)
        R = SearchTree(v, T->Right);
    return R;
}

Это, я почтительно заявляю, проще. Конечно, при работе с конечным узлом NULL он выполняет еще один вызов функции, но тестов «если null» разбросано меньше.

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

person Jonathan Leffler    schedule 07.11.2010