algorithm - 在后缀树中遍历

Question

我用java语言创建了一个后缀树。我们知道后缀树的应用之一是从树中搜索字符串。所以我的问题是，如何遍历后缀树的每个节点以查找后缀树中是否存在搜索字符串。

先感谢您。

Answer 1

你应该发布你的代码...

我假设这是一棵二叉树......继承人的伪代码

findString(RootNode,StringWeWant){
    if RootNode == StringWeWant{
     WERE DONE
    }
    else if RootNode < StringWeWant (string comparison){
     findString(RootNode.rightchild, StringWeWant)
    }
     else{
     findString(RootNode.leftchild,StringWeWant)
    }

}

如您所见，这是一个递归函数，您可以创建它最初测试根节点以查看它是否是我们要查找的字符串。如果根节点小于我们想要的字符串，我们要向右遍历。如果它大于，则向左遍历。我们可以调用相同的函数，但传入我们想要比较的新节点，直到找到我们想要的字符串。

希望能帮助到你。