[eftdxehm] Pre plus post order tree traversal

1. Say the node name.
2. Recursively process its children left to right.
3. Say the node name again.

There will be matching pairs of nodes names.  HTML syntax is like this, as is SystemVerilog.

Let's only consider complete binary trees, because nodes will have large, in fact, maximal (among binary trees), distances between the start and end tag.

Assign the letters of a string to the nodes of a complete binary tree.  Preorder is probably best, though inorder and breadth-first are also good alternatives.  Read off according to pre-plus-post-order above.  This defines a string transformation.

string

s
t		n
r	i	g

Here are various ways of writing a pre and post order tree traversal:

1. <s><t><r/><i/></t><n><g/><0/></n></s>
2. s t r! i! /t n g! 0 /n /s
3. strriitngg.ns
4. strriitnggns

The last version only works because we have constrained ourselves to complete binary trees, so if a node has only one child, it must be a left child.

There will be ambiguity in parsing if a letter occurs in the original string more than once: where is its pair?  This ambiguity be resolved quickly if length of the whole string is known, because we know the structure of the complete binary tree.

Not sure what this could be useful for.  The original motivation was to define a string transformation in which a local change in the input string results in a large, nonlocal change in the output, but cryptographic hashing is much better for this.