type
  PTRInode = ^TRInode;
  TRInode  = record
    prefend : Boolean;
    triref  : array[0..25] of PTRInode;
    Data: typ_danych;
  end;

struct TRInode
{
  bool prefend;
  TRInode * triref[26];
  typ_danych data;
};

Type TRInode
  prefend As Boolean
  triref(0 To 25) As TRInode Ptr
  data As typ_danych
End Type

// Drzewo TRIE
// Data: 30.10.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------

program trie;

// Węzeł Trie  
type
  PTRInode = ^TRInode;
  TRInode  = record
    prefend : Boolean;
    triref  : array[0..25] of PTRInode;
  end;

// Inicjuje węzeł Trie
//--------------------
procedure tri_init(p : PTRInode);
var
  i : integer;

begin
  p^.prefend := false;
  for i := 0 to 25 do
    p^.triref[i] := nil;
end;

// Sprawdza, czy węzeł jest pusty
// r - wskazanie węzła
// Wynik:
// true - węzeł jest pusty
// false - węzeł nie jest pusty
//-------------------------------
function tri_empty(r : PTRInode)
                     : boolean;
var
  i : integer;

begin
  for i := 0 to 25 do
    if r^.triref[i] <> nil then
      exit(false);
  tri_empty := true;
end;

// Wstawia klucz k do drzewa r
// r - korzeń drzewa
// k - klucz
// Zwraca ostatni węzeł klucza
//----------------------------
function tri_insert(r : PTRInode;
                    k : string)
                      : PTRInode;
var
  p : PTRInode;
  i, c : integer;

begin
  p := r;
  for i := 1 to length(k) do
  begin
    c := ord(k[i])-65;
    if p^.triref[c] = nil then
    begin
      new(p^.triref[c]);
      tri_init(p^.triref[c]);
    end;
    p := p^.triref[c];
  end;
  p^.prefend := true;
  tri_insert := p
end;

// Wyszukuje klucz k w drzewie r
// r - korzeń
// k - szukany klucz
// Zwraca ostatni węzeł klucza lub nil
//------------------------------------
function tri_find(r : PTRInode;
                  k : string)
                    : PTRInode;
var
  p : PTRInode;
  i,c : integer;

begin
  p := r;
  for i := 1 to length(k) do
  begin
    c := ord(k[i])-65;
    if p^.triref[c] = nil then exit(nil);
    p := p^.triref[c];
  end;
  if p^.prefend = false then exit(nil);
  tri_find := p;
end;

// Usuwa klucz z drzewa r
// r - wskazanie korzenia
// k - usuwany klucz
// d - pozycja znaku usuwanego klucza.
// Zwraca wskazanie węzła
//------------------------------------
function tri_delete(r : PTRInode;
                    k : string;
                    d : integer)
                      : PTRInode;
var
  c : integer;

begin
  if r = nil then exit(nil);
  if d = length(k)+1 then
  begin
    r^.prefend := false;
    if tri_empty(r) = true then
    begin
      dispose(r);
      exit(nil);
    end;
    exit(r);
  end;
  c := ord(k[d])-65;
  r^.triref[c] :=
    tri_delete(r^.triref[c],k,d+1);
  if (tri_empty(r) = true) and
     (r^.prefend = false) then
  begin
    dispose(r);
    exit(nil);
  end;
  exit(r);
end;

// Przechodzi przez drzewo TRIE
// r - korzeń
// k - klucz
//-----------------------------
procedure tri_traverse(r : PTRInode;
                       k : string);
var
  i : integer;

begin
  if r = nil then exit();
  if r^.prefend = true then
    writeln(k);
  for i := 0 to 25 do
    tri_traverse(r^.triref[i],k+chr(i+65));
end;

// Usuwa drzewo TRIE
// r - korzeń
//------------------
procedure tri_remove(r : PTRInode);
var
  i : integer;

begin
  if r <> nil then
    for i := 0 to 25 do
    begin
      if r^.triref[i] = nil then continue;
      if tri_empty(r^.triref[i]) = false then
        tri_remove(r^.triref[i]);
      dispose(r^.triref[i]);
      r^.triref[i] := nil;
    end;
end;

// Program główny
//---------------

var
  // Klucze
 keys : array[0..15] of string =
    ('ALGA', 'ALGORYTM',
     'ALT', 'ARGON',
     'BRAMA', 'BRAWO',
     'KOMAR','KOC',
     'KOCZKODAN','LAWETA',
     'LAWA','LEN',
     'MORZE','MORA',
     'MAT','MATA');

  i,j  : integer;
  root : PTRInode;

begin
  randomize();

  // Tworzymy puste drzewo TRIE
  new(root);
  tri_init(root);

  // W drzewie umieszczamy 10 losowych kluczy
  writeln('DODAJEMY:');
  for i := 1 to 10 do
  begin
    j := random(16);
    writeln(keys[j]);
    tri_insert(root,keys[j])
  end;
  writeln;
  writeln('DRZEWO TRIE:');
  tri_traverse(root,'');
  writeln;

  // Szukamy 10 losowych kluczy
  for i := 1 to 10 do
  begin
    j := random(16);
    write('KLUCZ ',keys[j],' ');
    if tri_find(root,keys[j]) = nil then
      write('NIE');
    writeln('OBECNY');
  end;
  writeln;

  // Usuwamy 8 losowych kluczy
  writeln('USUWAMY:');
  for i := 1 to 8 do
  begin
    j := random(16);
    writeln(keys[j]);
    root := tri_delete(root,keys[j],1);
  end;
  writeln;
  writeln('DRZEWO TRIE:');
  tri_traverse(root,'');
  writeln;

  // Usuwamy drzewo
  tri_remove(root);
  dispose(root);
end.

// Drzewo TRIE
// Data: 30.10.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Węzeł Trie
struct TRInode
{
  bool prefend;
  TRInode * triref[26];
};

// Inicjuje węzeł Trie
//--------------------
void tri_init(TRInode * p)
{
  int i;

  p->prefend = false;
  for(i = 0; i < 26; i++)
    p->triref[i] = nullptr;
}

// Sprawdza, czy węzeł jest pusty
// r - wskazanie węzła
// Wynik:
// true - węzeł jest pusty
// false - węzeł nie jest pusty
//-------------------------------
bool tri_empty(TRInode * r)
{
  int i;

  for(i = 0; i < 26; i++)
    if(r->triref[i]) return false;
  return true;
}

// Wstawia klucz k do drzewa r
// r - korzeń drzewa
// k - klucz
// Zwraca ostatni węzeł klucza
//----------------------------
TRInode * tri_insert(TRInode * r,
                     string k)
{
  TRInode * p;
  int i, c;

  p = r;
  for(i = 0; i < (int) k.length(); i++)
  {
    c = k[i]-65;
    if(!p->triref[c])
    {
      p->triref[c] = new(TRInode);
      tri_init(p->triref[c]);
    }
    p = p->triref[c];
  }
  p->prefend = true;
  return p;
}

// Wyszukuje klucz k w drzewie r
// r - korzeń
// k - szukany klucz
// Zwraca ostatni węzeł klucza lub nil
//------------------------------------
TRInode * tri_find(TRInode * r,
                   string k)
{
  TRInode * p;
  int i, c;

  p = r;
  for(i = 0; i < (int)k.length(); i++)
  {
    c = k[i]-65;
    if(!p->triref[c]) return nullptr;
    p = p->triref[c];
  }
  if(!p->prefend) return nullptr;
  return p;
}

// Usuwa klucz z drzewa r
// r - wskazanie korzenia
// k - usuwany klucz
// d - pozycja znaku usuwanego klucza.
// Zwraca wskazanie węzła
//------------------------------------
TRInode * tri_delete(TRInode * r,
                     string k,
                     int d)
{
  int c;

  if(!r) return nullptr;
  if(d == (int)k.length())
  {
    r->prefend = false;
    if(tri_empty(r))
    {
      delete r;
      return nullptr;
    }
    return r;
  }
  c = k[d]-65;
  r->triref[c] =
    tri_delete(r->triref[c],k,d+1);
  if(tri_empty(r) && !r->prefend)
  {
    delete r;
    return nullptr;
  }
  return r;
}

// Przechodzi przez drzewo TRIE
// r - korzeń
// k - klucz
//-----------------------------
void tri_traverse(TRInode * r,
                  string k)
{
  int i;

  if(!r) return;
  if(r->prefend)
    cout << k << endl;
  for(i = 0; i < 26; i++)
    tri_traverse(r->triref[i],k+char(i+65));
}

// Usuwa drzewo TRIE
// r - korzeń
//------------------
void tri_remove(TRInode * r)
{
  int i;

  if(r)
    for(i = 0; i < 26; i++)
    {
      if(!r->triref[i]) continue;
      if(!tri_empty(r->triref[i]))
        tri_remove(r->triref[i]);
      delete r->triref[i];
      r->triref[i] = nullptr;
    }
}

// Program główny
//---------------
main()
{

  // Klucze
  string keys[16] =
    {"ALGA","ALGORYTM",
     "ALT", "ARGON",
     "BRAMA","BRAWO",
     "KOMAR","KOC",
     "KOCZKODAN","LAWETA",
     "LAWA","LEN",
     "MORZE","MORA",
     "MAT","MATA"};
  int i,j;
  TRInode * root;

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Tworzymy puste drzewo TRIE
  root = new(TRInode);
  tri_init(root);

  // W drzewie umieszczamy 10 losowych kluczy
  cout << "DODAJEMY:" << endl;
  for(i = 0; i < 10; i++)
  {
    j = rand() % 16;
    cout << keys[j] << endl;
    tri_insert(root,keys[j]);
  }
  cout << endl
       << "DRZEWO TRIE:" << endl;
  tri_traverse(root,"");
  cout << endl;

  // Szukamy 10 losowych kluczy
  for(i = 0; i < 10; i++)
  {
    j = rand() % 16;
    cout << "KLUCZ " << keys[j] << " ";
    if(!tri_find(root,keys[j]))
      cout << "NIE";
    cout << "OBECNY" << endl;
  }

  // Usuwamy 8 losowych kluczy
  cout << endl
       << "USUWAMY:" << endl;
  for(i = 0; i < 8; i++)
  {
    j = rand() % 16;
    cout << keys[j] << endl;
    root = tri_delete(root,keys[j],0);
  }
  cout << endl
       << "DRZEWO TRIE:" << endl;
  tri_traverse(root,"");
  cout << endl;
  // Usuwamy drzewo
  tri_remove(root);
  delete root;
}

' Drzewo TRIE
' Data: 30.10.2024
' (C)2024 mgr Jerzy Wałaszek
'---------------------------

' Węzeł Trie
Type TRInode
  prefend As Boolean
  triref(0 To 25) As TRInode Ptr
End Type

' Inicjuje węzeł Trie
'--------------------
Sub tri_init(ByVal p As TRInode Ptr)
  Dim i As Integer

  p->prefend = False
  For i = 0 To 25
    p->triref(i) = 0
  Next
End Sub

' Sprawdza, czy węzeł jest pusty
' r - wskazanie węzła
' Wynik:
' true - węzeł jest pusty
' false - węzeł nie jest pusty
'-------------------------------
Function tri_empty(ByVal r As TRInode Ptr) _
                           As Boolean
  Dim i As Integer
  
  For i = 0 To 25
    If r->triref(i) <> 0 Then Return False
  Next
  Return True
End Function

' Wstawia klucz k do drzewa r
' r - korzeń drzewa
' k - klucz
' Zwraca ostatni węzeł klucza
'----------------------------
Function tri_insert(ByVal r As TRInode Ptr,_
                    ByVal k As String) _
                            As TRInode Ptr
  Dim p As TRInode Ptr
  Dim As Integer i, c

  p = r
  For i = 0 To Len(k) - 1
    c = k[i] - 65
    If p->triref(c) = 0 Then
      p->triref(c) = New TRInode
      tri_init(p->triref(c))
    End If
    p = p->triref(c)
  Next
  p->prefend = True
  Return p
End Function

' Wyszukuje klucz k w drzewie r
' r - korzeń
' k - szukany klucz
' Zwraca ostatni węzeł klucza lub 0
'----------------------------------
Function tri_find(ByVal r As TRInode Ptr, _
                  ByVal k As String) _
                          As Trinode Ptr
  Dim p As TRInode Ptr
  Dim As Integer i, c

  p = r
  For i = 0 To Len(k) - 1
    c = k[i] - 65
    If p->triref(c) = 0 Then Return 0
    p = p->triref(c)
  Next
  If p->prefend = False Then Return 0
  Return p
End Function

' Usuwa klucz z drzewa r
' r - wskazanie korzenia
' k - usuwany klucz
' d - pozycja znaku usuwanego klucza.
' Zwraca wskazanie węzła
'------------------------------------
Function tri_delete(ByVal r As TRInode Ptr, _
                    ByVal k As String, _
                    ByVal d As Integer) _
                            As TRInode Ptr
  Dim c As Integer

  If r = 0 Then Return 0
  If d = Len(k) Then
    r->prefend = False
    If tri_empty(r) = True Then
      Delete r
      Return 0
    End If
    Return r
  End If
  c = k[d] - 65
  r->triref(c) = _
    tri_delete(r->triref(c),k,d + 1)
  If (tri_empty(r) = True) AndAlso _
     (r->prefend = False) Then
    Delete r
    Return 0
  End If
  Return r
End Function

' Przechodzi przez drzewo TRIE
' r - korzeń
' k - klucz
'-----------------------------
Sub tri_traverse(ByVal r as TRInode Ptr, _
                 ByVal k As String)
  Dim i As Integer

  If r = 0 Then Return
  If r->prefend = True Then _
    Print k
  For i = 0 To 25
    tri_traverse(r->triref(i),k+chr(i+65))
  Next
End Sub

' Usuwa drzewo TRIE
' r - korzeń
'------------------
Sub tri_remove(ByVal r As TRInode Ptr)
  Dim i As Integer

  If r <> 0 Then 
    For i = 0 To 25
      If r->triref(i) = 0 Then Continue For
      If tri_empty(r->triref(i)) = False Then _
        tri_remove(r->triref(i))
      Delete r->triref(i)
      r->triref(i) = 0
    Next
  End If
End Sub  

' Program główny
'---------------

' Klucze
Dim As String keys(15) = _
    {"ALGA","ALGORYTM",_
     "ALT", "ARGON",_
     "BRAMA","BRAWO",_
     "KOMAR","KOC",_
     "KOCZKODAN","LAWETA",_
     "LAWA","LEN",_
     "MORZE","MORA",_
     "MAT","MATA"}
Dim As Integer i,j
Dim root As TRInode Ptr

' Inicjujemy generator pseudolosowy
Randomize

' Tworzymy puste drzewo TRIE
root = new TRInode
tri_init root

' W drzewie umieszczamy 10 losowych kluczy
Print "DODAJEMY:"
For i = 1 To 10
  j = Int(Rnd * 16)
  Print keys(j)
  tri_insert root,keys(j)
Next
Print
Print "DRZEWO TRIE:"
tri_traverse root,""
Print

' Szukamy 10 losowych kluczy
For i = 1 To 10
  j = Int(Rnd * 16)
  Print "KLUCZ "; keys(j);" ";
  If tri_find(root,keys(j)) = 0 Then _
    Print "NIE";
  Print "OBECNY"
Next  
Print

' Usuwamy 8 losowych kluczy
Print "USUWAMY:"
For i = 1 To 8
  j = Int(Rnd * 16)
  Print keys(j)
  root = tri_delete(root,keys(j),0)
Next
Print
Print "DRZEWO TRIE:"
tri_traverse root,""
Print

' Usuwamy drzewo
tri_remove root
Delete root
End

# Drzewo TRIE
# Data: 30.10.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

# węzeł TRI
class TRInode:
    def __init__(self):
        self.prefend = False
        self.triref  = [None] * 26


# Sprawdza, czy węzeł jest pusty
# r - wskazanie węzła
# Wynik:
# true - węzeł jest pusty
# false - węzeł nie jest pusty
#-------------------------------
def tri_empty(r):
    for i in range(26):
        if r.triref[i]:
            return False
    return True


# Wstawia klucz k do drzewa r
# r - korzeń drzewa
# k - klucz
# Zwraca ostatni węzeł klucza
def tri_insert(r, k):
    p = r
    for i in range(len(k)):
        c = ord(k[i]) - 65
        if not p.triref[c]:
            p.triref[c] = TRInode()
        p = p.triref[c]
    p.prefend = True
    return p


# Wyszukuje klucz k w drzewie r
# r - korzeń
# k - szukany klucz
# Zwraca ostatni węzeł klucza lub 0
def tri_find(r, k):
    p = r
    for i in range(len(k)):
        c = ord(k[i]) - 65
        if not p.triref[c]:
            return None
        p = p.triref[c]
    if not p.prefend:
        return None
    return p


# Usuwa klucz z drzewa r
# r - wskazanie korzenia
# k - usuwany klucz
# d - pozycja znaku usuwanego klucza.
# Zwraca wskazanie węzła
def tri_delete(r, k, d):
    if not r: return None
    if d == len(k):
        r.prefend = False
        if tri_empty(r):
            del r
            r = None
        return r
    c = ord(k[d]) - 65
    r.triref[c] = tri_delete(r.triref[c],k,d+1)
    if tri_empty(r) and not r.prefend:
        del r
        r = None
    return r


# Przechodzi przez drzewo TRIE
# r - korzeń
# k - klucz
def tri_traverse(r, k):
    if not r: return
    if r.prefend: print(k)
    for i in range(26):
        tri_traverse(r.triref[i],k+chr(i+65))


# Usuwa drzewo TRIE
# r - korzeń
def tri_remove(r):
    if r:
        for i in range(26):
            if not r.triref[i]: continue
            if not tri_empty(r.triref[i]):
                tri_remove(r.triref[i])
            r.triref[i] = None


# Program główny
#---------------

# Klucze
keys = ["ALGA","ALGORYTM",
        "ALT", "ARGON",
        "BRAMA","BRAWO",
        "KOMAR","KOC",
        "KOCZKODAN","LAWETA",
        "LAWA","LEN",
        "MORZE","MORA",
        "MAT","MATA"]
root = TRInode()

# W drzewie umieszczamy 10 losowych kluczy
print("DODAJEMY:")
for i in range(10):
    j = random.randrange(16)
    print(keys[j])
    tri_insert(root, keys[j])
print()
print("DRZEWO TRIE:")
tri_traverse(root, "")
print()
# Szukamy 10 losowych kluczy
for i in range(10):
    j = random.randrange(16)
    print("KLUCZ", keys[j], end=" ")
    if not tri_find(root,keys[j]):
        print("NIE", end="")
    print("OBECNY")
print()
print("USUWAMY:")
for i in range(8):
    j = random.randrange(16)
    print(keys[j])
    root = tri_delete(root, keys[j],0)
print()
print("DRZEWO TRIE:")
tri_traverse(root, "")
print()
tri_remove(root)
del root