Рекурсия и поиск дерева в C? - PullRequest
Новая
       3

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

2 голосов
/ 07 ноября 2010

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

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

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

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

Вот код, который я написал до сих пор: 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;
}

Ответы [ 4 ]

7 голосов
/ 07 ноября 2010

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

Теперь вы хотите вернуть то, что рекурсивные вызовы возвращают 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;
}
3 голосов
/ 07 ноября 2010

Вам не нужно беспокоиться о стеке вызовов; как это работает, скрыт компилятором 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);
1 голос
/ 07 ноября 2010

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

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

0 голосов
/ 07 ноября 2010

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

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, но вокруг него разбросано меньше тестов 'if null'.

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

...