Unfortunately, I haven't really seen a valid system for such trees. Not many people plan to have a leaf coming off of more than one branch, but I do understand how this could be helpful. Therefore, I'd leave you with four possible solutions:
Build your own tree module that will do what you need it to do. (One idea I've always loved, and use in my own home-spun tree algorithms is the idea of a sort key, which can tell all the parents of a single id, and could possible allow for two parents. A sort key looks like (root_id,branch_id,parent_id,leaf_id), assuming one has a root, a branch a sub-branch, and a leaf. You could then hack into that allow for (root_id,branch_id,[parent_id|other_parent_id],leaf_id), and parse into that with a split, and a regex. This would be helpful if you want to get the history of a leaf, but developing this into a full-scale tree module would take some time.
Duplicate the leafs, and use DBIx::Tree (This means that you'd leave all the same information, except for the id, and parent id.) Unfortunately, it also means that you'll have to duplicate children of that parent.
Develop your own tree algorithm, or edit DBIx::Tree to allow for two sets of parents. (This actually wouldn't be too hard.) I would suggest this solution, or the next one. My advice would be to allow DBIx::Tree to search for an or clause in your parent_id, and then have that clause build to both parents. Unfortunately you'd have to change the algorithm a little further to allow for sub-leaves to be built in both places. I'll leave that as an exercise for your mind :)
Look some more for a cpan solution, because I don't know it :)