Как в мире этот блок кода работает [деревья]?

Question

Как именно работает блок кода ниже?В частности, как программа узнает, какую опцию возвращать?

return    ancestor (node1->left(), node2)
           || ancestor (node1->right(), node2)
           || ancestor (node2->left(), node1)
           || ancestor (node2->left(), node1);

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

Обратите внимание, что узел 1 и узел 2 передаются в функцию, которая отвечает за определение наличия возможных отношений предок / потомок:

bool ancestor (const Binary_node<Type> * node1, const Binary_node<Type> * node2)
{
         // .... code
}

Answer 1

Как программа узнает, какую опцию вернуть?

Программа продолжит пробовать варианты, пока не найдет тот, который работает.

Как именно работает блок кода ниже?

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

• Переместите узел 1 в его левое поддерево и попробуйте пройти оставшуюся часть проблемы.
• Если это не сработало, попробуйте переместить узел 1 к его правому поддереву.
• Если это не сработало, переместите узел 2 на левое поддерево.
• Если это не сработало, вместо этого переместите узел 2 к его правому поддереву.

Если все четыре возможности потерпели неудачу, то узлы node1 и node2, несомненно, не связаны через отношения предков.

Предупреждение: Как реализовано, функция предка очень медленная, за исключением очень маленьких деревьев. Поскольку в каждом вызове ancestor () мы используем четыре параметра, число состояний примерно в четыре раза увеличивается при увеличении высоты дерева на 1.

Answer 2

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

Answer 3

Если один из вызовов ancestor вернет true, он вернет true (без оценки остальных вызовов).

Answer 4

Обратите внимание, что предок возвращает только true / false. Этот код использует раннюю оценку логических выражений. В операторе 'или' (||). если первый вызов не возвращает true, он вызывает следующий и так далее, пока один из них не вернет true. Если ни один из них не возвращает true, возвращается false.

В этом коде: если я узнаю, что node1-> left () является предком node2, мне не нужно оценивать оставшуюся часть утверждения, поскольку я уже знаю ответ.

Answer 5

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

Answer 6

Возвращает логическое значение.Таким образом, блок, на который вы ссылаетесь, просто использует короткое замыкание для возврата первого найденного значения true или false, если все они оцениваются как таковые.

Answer 7

Я полагаю, что ваша функция возвращает bool.Если один из предков верен, он вернет истину.Если вы используете два логических значения, результат будет следующим:

A       B     (A  ||  B)
false  false    false
true   false    true
false  true     true
true   true     true

Если вы используете несколько логических значений (или значений, которые можно интерпретировать как логические), то A||B||C.. равно ((A||B)||C)||...

Answer 8

Оценивает слева направо, поэтому сначала проверяет ancestor (node1->left(), node2).Далее он смотрит на побитовый оператор ||, который в основном говорит: «Если предыдущая операция ложная, попробуйте следующую».