我有一个存储字符串的二叉搜索树。字符串按字典顺序进行比较（使用 c 中的 strcmp）。
给定一些输入字符串，我想检索存储在 BST 中的该字符串的所有前缀的列表。例如，如果我的 BST 包含“a”、“ab”和“abc”，则在给定输入字符串“abcd”的情况下，此类搜索应返回这三个字符串的列表（详细信息：如果 BST 包含字符串本身，它被视为前缀）。
天真的方法是测试 BST 是否一一包含字符串的每个前缀（对于“hello”，搜索“h”、“he”、“hel”，...），但我想一种更有效的方法，可以避免多次遍历同一节点。
你会怎么做？我已经思考这个问题有一段时间了，但似乎永远无法弄清楚。
谢谢！
使用 BST 属性，您可以找到输入字符串的最小前缀（如果有），并将其路径保留在内存中。从那里您可以访问 inorder successor 节点（使用路径），直到遇到不是前缀的字符串。然后你就会找到它们了。