How can I do a prefix tree?

Question

I need to do a prefix tree, that the user enter a word and the program display the prefix tree The output should be: String: Banana

a

na

ana

nana

anana

Banana

the output looks suspiciously like a suffix array (not a suffix tree). I think you need to expand on your question a little more, the code you have now appears to work just fine at generating the prefixes. I think you'll need to do some work in writing code to generate the suffixes. If you get stuck, you should share what you have so far. — nlloyd, Jul 01 '16 at 16:43
The program is a suffix array, but I wanna do a Prefix tree but I don't know how. — Vanezsitah MOontezs, Jul 01 '16 at 16:47
this [video](https://www.youtube.com/watch?v=VA9m_l6LpwI) shows you how to create a suffix tree conceptually. You then just have to convert that to code. Look up how to work with trees in java here: http://stackoverflow.com/questions/3522454/java-tree-data-structure — nlloyd, Jul 01 '16 at 16:52
Have you written any code yet? If so, please add it to your question. — Mario Tacke, Jul 01 '16 at 17:20
What you've listed as output isn't a prefix tree for Banana. Can you elaborate on what exactly it is that you're trying to do? — templatetypedef, Jul 01 '16 at 20:11

score 0 · Accepted Answer · answered Jul 01 '16 at 19:56

This is in C++

#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;
int primero;
struct nodo //Se crea el nodo
{
nodo* ptr[27]; //Las 26 ramas
int prinodo;
int ultimon;
nodo(int s,int e)
{
    for (int i = 0; i < 27; ++i)
    {
        ptr[i]=NULL;
    }
    prinodo=s;
    ultimon=e;
}
}*raiz=NULL;


nodo* fun(nodo* hijo,string str,int ind)
{
int s=hijo->prinodo; //Se van creando las ramas 
while(s<=hijo->ultimon&&str.at(s)==str.at(ind))
    {
        s++;
        ind++;
    }
if(s<=hijo->ultimon) //
{
    hijo->ptr[str.at(ind)-'a']=new nodo(ind,primero);
    if(str.at(s)=='$')
        hijo->ptr[26]=new nodo(s,hijo->ultimon);
    else
        hijo->ptr[str.at(s)-'a']=new nodo(s,hijo->ultimon);
    hijo->ultimon=s-1;
    return hijo;
}
else
{
    if(hijo->ptr[str.at(ind)-'a'])
    {
        hijo->ptr[str.at(ind)-'a']=fun(hijo->ptr[str.at(ind)-'a'],str,ind);
        return hijo;
    }
    else
    {
        hijo->ptr[str.at(ind)-'a']=new nodo(ind,primero);
        return hijo;
     }
    }

    }




nodo* crea(nodo* raiz,string str,int ind)
{
if(!raiz)
{
    raiz=new nodo(ind,primero);
    return raiz;
}
if(str.at(ind)=='$')
{
    raiz->ptr[26]=new nodo(ind,primero);
    return raiz;
}
if(!raiz->ptr[str.at(ind)-'a'])
{
    raiz->ptr[str.at(ind)-'a']=new nodo(ind,primero);
    return raiz;
}
raiz->ptr[str.at(ind)-'a']=fun(raiz->ptr[str.at(ind)-'a'],str,ind);
return raiz;
}



 void Imprime(nodo* raiz,string str)
  {
if(!raiz)
    return;
if(raiz->prinodo!=-1)
{
    for(int i=raiz->prinodo;i<=raiz->ultimon;i++)
    {
        cout<<str.at(i);
    }
    cout<<"\n";Imprime
}
for(int i=0;i<27;i++)
{
    Imprime(raiz->ptr[i],str);
}
}


int main(int argc, char const *argv[])
{
  std::cout << "Nombre del archivo: \n" ; // Pregunta el nombre del archivo a buscar la cadena
   std::string input ;
   std::getline( std::cin , input ) ;
   std::ifstream infile( input.c_str( ) , std::ios::in ) ;
   std::string file( input ) ;
   std::cout << "Inserte el número de linea de la cadena: " ; //Pregunta el nombre de la línea donde se buscará la cadena
   std::getline( std::cin , input ) ;
   int linenumber = std::stoi( input ) ;
   int lines_read = 0 ;
   std::string line ;
   if ( infile.is_open( ) ) {
      while ( infile ) {
     getline( infile , line ) ;
     lines_read++ ;
     if ( lines_read == linenumber ) {
        std::cout <<"Palabra: "<< line << std::endl ; //Imprime la palabra

                    primero=line.length()-1;
                line=line+"$";
                    raiz=new nodo(-1,-1);

                        for(int i=line.length()-1;i>=0;i--) //Hace la separación dela palabra e iprime los prefijosImprime
                        {
                            raiz=crea(raiz,line,i);
                            Imprime(raiz,line);
                            cout<<"";
                        }

          break;
         }
      }

   }


return 0;
}

How can I do a prefix tree?

1 Answers1