c++ - C++ 中的后缀 Trie

Question

我一直在尝试编写后缀 trie 的 C++ 代码，但是我希望此代码跟踪每个节点的计数器，以了解在后缀 trie 构造期间字符或子字符串出现的频率:记住正在使用只有 4 个字符 A、C、G 和 T

下面的代码是我的尝试，但它不能正常工作:

#include<iostream>
#include <string>
#include <stdio.h>
#include <string.h>
using namespace std;

struct SuffixTreeNode{
    char c;
    struct SuffixTreeNode* one;
    struct SuffixTreeNode* two;
    struct SuffixTreeNode* three;
    struct SuffixTreeNode* four;
    //int count;

};

SuffixTreeNode* CreateNode(char ch){
    SuffixTreeNode* newnode=new SuffixTreeNode();
    newnode->c=ch;
    newnode->one=NULL;
    newnode->two=NULL;
    newnode->three=NULL;
    newnode->four=NULL;
    //count=0;
}   

SuffixTreeNode* Insert(SuffixTreeNode* root,char ch){
    if (root==NULL){
        root=CreateNode(ch);
    }
    else if(ch=='a'){
        root->one=Insert(root->one,ch);
    }
    else if(ch=='c'){
        root->two=Insert(root->two,ch);
    }
    else if(ch=='g'){
        root->three=Insert(root->three,ch);
    }
    else if(ch=='t') {
        root->four=Insert(root->four,ch);
    }

    return root;
}

bool Search(SuffixTreeNode* root, int data){
    if(root==NULL) return false;
    else if (root->c==data) return true;
    else if (root->c=='a')return Search(root->one,data);
    else if (root->c=='c')return Search(root->two,data);
    else if (root->c=='g')return Search(root->three,data);
    else return Search(root->four,data);
}

int main(){
    SuffixTreeNode* root=NULL;
    char str;
    root=Insert(root,'a');
    root=Insert(root,'c');
    root=Insert(root,'c');
    root=Insert(root,'t');
    root=Insert(root,'a');
    root=Insert(root,'g');
    cout<<"Enter character to be searched\n";
    cin>>str;

    if(Search(root,str)==true)cout<<"Found\n";
    else cout<<"Not found\n";
}

Answer 1

问题是它的设计对于搜索和插入是有缺陷的:你这样做是为了单个字符，而 trie应该使用字符串。

问题分析

如果你打印出 trie，你会看到你构建了一棵树，扩展了与字母对应的分支。你这样做是因为你一次插入一个字母，但这不是 trie 的正常布局:

同样，当你搜索一个元素时，如果它是根元素，一切就OK了。但如果它不是根元素，你的代码将始终搜索与当前节点对应的分支，并且这是递归的，这意味着它只会在与根对应的分支中搜索。

解决方案的第一步:更正代码

如果你想在 trie 结构中找到任何字母，你需要更新你的搜索来探索不是与当前节点的字母对应的分支，而是到被搜索的字母:

bool Search(SuffixTreeNode* root, int data){
    cout << (char)data<<"=="<<root->c<<"?"<<endl; 
    if(!root) return false;
    else if (root->c==data) return true;
    else if (data=='a')return Search(root->one,data);
    else if (data=='c')return Search(root->two,data);
    else if (data=='g')return Search(root->three,data);
    else return Search(root->four,data);
}

这更正了代码，而不是底层设计。这里是online demo here .

但还需要进一步的工作来纠正设计

设计应该插入/搜索字符串s。这个想法是用 s[0] 检查当前字符并递归地插入/搜索字符串的剩余部分 s.substr(1);