I'm not entirely sure of what you're asking for, but I think it might be one of these three:

**Permutations that preserve topological structure**  
The tree you listed in parenthetical notation is (5 (2 (1 4) ) (3) (5 (6 (7 (8) ) ) ). Are you looking for permutations of this tree structure, because you can simply calculate all n! permutations of nodes and put them in the same tree structure:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )  
(9 (8 (7 6) ) (5) (4 (3 (1 (2) ) ) )  
(9 (8 (7 6) ) (5) (4 (1 (2 (3) ) ) )  
(9 (8 (7 6) ) (5) (4 (1 (3 (2) ) ) )  
...  
(This would yield 362,880 distinct trees).  

Note, this class of trees would preserve the sequences of lengths of the current tree. Now, if you have an array of these, simply use a good PRNG.

**Permutations that calculate topological isomorphisms**  
It also would preserve topological properties, so if you want to generate other isomorphic topologies, then you can take the structure of the tree and do permutations on the sequences at the same level. Hence:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )  
(9 (8 (7 6) ) (4 (3 (2 (1) ) ) (5) )  
(9 (5) (8 (7 6) ) (4 (3 (2 (1) ) ) )  
(9 (5) (4 (3 (2 (1) ) ) (8 (7 6) ) )  
...  
(This will be a variable number of permutations, in this case (3!(1!)(2!)(1!)) or 12 trees.)  

**Permutations that calculate equivalent lengths**

Let your tree be [1 2[1 4] 3 4 *5[2 3 6] 6[7] 7[8] 8] where * represents root, and nodes inside of brackets are pointers. Notice it's possible to calculate lengths by taking the absolute value of the difference between nodes (2[4]->2[[2]] The node two which points to [node four] is a node that has an [[edge length 2]]). Then use [1 2[[1 2]] 3 4 *5[[3 2 1]] 6[[1]] 7[[1]] 8 9] -> {1, 1, 1, 1, 2, 3}. Now we can simply replicate this by traversing the original tree and constructing isomorphisms of length. Hence:

1. Determine root  
Rnd(1-9)->3 -> [1 2 *3 4 5 6 7 8]  
2. Permute first level by taking three lengths and finding candidates  
[1 2 *3[[3 2 1]] 4 5 6 7 8 9]->  (note three lengths)  
[3]±[[3]]->{0,6} (0 is invalid so don't push on the stack)  
[3]±[[2]]->{1,5}  
[3]±[[1]]->{2,4}  
Note we need to select P(2,1) on all three sets iteratively.   
So, randomly, one permutation is {6,1,4} :[1[] 2 *3[1 4 6] 4 5 6 7 8].  
3. Call this recursively on [1], [4], [6] over the set {with [[1], [[1]], and [[1 2]] with the base case being any tree that satisfies {1, 1, 1, 1, 2, 3}.

Now, I think that preserving the lengths as a function of order of the sequence might yield a very small set, because certain trees, might only have a single isomorphism. Consider:

(1 (2 (3 (4 (5 (6 (7 (8)))))))) ~ (8 (7 (6 (5 (4 (3 (2 (1))))))))

There's only one isomophism because of the way a tree when considering edges whose lengths are caculated from sequences partitions. In fact, every tree done in this manner might have at most 1, but I'd have to think about how to prove that after implementing code.

Let me know what you think; if you can clarify what you're seeking, I might be able to help.