используя возврат с дерева

Question

Я использую алгоритм возврата в дереве благодаря стеку (с push и pop).Это работает, но у меня есть проблема.Путь, заданный стеком, является «неправильным».

bool Prefix(Node*root, stack *tas, char *search)
{
    if (!isEmpty(root))
    {
        if (strcmp(search,root->data) != 0)
            push(tas, root->data, search, root);

        if (strcmp(search,root->data) == 0)
        {
            return True ;
        }

        Prefix(root->left, tas, search);
        Prefix(root->right, tas, search);
    }
    return False;
}

Например, у меня есть дерево как:

     Root
    /    \    
   A      B
  / \    / \
 C   D  E   F    

Когда я хочу, например, путь C,эта функция возвращает RAB (хорошо для R и A, а не B).

Я не знаю, происходит ли это от этой функции или функции push ().Если вы не видите никакой ошибки в функции, я вставлю push (), но она довольно длинная.

Редактировать: Теперь я лучше понимаю, я добавил в функцию:
если узеллист, поп ().Если я ищу F, он возвращает мне RABF вместо RB F. Я не знаю, как избежать сохранения A в стеке.

edit2:

Вот код: (возвращаетRABF вместо RBF)

bool Prefix(Node*root, stack *tas, char *search)
{
    if (!isEmpty(root))
    {
        if (strcmp(search,root->data) == 0)
            return True ;

        if (LeafOrNot(root) == True ){  //it's a leaf, pop()
            pop(tas);

        if (Prefix(root->left, tas, search))
            return True;
        if (Prefix(root->right, tas, search))
            return True;
    }
    return False;
}

Я не понимаю, как я могу получить доступ к дочернему узлу для получения хорошего результата, возможно, добавив еще к if (Префикс (root-> left, tas, search)))У кого-нибудь есть идеи?

спасибо!

Answer 1

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

Простой способ убедиться в этом - просто пройти через вызовы функций (учитывая ваше дерево примеров):

Prefix("Root")
  found "C"?
    no: Prefix("A")
      found "C"?
        no: Prefix("C")
           found "C"?
              yes: return true
        (without check of Prefix("C")): Prefix("D")
           found "C"?
              no: return false
      Prefix("B")
        found "C"?
          no: Prefix("E")
             found "C"?
               no: return false
          Prefix("F")
             found "C"?
               no: return false
       return false
  return false

Показывает порядок вызовов, и отступы примерно соответствуют кадрам в стеке вызовов.

Вы можете видеть, где проверка того, вернет ли вызов Prefix true, позволит ли вам выйти в соответствующее время.

Answer 2

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

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

Например, вы можете сделать это.

bool Prefix(Node*root, stack *tas, char *search)
{
    if (!isEmpty(root))
    {
        push(tas, root->data, search, root);

        if (strcmp(search,root->data) == 0)
        {
            return True;
        }

        if (Prefix(root->left, tas, search))
            return True;
        if (Prefix(root->right, tas, search))
            return True;
    }
    return False;
}