1

У нас есть заполненное (не пустое) бинарное дерево поиска с вершинами, содержащими поля info-значение,left-указатель на левое поддерево,right-указатель на правое поддерево.

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

Вот моя рекурсивная функция, в которую изначально подаются указатель на корневой узел и любой указатель, который впоследствии и будет ответом:

bool Find(Node *t, Node * &p)
{
    Node *p1;
    if (IsLeaf(t)) { p = t; return true; } 
    else if (p1 = IsOneRoot(t)) { Find(p1,p); return false; }
    else {
        Node *pl,*pr;
        bool b1 = Find(t->left,pl),b2=Find(t->right,pr);
        if (b1 && b2) { p = t; return true; } 
        else p = ( IsLeaf(pl) ? pr : pl );
        return false;
    }
}

, где Node - структура с 3 указанными выше полями;

IsLeaf(Node *x) возвращает true, если *x - лист;

IsOneRoot(Node *x) возвращает указатель на единственного потомка, если же потомка 2 или 0, то возвращает 0.

Функция проходит все тесты, кроме тестов типа:

      20
   15     25
13  17  23  27
   16         30 

Для данного теста выводит 30, хотя, по идее, должно вывести 13 или 23, т.к. они находятся выше. В чём ошибка?

6
  • Алгоритм работает, но есть одна проблема: вы нашли ноду 13, но далее вызов функций Find продолжается и заканчивается на 30, это значение в итоге и возвращается. Необходимо предусмотреть выход из функции, если p уже нашелся, например, за счет проверки на nullptr 19 дек 2015 в 14:22
  • @PavelParshin тут всегда такой вопрос был?
    – Nick Volynkin
    19 дек 2015 в 16:03
  • @Nick: нет, это автовандализм.
    – VladD
    19 дек 2015 в 16:06
  • @VladD с телефона не видна история правок.
    – Nick Volynkin
    19 дек 2015 в 16:16
  • @Nick: А по ссылке: ru.stackoverflow.com/posts/476113/revisions ?
    – VladD
    19 дек 2015 в 16:23

1 ответ 1

1

Вы всегда выбираете ту году, которая стоит правее, а не выше:

p=(IsLeaf(pl) ? pr : pl);

Высота в вашем алгоритме никак не сравнивается. Если надо сравнивать высоту - то стоит возвращать не только найденную вершину, но и глубину, на которой её нашли. Или переписать рекурсивный перебор на очередь, по слоям.

2
  • Сорри, нет сейчас нет доступа к нормальной машине :( Замените возвращаемый тип на структуру (bool, depth, node) - т.е. то же, что сейчас у вас + глубина. Для случая, если возвращается результат из дочерней ноды - увеличивайте depth на 1. Сравнение на isleaf(pl) заменитель н сравнение глубины.
    – user177221
    19 дек 2015 в 15:07
  • @konstantin ваш код приходит в 13, потом в 30. А потом срабатывает проверка Isleaf(13) - true ? 30 : 13. И возвращается 30.
    – user177221
    19 дек 2015 в 15:09

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.