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