时间戳

首页 > 解决方案 > 遍历树收集节点组合

java - 遍历树收集节点组合

问题描述

摘要：我有一棵树，其中包含汽车零件，我需要从中构建这些零件的所有有效组合。

可能需要零件 - 每个构建都必须包含它们。

零件可以是可选的。

零件可能与其他零件发生冲突。

零件内部可以有可选零件。

示例树：

Car
| - Motor (required)
| - - V8
| - - V12
| - - - Colour (optional)
| - - - - Black
| - - - - Chrome
| - Transmission (required)
| - - Mechanical
| - - Automatic
| - Wheels (optional)
| - - Basic
| - - Fancy
| - - - Colour (optional)
| - - - - Red
| - - - - Blue
| - BodyStyle (optional)
| - - Hatchback (conflicts with Motor.V12)
| - - Buggy (conflicts with Motor.V8)

此树的有效构建：

Car | Motor.V8 | Transmission.Automatic
Car | Motor.V8 | Transmission.Automatic | Wheels.Basic
Car | Motor.V12.Colour.Black | Transmission.Automatic | Wheels.Basic
Car | Motor.V8 | Transmission.Automatic | BodyStyle.Hatchback
Car | Motor.V12 | Transmission.Mechanical | Wheels.Fancy | BodyStyle.Buggy
Car | Motor.V12 | Transmission.Mechanical | Wheels.Fancy.Colour.Red | BodyStyle.Buggy

我应该朝着什么方向去解决这个任务？

这应该是一项相对容易的任务，但我什至在努力从哪里开始。

标签： javaalgorithmtree

解决方案

鉴于您要问如何开始，这里有一个建议：

  1. 从一个接口开始，该接口代表您可能需要查询的有关节点的任何内容
  2. 编写该接口的最简单实现（例如，您的“蓝色”叶节点）。包括单元测试以确保它符合您的要求。
  3. 继续遍历其余节点，直到它们都按照您的预期进行。
  4. 现在编写一个全新的类，它只使用接口方法生成所有变体。

推荐阅读