Recorrido de abajo hacia arriba de un Trie

Trie es una estructura de datos de recuperación de información eficiente. Con Trie, las complejidades de búsqueda se pueden llevar a un límite óptimo (longitud de clave). 
Dado un intento. La tarea es imprimir los caracteres de forma ascendente.
Recorrido ascendente
 

Primero imprima la string del subárbol más a la izquierda (de abajo hacia arriba), luego imprima la string del segundo subárbol izquierdo (de abajo hacia arriba), luego imprima para el tercer subárbol izquierdo y así sucesivamente.

Es similar al recorrido posterior al pedido de un árbol
. Ejemplo: 
 

    
Input :
                                          root
                                         /    \    
                                         a     t     
                                         |     |     
                                         n     h     
                                         | \   |   
                                         s  y  e     
                                         |     |  \ 
                                         w     i   r
                                         |     |   |
                                         e     r   e
                                         |        
                                         r        
Output : r, e, w, s, y, n, a, r, i, e, r, e, h, t  

Input : 
                                           root
                                          /     \    
                                         c       t     
                                         |       |     
                                         a       h     
                                         | \     |     
                                         l  t    e     
                                         |       |  \ 
                                         l       i   r
                                         | \     |   |
                                         e  i    r   e
                                         |  |
                                         r  n
                                            |
                                            g 

Output : r, e, g, n, i, l, l, t, a, c, r, i, e, r, e, h, t

Explicación: 
en el primer ejemplo, la raíz tiene dos partes. La primera parte contiene strings: «respuesta» y «cualquiera». 
la segunda parte con strings «their» y «there». 
 

  • Ahora primero llegamos al subárbol izquierdo que contiene las strings «respuesta» y «cualquiera» que se separan por el carácter ‘n’. Ahora ‘n’ separa dos partes de los caracteres ‘s’, ‘w’, ‘e’, ​​’r’ e ‘y’. así que imprima ‘s’, ‘w’, ‘e’, ​​’r’ en orden inverso, luego imprima ‘y’ y suba e imprima ‘n’ (que separa la string), luego suba e imprima ‘a’. Ahora el primer subárbol izquierdo tiene impreso de abajo hacia arriba ‘r’, ‘e’, ​​’w’, ‘s’, ‘y’, ‘n’, ‘a’.
  • Haga lo mismo para otro subárbol de la raíz que contenga las strings «their» y «there» que están separadas por el carácter ‘e’.

Enfoque: 
la idea de hacer esto es comenzar a atravesar desde el Node raíz del trie, cada vez que encontramos un Node secundario NO NULO, avanzamos recursivamente cuando obtenemos «NULO», simplemente regresamos e imprimimos el valor del Node actual y Lo mismo ocurre 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 del enfoque anterior:
 

C++

// CPP program to traverse in bottom up manner
#include <bits/stdc++.h>
using namespace std;
#define CHILDREN 26
#define MAX 100
 
 
// Trie node
struct trie {
    trie* child[CHILDREN];
    // endOfWord is true if the node represents
    // end of a word
    bool endOfWord;
};
 
// Function will return the new node(initialized to NULLs)
trie* createNode()
{
    trie* temp = new trie();
    temp->endOfWord = false;
    for (int i = 0; i < CHILDREN; i++) {
        // Initialise all child to the null, initially
        temp->child[i] = NULL;
    }
     
    // Return newly created node
    return temp;
}
// Function will insert the string in a trie recursively
void insertRecursively(trie* itr, string str, int i)
{
    if (i < str.length()) {
        int index = str[i] - 'a';
        if (itr->child[index] == NULL) {
            // Assigning a newly created node
            itr->child[index] = createNode();
        }
        // Recursive call for insertion
        // of a string in a trie
        insertRecursively(itr->child[index], str, i + 1);
    }
    else {
        // Make the endOfWord true which represents
        // the end of string
        itr->endOfWord = true;
    }
}
// Function call to insert a string
void insert(trie* itr, string str)
{
    // Function call with necessary arguments
    insertRecursively(itr, str, 0);
}
// Function to print traverse
// the tree in bottom to top manner
void printPattern(trie* itr)
{
    // Base condition
    if (itr == NULL)
        return;
 
    // Loop for printing t a value of character
    for (int i = 0; i < CHILDREN; i++) {
         
        // Recursive call for print pattern
        printPattern(itr->child[i]);
        if (itr->child[i] != NULL) {
            char ch = (i + 97);
            cout << ch << ", "; // Print character
        }
    }
}
 
// Driver code
int main()
{
    trie* root = createNode();
     
    // Function to insert a string
    insert(root, "their");
    insert(root, "there");
    insert(root, "answer");
    insert(root, "any");
     
     
    // Function call for printing a pattern
    printPattern(root);
 
    return 0;
}

Java

// Java program to traverse in bottom up manner
public class Main
{
    static int CHILDREN = 26;
     
    // Trie node
    static class trie {
         
        public boolean endOfWord;
        public trie[] child;
         
        public trie()
        {
            endOfWord = false;
             
            // endOfWord is true if the node represents
            // end of a word
            child = new trie[CHILDREN];
        }
    }
     
    // Function will return the new node(initialized to NULLs)
    static trie createNode()
    {
        trie temp = new trie();
        temp.endOfWord = false;
        for (int i = 0; i < CHILDREN; i++)
        {
             
            // Initialise all child to the null, initially
            temp.child[i] = null;
        }
            
        // Return newly created node
        return temp;
    }
     
    // Function will insert the string in a trie recursively
    static void insertRecursively(trie itr, String str, int i)
    {
        if (i < str.length()) {
            int index = str.charAt(i) - 'a';
            if (itr.child[index] == null)
            {
                 
                // Assigning a newly created node
                itr.child[index] = createNode();
            }
             
            // Recursive call for insertion
            // of a string in a trie
            insertRecursively(itr.child[index], str, i + 1);
        }
        else
        {
             
            // Make the endOfWord true which represents
            // the end of string
            itr.endOfWord = true;
        }
    }
     
    // Function call to insert a string
    static void insert(trie itr, String str)
    {
         
        // Function call with necessary arguments
        insertRecursively(itr, str, 0);
    }
     
    // Function to print traverse
    // the tree in bottom to top manner
    static void printPattern(trie itr)
    {
         
        // Base condition
        if (itr == null)
            return;
        
        // Loop for printing t a value of character
        for (int i = 0; i < CHILDREN; i++) {
                
            // Recursive call for print pattern
            printPattern(itr.child[i]);
            if (itr.child[i] != null) {
                char ch = (char)(i + 97);
                System.out.print(ch + ", "); // Print character
            }
        }
    }
     
    public static void main(String[] args) {
        trie root = createNode();
        
        // Function to insert a string
        insert(root, "their");
        insert(root, "there");
        insert(root, "answer");
        insert(root, "any");
            
            
        // Function call for printing a pattern
        printPattern(root);
    }
}
 
// This code is contributed by divyesh072019.

Python3

# Python3 program to traverse in bottom up manner
CHILDREN = 26
MAX = 100
 
# Trie node
class trie:
 
    def __init__(self):
        self.child = [None for i in range(CHILDREN)]
         
        # endOfWord is true if the node represents
        # end of a word
        self.endOfWord = False
 
# Function will return the new node(initialized to NULLs)
def createNode():
 
    temp = trie()
    return temp
 
# Function will insert the string in a trie recursively
def insertRecursively(itr, str, i):
 
    if (i < len(str)):
        index = ord(str[i]) - ord('a')
         
        if (itr.child[index] == None):
           
            # Assigning a newly created node
            itr.child[index] = createNode()
         
        # Recursive call for insertion
        # of a string in a trie
        insertRecursively(itr.child[index], str, i + 1)
     
    else:
        # Make the endOfWord true which represents
        # the end of string
        itr.endOfWord = True
     
# Function call to insert a string
def insert(itr, str):
 
    # Function call with necessary arguments
    insertRecursively(itr, str, 0)
 
# Function to print traverse
# the tree in bottom to top manner
def printPattern(itr):
 
    # Base condition
    if(itr == None):
        return
 
    # Loop for printing t a value of character
    for i in range(CHILDREN):
 
        # Recursive call for print pattern
        printPattern(itr.child[i])
        if (itr.child[i] != None):
            ch = chr(i + 97)
             
            # Print character
            print(ch,end=', ')
             
# Driver code
if __name__=='__main__':
 
    root = createNode()
 
    # Function to insert a string
    insert(root, "their")
    insert(root, "there")
    insert(root, "answer")
    insert(root, "any")
 
    # Function call for printing a pattern
    printPattern(root)
 
    # This code is countributed by rutvik_56

C#

// C# program to traverse in bottom up manner
using System;
class GFG {
     
    static int CHILDREN = 26;
     
    // Trie node
    class trie {
        
        public bool endOfWord;
        public trie[] child;
        
        public trie()
        {
            endOfWord = false;
           
            // endOfWord is true if the node represents
            // end of a word
            child = new trie[CHILDREN];
        }
    }
      
    // Function will return the new node(initialized to NULLs)
    static trie createNode()
    {
        trie temp = new trie();
        temp.endOfWord = false;
        for (int i = 0; i < CHILDREN; i++)
        {
           
            // Initialise all child to the null, initially
            temp.child[i] = null;
        }
          
        // Return newly created node
        return temp;
    }
   
    // Function will insert the string in a trie recursively
    static void insertRecursively(trie itr, string str, int i)
    {
        if (i < str.Length) {
            int index = str[i] - 'a';
            if (itr.child[index] == null)
            {
               
                // Assigning a newly created node
                itr.child[index] = createNode();
            }
           
            // Recursive call for insertion
            // of a string in a trie
            insertRecursively(itr.child[index], str, i + 1);
        }
        else
        {
           
            // Make the endOfWord true which represents
            // the end of string
            itr.endOfWord = true;
        }
    }
   
    // Function call to insert a string
    static void insert(trie itr, string str)
    {
       
        // Function call with necessary arguments
        insertRecursively(itr, str, 0);
    }
   
    // Function to print traverse
    // the tree in bottom to top manner
    static void printPattern(trie itr)
    {
       
        // Base condition
        if (itr == null)
            return;
      
        // Loop for printing t a value of character
        for (int i = 0; i < CHILDREN; i++) {
              
            // Recursive call for print pattern
            printPattern(itr.child[i]);
            if (itr.child[i] != null) {
                char ch = (char)(i + 97);
                Console.Write(ch + ", "); // Print character
            }
        }
    }
 
  static void Main() {
    trie root = createNode();
      
    // Function to insert a string
    insert(root, "their");
    insert(root, "there");
    insert(root, "answer");
    insert(root, "any");
      
      
    // Function call for printing a pattern
    printPattern(root);
  }
}
 
// This code is contributed by mukesh07.

Javascript

<script>
    // Javascript program to traverse in bottom up manner
    let CHILDREN = 26;
     
    // Trie node
    class trie
    {
        constructor()
        {
         
           // endOfWord is true if the node represents
           // end of a word
           this.child = new Array(CHILDREN);
           this.endOfWord = false;
        }
    }
     
    // Function will return the new node(initialized to NULLs)
    function createNode()
    {
        let temp = new trie();
        temp.endOfWord = false;
        for (let i = 0; i < CHILDREN; i++)
        {
            
            // Initialise all child to the null, initially
            temp.child[i] = null;
        }
           
        // Return newly created node
        return temp;
    }
    
    // Function will insert the string in a trie recursively
    function insertRecursively(itr, str, i)
    {
        if (i < str.length) {
            let index = str[i].charCodeAt() - 'a'.charCodeAt();
            if (itr.child[index] == null)
            {
                
                // Assigning a newly created node
                itr.child[index] = createNode();
            }
            
            // Recursive call for insertion
            // of a string in a trie
            insertRecursively(itr.child[index], str, i + 1);
        }
        else
        {
            
            // Make the endOfWord true which represents
            // the end of string
            itr.endOfWord = true;
        }
    }
    
    // Function call to insert a string
    function insert(itr, str)
    {
        
        // Function call with necessary arguments
        insertRecursively(itr, str, 0);
    }
    
    // Function to print traverse
    // the tree in bottom to top manner
    function printPattern(itr)
    {
        
        // Base condition
        if (itr == null)
            return;
       
        // Loop for printing t a value of character
        for (let i = 0; i < CHILDREN; i++) {
               
            // Recursive call for print pattern
            printPattern(itr.child[i]);
            if (itr.child[i] != null) {
                let ch = String.fromCharCode(i + 97);
                document.write(ch + ", "); // Print character
            }
        }
    }
     
    let root = createNode();
       
    // Function to insert a string
    insert(root, "their");
    insert(root, "there");
    insert(root, "answer");
    insert(root, "any");
       
       
    // Function call for printing a pattern
    printPattern(root);
     
    // This code is contributed by suresh07.
</script>

Producción: 
 

 r, e, w, s, y, n, a, e, r, e, r, e, i, h, t,

Publicación traducida automáticamente

Artículo escrito por MohammadMudassir 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 *