Perform a depth-first traversal, retaining the path's letters in a buffer. A terminal node must be printed before its children, so a word precedes its proper extensions in lexicographic order.The recursion invariant is that
VAR word: ARRAY N OF CHAR;
PROCEDURE Visit(t: Trie; depth: INTEGER);
VAR j, c: INTEGER;
BEGIN
IF t # NIL THEN
IF t.terminal THEN
j := 0;
WHILE j < depth DO
Out.Char(word[j]); j := j+1
END;
Out.Ln
END;
c := 0;
WHILE c < 26 DO
IF t.child[c] # NIL THEN
word[depth] := CHR(ORD("a")+c);
Visit(t.child[c], depth+1)
END;
c := c+1
END
END
END Visit;
PROCEDURE PrintTrie(t: Trie);
BEGIN
Visit(t, 0)
END PrintTrie;word[0..depth) spells the path to t. The child loop's loop invariant says children with indices below c have been completely printed. Each edge appends its lowercase label; each terminal flag prints exactly one represented string. All words therefore appear once, in lowercase. The output loop prints precisely the prefix of length depth; no terminating zero needs storing in this buffer.An
N-character buffer suffices for words of length at most N. At depth N there can be no child, so word[N] is never accessed. A terminal root prints an empty line; a NIL root prints nothing. The running time is linear in allocated nodes plus the number of printed characters, since the alphabet size is fixed at 26. Articles by others on the same topic
There are currently no matching articles.