In the breadth-first traversal example, it looks like the resulting linked list is completely static. By that I mean that you could pre-compute the traversal order and store it into the linked list of 'p' pointers. Then you can traverse as many times as you want just by following the pointers. In fact, as long as you aren't editing the tree, these traversals should even be reentrant and thread-safe.
I feel like you could do the same sort of thing with depth-first search, or any other scan order really: Do one "expensive" (ie, allocating) traversal to build a linked list, then lots of (comparatively) cheap linked-list-following. Or you could even build the linked list along with the trie, and update both when you add/remove elements (if that's much rarer than traversals). For the latter you'd probably want to use a doubly-linked-list so you don't have to do another search to find the "previous" element.
If you are able to allocate extra memory, or can structure the memory layout appropriately, it might even make sense to (re-)pack the trie nodes in traversal order in memory, so that the memory accesses during a traversal are nice and linear. Again, depends a lot on how you're using the trie and what your constraints are.