ツリーが偶数個のノードを持つ場合、バイナリツリーが与えられ、真を返すブール関数を書く

Question

Q：バイナリツリーを与えられたブール関数を書いて、 ツリーが偶数ノード数。空のツリーは偶数のノードを持つとみなされます。

注：

関数はただ一つの引数、根へのポインタを持っている必要があります。

グローバル変数は使用できません。

追加の機能は定義できません。

Answer 1

以下は、1つのノードで構成されるツリーが奇数であることを前提としています。つまり、ツリーがルートノードのみで構成されている場合、そのツリーには奇数のノードがあります。あなたの説明で「空の木」が何を意味するのかは不明です。私はそれが "ヌル・ルート"を意味すると仮定した。

ノードが結合されていても、その子ノードが奇数個であっても、ノードを考えることができます。はい、奇妙です。ノード自体を数えなければならないからです。

1 
2 3 

ノードの子ノードは、偶数のノードを持ちます。しかし、ルートノードも数えなければなりません。

したがって、1つの子ノードには偶数のノードが必要で、もう1つのノードには奇数のノードが必要です。

は大きな木を考えてみましょう：

 1 
    2  3 
4 5  6 
7 

ノード4が偶数です。ノード5は奇数です。ノード2は偶数です。ノード6は奇数です。ノード3は偶数です。両方の子が偶数であるため、ノード1は奇数です。

left right result 
false false false 
false true true 
true false true 
true true false 

両方に該当する、またはその両方が偽であれば、それは偽です：さえ= trueとfalse =奇数と仮定

真理値表、。どちらかが真であれば、結果は真です。それは排他的なものです。

これは再帰的に機能します。上記の木を試してみましょう。

• 7にはノードがないため、結果は奇数です。
• 4には、奇数の左ノードと偶数の右ノードがあります（ヌルノードは偶数とみなされます）。 4は偶数です。
• 5にノードがないため、奇妙です。
• 2は、4が偶数であり、5が奇数であっても同じです。
• 6は子がないために奇数です。
• 3は左が偶数で右が奇数であるためです。
• 左辺ノードと右辺ノード（2と3）が両方とも偶数であるため、1は奇数です。

説明を与えられた再帰関数を書くことができるはずです。

Answer 2

Bool isEven(treepr *p) 
{ 
    if(p) 
    { 
     if(isEven(p->left) == isEven(p->right)) 
      return false; 
     else 
      return true; 
    } 

    return true; 
}