我正在寻找一种算法来解决一个问题，在该算法中，我维护一个树结构，我需要在该树结构上找到数据节点的最接近匹配项。如果没有完全匹配，则回退到最接近的前缀。
例如，如果说我有以下结构，其中单词(单词中的数字)是分支，方括号中的数字是数据(叶节点)；我正在寻找一种算法，该算法会返回如下表所示的结果集。请注意路径分隔符是 ">"
one - [1]
/\
two five
/\ \
eight [12] nine
/ \
[128] [159]
+---------------------------+--------+---------------------------------------------+
| path | result | |
+---------------------------+--------+---------------------------------------------+
| one > five > nine | 159 | whole path matches |
| one > five | 1 | partial (only "one" matched) |
| one > two > eight | 128 | whole path matches |
| one > two | 12 | whole path matches |
| one > two > eight > seven | 128 | partial (only "one > two > eight" matched) |
| one > two > seven | 12 | partial (only "one > two" matched) |
+---------------------------+--------+---------------------------------------------+
我非常喜欢基于 C++(STL 或 boost)的库；但仅仅为此目的指向一个漂亮的算法也同样好。
最佳答案
你正在寻找一个三元搜索树
关于c++ - 算法 - 具有最近路径前缀回退的查找树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19120928/