遍歷一個trie以獲取所有單詞

Question

我已經編寫了Perl代碼，實際上創建了一個給定數組中的一組單詞的數據結構。現在我遇到了遍歷和打印文字的問題。

也粘貼創建的數據結構的Dumper輸出。

遍歷後的最後一組單詞似乎並不正確，因爲遍歷邏輯肯定缺少某些東西。但是，創建好並且工作得很快。有人可以幫我嗎？

的特里結構的頂層是一個哈希

1. 每個散列條目有一個鍵是一種 字母和每個散列指向一個 數組引用。

2. 陣列裁判又包含散列的 列表以及每個哈希產品 同1

如果你看到在輸出中的第一個字。它出現爲archtopriumwe。

我們應該得到弧，拱，頂上，中庭，敬畏

CODE

 
use Data::Dumper; 
my %mainhash; 

## Subroutine 
sub storeword { 
    my $type = shift; 
    my $fc = shift; 
    my $word = shift; 
    return if ((not defined $word) or (length($word) == 0));  
    my @letters = split (//,$word); 
    my $len = scalar(@letters) - 1; 
    my ($arr_ref,$pass_ref,$flag ,$i,$hashitem,$newitem); 
    $pass_ref = $hashitem = $new_item = undef; 
    $arr_ref = $type; 
    $setstop = 1 if (length($word) == 1); 
    $flag =0; 
    for($i = 0;$i {$letters[0]}) { 
      $flag =1; 
      $pass_ref = $hashitem->{$letters[0]}; 
      last; 
     } 
    } 
    if ($flag == 0) { 
     $newitem->{$letters[0]} = []; 
     push(@$arr_ref,$newitem); 
     $pass_ref = $newitem->{$letters[0]}; 
    } 

    storeword($pass_ref,$letters[0],join ('',@letters[ 1..$len])); 
} 

## Subroutine 
sub process { 
    my ($prefix,$trie) = @_; 
    for my $letter (sort keys %$trie) { 
     if (@{ $trie->{$letter} }) { 
      for my $branch (@{ $trie->{$letter} }) { 
       process("$prefix$letter", $branch); 
      } 
     } 
     else { 
      print "$prefix$letter\n"; 
     } 
    } 
} 

##main 

##list of words 
my @wd = qw (arc atop awe blob boil fame tub arch atrium); 

##inserting each word into the datastructure 
foreach my $w (@wd) { 
    my @letters = split (//,$w); 
    my $len = scalar(@letters) - 1; 
    if (not exists $mainhash{$letters[0]}) { 
     $mainhash{$letters[0]} = []; 
    } 
    storeword($mainhash{$letters[0]},$letters[0],join ('',@letters[ 1..$len])); 
} 
    print Dumper(%mainhash); 
     ## Trying to print each word from trie. 
    print("\n List of words\n");  
    process('',\%mainhash); 

輸出：

 
$VAR1 = 'a'; 
$VAR2 = [ 
      { 
      'r' => [ 
        { 
         'c' => [ 
           { 
            'h' => [] 
           } 
           ] 
        } 
        ] 
      }, 
      { 
      't' => [ 
        { 
         'o' => [ 
           { 
            'p' => [] 
           } 
           ] 
        }, 
        { 
         'r' => [ 
           { 
            'i' => [ 
              { 
              'u' => [ 
                 { 
                 'm' => [] 
                 } 
                ] 
              } 
             ] 
           } 
           ] 
        } 
        ] 
      }, 
      { 
      'w' => [ 
        { 
         'e' => [] 
        } 
        ] 
      } 
     ]; 
$VAR3 = 'b'; 
$VAR4 = [ 
      { 
      'l' => [ 
        { 
         'o' => [ 
           { 
            'b' => [] 
           } 
           ] 
        } 
        ] 
      }, 
      { 
      'o' => [ 
        { 
         'i' => [ 
           { 
            'l' => [] 
           } 
           ] 
        } 
        ] 
      } 
     ]; 
$VAR5 = 'f'; 
$VAR6 = [ 
      { 
      'a' => [ 
        { 
         'm' => [ 
           { 
            'e' => [] 
           } 
           ] 
        } 
        ] 
      } 
     ]; 
$VAR7 = 't'; 
$VAR8 = [ 
      { 
      'u' => [ 
        { 
         'b' => [] 
        } 
        ] 
      } 
     ]; 

List of words 
archtopriumwe 
bloboil 
fame 
tub 

Answer 1

你看到你的代碼是隻打印一次數據結構中的每個字母，而不是一次每個字它在？並且只爲樹中的每個頂級字母打印一次換行符，而不是每個單詞一個？

爲了解決這個問題，你需要傳遞更多的上下文到你的遞歸子。事情是這樣的：

sub process { 
    my ($prefix, $trie) = @_; 
    for my $letter (sort keys %$trie) { 
     if (@{ $trie->{$letter} }) { 
      for my $branch (@{ $trie->{$letter} }) { 
       process("$prefix$letter", $branch); 
      } 
     } 
     else { 
      print "$prefix$letter\n"; 
     } 
    } 
} 

print("\n List of words\n"); 
process('', \%mainhash); 

這不打印的弧線，因爲你沒有提供的方式在你的數據結構告訴弧是一個字，但如boi不是。每個字母的值需要提供兩件事：一個布爾指示符，這是一個單詞的結尾，以及可能的後續字母及其子樹的列表。