この宿題を理解するのに助けが必要です。考えられるすべての「仕事のシフト」を見つける二分決定木を構築する必要があります。基本的に、ジョブ S と、シフトの長さを表す数値の配列を入力します。タスクは、S に等しいシフトのすべての可能な組み合わせを見つけることです。
例：
list of shifts: 43 12 54 3 8 18 3 2 9 15
S = 23
some possible combinations: 12, 3, 8 and 18, 3, 2
これを実装する方法について混乱しています。彼は、「左の子へのトラバーサルはシフトにジョブを選択することを意味し、右の子へのトラバーサルはシフトに特定のジョブを選択しないことを意味する」と述べました。
明らかに役に立ちますが、必ずしもコードは必要ありません:) ps彼は二分探索木を使用しないことを強調しているようでした
シフトはリストにあるため、指定された順序で到着していると想定しています。
リストの最初の位置にいるとしましょう。ノードを作成しましょう。これはツリーのルートにもなります。このノードは現在のノードです。最初の数値 43 が現在のノードに入れられます。今、私たちはそれを取るかどうかを選択できます。43 は 23 よりも大きいので、取りません。つまり、43 を含むノードから左の枝を下ります。ツリーは次のようになります。
43
次に、12 を取得します。したがって、ツリーは次のようになります (横向きの矢印は、右の子またはシフトが取得されたことを意味し、下向きの矢印は、左の子または未取得を意味します)。:
43
|
12
それを取ると、右の枝を下る必要があります。次の番号は 54 です。それを現在のノードに入れましょう。
43
|
12 - 54
54 は大きすぎます。それで、左の枝を下ります。次の番号は 3 です。それを現在のノードに入れます。
43
|
12 - 54
|
3
この番号3が取られます。次の数字 8 も同様です。これで 23 が得られます。センチネル値 (x 記号) をここに入れましょう。これは、23 に到達したことを示します。ツリーは次のようになります。
43
|
12 - 54
|
3 - 8 - x
さて、8 までさかのぼります。次に、左の枝を下って 18 を見つけます。ツリーは次のようになります。
43
|
12 - 54
|
3 - 8 - x
|
18
大きすぎるので、18 にはしません。次に、3、2 .. この方法でツリーを構築し続けます。
43
|
12 - 54
|
3 - 8 - x
|
18
|
3 - 2 - 9
|
15
|
o
15 の左側の子に別のセンチネル値 o を配置して、入力が使い果たされたためにこれ以上進むことができないことを示します。ここで 2 までさかのぼり、次に 2 を取らないことを検討し、リストから再び 9 を受け取ることができます。しかし、それで合計が 23 になることもありません。
43
|
12 - 54
|
3 - 8 - x
|
18
|
3 - 2 - 9
| |
9 15
| |
15 o
|
o
そしてそれは続きます：
43
|
12 - 54
|
3 - 8 - x
|
18
|
3 --- 2 - 9
| | |
2-9 9 15
| |
15 o
|
o
いずれにせよ、最終的には、成功を示す x が含まれる葉ノードがいくつかあるツリーができあがります。そのノードへのパスで右折した数は、合計 23 になります。