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

Answer 1

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;
}