Построение двоичного дерева решений для всех комбинаций чисел, равных значению

Question

Мне нужна помощь в понимании этого задания на домашнюю работу. Мне нужно построить двоичное дерево решений, которое найдет все возможные «сдвиги для работы». В основном вы вводите задание 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 Казалось, он пытался не использовать двоичное дерево поиска.

Answer 1

Я предполагаю, что сдвиги поступают в данном порядке, так как они находятся в списке.

Предположим, что мы находимся на первой позиции списка. Давайте сделаем узел, это также послужит корнем дерева. Этот узел является текущим узлом. Первое число 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, чтобы указать, что мы не можем идти дальше, потому что вход исчерпали. Мы можем проследить назад до 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 

Anywyas, в конечном счете, мы будем иметь дерево, где некоторые из узлов листа будет содержать х индикации успех. Число, которое вы приняли правильно, поворачивается на пути к этому узлу, дает вам сумму 23.