У нас есть заполненное (не пустое) бинарное дерево поиска с вершинами, содержащими поля 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
, т.к. они находятся выше.
В чём ошибка?