0

我需要帮助理解这个家庭作业。我需要构建一个二元决策树，以找到所有可能的“工作轮班”。基本上，您输入一个作业 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 他似乎指出不使用二叉搜索树

4

1 回答 1

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

我们将另一个标记值 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

无论如何，最终我们将有一棵树，其中一些叶节点将包含 x 表示成功。您在通往该节点的路径上右转的数字为您提供总和 23。

于 2013-11-09T05:33:03.840 回答