prueba | (Mostrar contenido)

Trie es una estructura de datos de recuperación de información eficiente. En nuestra publicación anterior sobre trie, hemos discutido sobre los conceptos básicos de trie y cómo insertar y buscar una clave en trie. En esta publicación, hablaremos sobre cómo mostrar todo el contenido de un trie. Es decir, mostrar todas las claves presentes en el Trie.
Ejemplos: 
 

Input: If Trie is      root
                    /   \    \
                    t   a     b
                    |   |     |
                    h   n     y
                    |   |  \  |
                    e   s  y  e
                 /  |   |
                 i  r   w
                 |  |   |
                 r  e   e
                        |
                        r
Output: Contents of Trie:
        answer
        any
        bye
        their
        there

La idea de hacer esto es comenzar a atravesar desde el Node raíz de trie, siempre que encontremos un Node secundario NO NULO, agregamos la clave principal del Node secundario en la «string str» en el índice actual (nivel) y luego llamamos recursivamente El mismo proceso para el Node secundario continúa hasta que encontramos el Node que es un Node hoja, que en realidad marca el final de la string. 
A continuación se muestra la implementación en C++ de la idea anterior: 
 

CPP

// CPP program to display content of Trie
#include <iostream>
#include <string.h>
#define alpha_size 26
#define ARRAY_SIZE(a) sizeof(a) / sizeof(a[0])
  
using namespace std;
  
// Trie node
struct TrieNode 
{
    struct TrieNode* children[alpha_size];
  
    bool isLeaf;
};
  
// Returns new trie node (initialized to NULLs)
struct TrieNode* createNode()
{
    struct TrieNode* pNode = new TrieNode;
  
    for (int i = 0; i < alpha_size; i++)
        pNode->children[i] = NULL;
  
    pNode->isLeaf = false;
  
    return pNode;
};
  
// function to insert a node in Trie
void insert_node(struct TrieNode* root, char* key)
{
    int level;
    int length = strlen(key);
    struct TrieNode* pCrawl = root;
  
    for (level = 0; level < length; level++) 
    {
        int index = key[level] - 'a';
  
        if (pCrawl->children[index] == NULL)
            pCrawl->children[index] = createNode();
  
        pCrawl = pCrawl->children[index];
    }
  
    pCrawl->isLeaf = true;
}
  
// function to check if current node is leaf node or not
bool isLeafNode(struct TrieNode* root)
{
    return root->isLeaf != false;
}
  
// function to display the content of Trie
void display(struct TrieNode* root, char str[], int level)
{
    // If node is leaf node, it indicates end
    // of string, so a null character is added
    // and string is displayed
    if (isLeafNode(root)) 
    {
        str[level] = '\0';
        cout << str << endl;
    }
  
    int i;
    for (i = 0; i < alpha_size; i++) 
    {
        // if NON NULL child is found
        // add parent key to str and
        // call the display function recursively
        // for child node
        if (root->children[i]) 
        {
            str[level] = i + 'a';
            display(root->children[i], str, level + 1);
        }
    }
}
  
// Driver program to test above functions
int main()
{
    // Keys to be inserted in Trie
    char keys[][8] = { "the", "a", "there", "answer",
                       "any", "by", "bye", "their" };
  
    struct TrieNode* root = createNode();
  
    // Inserting keys in Trie
    for (int j = 0; j < ARRAY_SIZE(keys); j++)
        insert_node(root, keys[j]);
  
    int level = 0;
    char str[20];
  
    // Displaying content of Trie
    cout << "Content of Trie: " << endl;
    display(root, str, level);
}

Python3

##Display words in a trie (recursive approach)
class TrieNode:
    def __init__(self):
        self.children=[None]*26
        self.isEndOfWord=False
          
class Trie:
    def __init__(self):
        self.root=self.getNode()
          
    def getNode(self):
        return TrieNode()
      
    def _charToIndex(self,ch):
        return ord(ch)-ord('a')
      
    def search(self,key):
        pCrawl=self.root
        length=len(key)
        for level in range(length):
            index=self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return False
            pCrawl=pCrawl.children[index]
              
        return pCrawl.isEndOfWord
      
    def insert(self,key):
        pCrawl=self.root
        length=len(key)
        for level in range(length):
            index=self._charToIndex(key[level])
            if not pCrawl.children[index]:
                pCrawl.children[index]=self.getNode()
                  
            pCrawl=pCrawl.children[index]
              
        pCrawl.isEndOfWord=True
          
    def delete(self,key):
        queue=[]
        pCrawl=self.root
        prev=self.root
        length=len(key)
        for level in range(length):
            index=self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return
            if pCrawl.isEndOfWord:
                queue.append([pCrawl,level])
                  
            pCrawl=pCrawl.children[index]
              
        if pCrawl.isEndOfWord == False:
            return
        ##If is a prefix of another tree, just change leaf
        flag=False
        for i in range(26):
            if pCrawl.children[index]:
                flag=True
        if flag:
            pCrawl.isEndOfWord==False
            return
        ##If not a prefix but a tree longer than others, delete until isEndOfWord == True again/reach root(a unique trie)
        if len(queue)==0:
            index=self._charToIndex(key[0])
            self.root.children[index]=None
            return
        pCrawl,level=queue.pop()
        index=self._charToIndex(key[level])
        pCrawl.children[index]=None
          
    def haschild(self,node):
        for i in range(26):
            if node.children[i]:
                return True
        return False
      
    def displayUtil(self,visited,node,str):
        index=0
        while index<26:
            if node.children[index]:
                str+=chr(97+index)
                #print(2,str)
                if node.children[index].isEndOfWord == False:
                    self.displayUtil(visited,node.children[index],str)
                    str=str[0 : (len(str)-1)]
                else:
                    if str not in visited:
                        visited.append(str)
                    if self.haschild(node.children[index]):
                        self.displayUtil(visited,node.children[index],str)
                        str=str[0 : (len(str)-1)]
                      
            index+=1
      
    def display(self):
        visited=[]
        str=''
        self.displayUtil(visited,self.root,str)
        print("Content of Trie:")
        for i in range(len(visited)):
            print(visited[i])
          
                        
keys = ["the","a","there","bye","any",
            "by","their","answer"]
output = ["Not present in trie","Present in trie"]
t=Trie()
for key in keys:
    t.insert(key)
  
t.display()
  
#This code is contributed by Zhaoxin Ban

Producción: 
 

Content of Trie:
a
answer
any
by
bye
the
their
there

NOTA: El algoritmo anterior muestra el contenido de Trie en orden clasificado lexicográficamente .
Algunas aplicaciones útiles de Trie son: 
 

Este artículo es una contribución de Yash Singla . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *