このコードブロックはどのように世界でどのように動作しますか？

Question

以下のコードブロックはどのくらい正確に機能しますか？より具体的には、プログラムはどのオプションを返すのかをどのように知っていますか？

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

このコードブロックは、コードの一部が、一つのノードがツリー内のノード1とノード2を与え、他方の祖先であるかどうかを決定するためにツリーをトラバースすることです。

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

Answer 1

返されるオプションはどのように分かりますか？

プログラムは、機能するものが見つかるまで、オプションを試し続けます。

次のコードブロックはどのくらい正確に機能しますか？祖先（）を呼び出すたびに

は、機能は4つの可能性を試みます：その左部分木に

• 移動ノード1を、問題の残りの残りの部分を介して動作してみてください。
• これでうまくいかなかった場合は、node1を右のサブツリーに移動してみてください。
• これでうまくいかなかった場合は、node2を左のサブツリーに移動してください。
• これでうまくいかなかった場合は、node2を右のサブツリーに移動してください。

4つの可能性がすべて失敗した場合、node1とnode2のノードは、祖先関係を介して必ずしも関連していません。

警告：実装されているように、非常に小さいツリーを除いて、祖先関数は非常に遅いです。各ancestor（）コールで4つのオプションを試すので、ツリーの高さを1つ増やすと州の数は約4倍になります。

Answer 2

真ancestorリターンへの呼び出しのいずれかが、それが返されます：ノード1とノード2が可能祖先/子孫関係が存在するかどうかを判断する責任がある関数に渡されていることを

は注意真（残りの呼び出しを評価することなく）。

Answer 3

用語は左から右に評価及びtrueある最初の評価（ショートカットブール評価）を終了し、trueが返される。れますそれ以外の場合は、結果はfalseです。

Answer 4

左から右に評価されるので、最初にancestor (node1->left(), node2)をテストします。次に、bitwise演算子||を見て、基本的に「前の演算が偽であれば、次にこの演算を試してください」と言う。

Answer 5

私はあなたの関数がboolを返すと思います。祖先の1人が真であれば、それは真を返します。あなたは2つのブール値を使用している場合、結果は次のとおりです。

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

あなたは、いくつかのブール値を使用する場合（または値を、それはブール値として解釈することができる）、A||B||C..は、それが戻ってい((A||B)||C)||...

Answer 6

に等しいよりも、ブール値だからあなたが参照しているブロックは、見つかった最初のtrueの値を返すためにshort circuitingを使用するか、またはすべてがそのように評価される場合はfalseを返します。

Answer 7

ここで、ステートメントには||でリンクされたいくつかの節があります。または& &の場合、左から右への評価で、最初の機会に短絡します。この場合、||関数が左から右（またはコードレイアウトの上から下）に動作し、何かがtrueを評価する最初のときにはtrueを返し、他のオプションの評価を避けます。

Answer 8

祖先はtrue/falseのみを返すことに注意してください。このコードは、初期の論理式評価を利用しています。 'または'（||）文で指定します。最初の呼び出しがtrueを返さない場合は、次の呼び出しを呼び出します。いずれもtrueを返さない場合、falseが返されます。

このコードでは、node1-> left（）がnode2の祖先であることが判明した場合、私はすでに答えを知っているので、残りの文を評価する必要はありません。