考虑以下示例:
这些是输入:
sed
BTY
sed ->CWD
CWD->DTT
EI->FHK
这些只是一个字符串。它们没有特别的意义。但"→";表示作为克隆传播。我想根据这些条目找到DTT的父亲。
有没有更快的解决方案?
我没有问编码，我只问方法。
这完全取决于令牌(ASED,CWD等)是否唯一。另外，您是想只使用标准c++库还是愿意使用其他库?
假设令牌是唯一的，并且您希望使用标准c++。在标准c++中没有树数据结构，但是在这种情况下，你不需要它们来解决你的问题。
还假设一个令牌只能有一个父级，您可以将表达式parent -> child还原为child -> parent(在您的算法中，而不是在输入列表中)。完成后，可以将子节点存储为map的键，将父节点存储为值。您需要将stop key作为一个值(例如NULL)引入，以表示特定的键没有父键。
要提取父节点，您需要从对应于子节点的映射中获取值，子节点是中间的父节点(链接)。接下来，获取中间父节点以获取其父节点。这将重复，直到您到达停止键。
由于这种方法的复杂性，取决于您选择哪种类型的mapstd::map或std::unordered_map
该算法可以稍微修改以支持多个父节点，在这种情况下，在传输过程中，您将传输您正在获取的键的所有可能值，这可以通过递归或堆栈来完成，并且您将使用std::multimap来存储数据。