Permuting a binary tree without the use of lists
- by Banang
I need to find an algorithm for generating every possible permutation of a binary tree, and need to do so without using lists (this is because the tree itself carries semantics and restraints that cannot be translated into lists). I've found an algorithm that works for trees with the height of three or less, but whenever I get to greater hights, I loose one set of possible permutations per height added.
Each node carries information about its original state, so that one node can determine if all possible permutations have been tried for that node. Also, the node carries information on weather or not it's been 'swapped', i.e. if it has seen all possible permutations of it's subtree. The tree is left-centered, meaning that the right node should always (except in some cases that I don't need to cover for this algorithm) be a leaf node, while the left node is always either a leaf or a branch.
The algorithm I'm using at the moment can be described sort of like this:
if the left child node has been swapped
swap my right node with the left child nodes right node
set the left child node as 'unswapped'
if the current node is back to its original state
swap my right node with the lowest left nodes' right node
swap the lowest left nodes two childnodes
set my left node as 'unswapped'
set my left chilnode to use this as it's original state
set this node as swapped
return null
return this;
else if the left child has not been swapped
if the result of trying to permute left child is null
return the permutation of this node
else
return the permutation of the left child node
if this node has a left node and a right node that are both leaves
swap them
set this node to be 'swapped'
The desired behaviour of the algoritm would be something like this:
branch
/ |
branch 3
/ |
branch 2
/ |
0 1
branch
/ |
branch 3
/ |
branch 2
/ |
1 0 <-- first swap
branch
/ |
branch 3
/ |
branch 1 <-- second swap
/ |
2 0
branch
/ |
branch 3
/ |
branch 1
/ |
0 2 <-- third swap
branch
/ |
branch 3
/ |
branch 0 <-- fourth swap
/ |
1 2
and so on...
Sorry for the ridiculisly long and waddly explanation, would really, really apreciate any sort of help you guys could offer me.
Thanks a bunch!
