How to move tree leaf nodes horizontally after automatic positioning?

Question

I'd like to draw trees like the following:

desired tree display http://quicklatex.com/cache3/ql_c0f6b5397c19caf09ce70d6e47841eb7_l3.png

That is, I have edges which are crossing. The tree should be drawn like a regular tree (without crossings) except at the last level where the leaves can be in any horizontal order. The number of nodes etc. is arbitrary, the image is just an example.

The only thing I know about the tree is (a) its structure, that is, nodes and their children, and (b) an ordering number (=x position) for each leaf which determines where the leaves should be displayed horizontally to form the crossings. In the example above, I would know a1 is at position 0, b1 at 1, a2 at 2, and b2 at 3. I can use these numbers when I draw a specific leaf.

The code must represent the structure of the tree, like that:

\documentclass[a4paper]{scrartcl}
\usepackage{tikz}
\usepackage{tikz-qtree}
\begin{document}
\begin{tikzpicture}
\tikzset{frontier/.style={distance from root=70pt}}
  \Tree [.Z [.\node{A};
                \node{a1};
                \node{a2}; ]
              [.\node{B};
                \node{b1};
                \node{b2}; ] ]
\end{tikzpicture}
\end{document}

which produces:

non-crossing tree display http://quicklatex.com/cache3/ql_4217cf1d35018cf2016b55ac580d6085_l3.png

Ideally, now I'd like to reorder the leaves based on their ordering numbers that I know:

  \Tree [.Z [.\node{A};
                \node at (0,0) {a1};
                \node at (2,0) {a2}; ]
              [.\node{B};
                \node at (1,0) {b1};
                \node at (3,0) {b2}; ] ]

The problem is that this becomes:

wrong tree http://quicklatex.com/cache3/ql_8b543330e2e251476b91100f13dcca4a_l3.png

Question: How can the repositioning of the leaves be achieved without loosing the automatic tree layout functionality of tikz-qtree?

Some background: These are derivation trees generated recursively by so-called multiple context-free grammars which can model languages like a^i b^j a^i b^j. I appended numbers to the terminals to make it more explicit where they end up when reordered.

Answer 1

Do you want something like this?

Note that I'm not at all sure I understand what you are trying to do.

In your comments on Gonzalo Medina's answer, you say you know that 'a' must end up in position 0 and 2, and 'b' in position 1 and 3, say. But it isn't clear how you expect this to be automated. (How can TeX tell the difference between 1 'a' and another? There is no input word 'abab' in your example code, so this information doesn't seem to be provided in any form.)

forest allows you to create 'dynamic' trees i.e. you can move stuff around at various stages. Here, I shift the nodes after the layout of the tree is computed but before it is drawn:

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest}

\begin{document}
  \begin{forest}
    for tree={
      parent anchor=south,
      child anchor=north,
      where n children=0{
        s sep=1.5em,
        inner xsep=0pt
      }{},
    }
    [Z
      [A
        [a1
        ]
        [a2, before drawing tree={x+=1.5em}
        ]
      ]
      [B
        [b1, before drawing tree={x-=1.5em}
        ]
        [b2
        ]
      ]
    ]
  \end{forest}
\end{document}

EDIT

The OP edited the question to demonstrate a solution based on my answer above and discussion in comments. However, that solution required manually specifying the total number of leaf nodes. I think that the following should avoid this requirement. The idea is to increment a LaTeX counter for each leaf node and then use the final value of this counter to adjust the position of the node before the tree is drawn. A new style, leaf position is defined which takes one argument which should be the position of the node in the ordered sequence i.e. leaf position=2 if the leaf should end up in the third (number 2) slot.

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest}
\usepackage{calc}

\begin{document}

\begingroup

\newcounter{leafnodes}
\setcounter{leafnodes}{0}
\forestset{
  leaf position/.style={
    before drawing tree={
      where n children=0{
        x/.pgfmath={(#1-(.5*\theleafnodes)+.5)*1.5em}
      }{},
    }
  },
}
\begin{forest}
  for tree={
    parent anchor=south,
    child anchor=north,
    where n children=0{
      s sep=1.5em,
      inner xsep=0pt,
      delay={TeX={\stepcounter{leafnodes}}},
    }{},
  },
  [Z
    [A
      [a1, leaf position=0
      ]
      [a2, leaf position=2
      ]
    ]
    [B
      [b1, leaf position=1
      ]
      [b2, leaf position=3
      ]
    ]
  ]
\end{forest}
\endgroup

\end{document}

EDIT EDIT

In response to the discussion in comments, here's an example which puts all of the leaf nodes on the same level, using tier=leaves, and which sets the height of these nodes to a standard size so that the edges drawn from the parents do not terminate at different heights. I've also moved the leftmost node a bit left since it looked a bit odd with a larger tree. Obviously this could be adjusted further if desired.

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest}
\usepackage{calc}

\begin{document}

\begingroup

\newcounter{leafnodes}
\setcounter{leafnodes}{0}
\forestset{
  leaf position/.style={
    before drawing tree={
      where n children=0{
        x/.pgfmath={(#1-(.5*\theleafnodes))*1.5em}
      }{},
    }
  },
}
\begin{forest}
  for tree={
    parent anchor=south,
    child anchor=north,
    where n children=0{
      s sep=1.5em,
      inner xsep=0pt,
      tier=leaves,
      text height=5pt,
      delay={TeX={\stepcounter{leafnodes}}},
    }{},
  },
  [Z
    [A
      [A
        [A
          [T, leaf position=6
          ]
          [y, leaf position=1
          ]
          [e, leaf position=0
          ]
        ]
        [a, leaf position=5
        ]
        [a, leaf position=4
        ]
      ]
      [a1, leaf position=8
      ]
      [a2, leaf position=2
      ]
    ]
    [B
      [b1, leaf position=7
      ]
      [b2, leaf position=3
      ]
    ]
  ]
\end{forest}
\endgroup

\end{document}

Answer 2

If you're willing to switch to the powerful forest package, this can be easily done:

\documentclass[a4paper]{scrartcl}
\usepackage{forest}

\begin{document}

\begin{forest}
for tree={
  parent anchor=south,
  child anchor=north,
  l sep=0.75cm
}
[Z,s sep=-40pt
  [A,calign=fixed edge angles,calign primary angle=-30,calign secondary angle=60
    [a1]
    [a2]
  ]
  [B,calign=fixed edge angles,calign primary angle=-60,calign secondary angle=30
    [b1]
    [b2]
  ]
]
\end{forest}

\end{document}

Answer 3

Derived from cfr's original answer and comments:

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest}
\usepackage{calc}

\begin{document}

\begingroup

\def\f{1.5em} % scale
\def\n{4} % number of leaves

\def\xleaf#1{\f*(#1-\n/2+0.5)} % calculates x of a leaf
\begin{forest}
  for tree={
    parent anchor=south,
    child anchor=north,
    where n children=0{
      s sep=1.5em,
      inner xsep=0pt
    }{},
  }
  [Z
    [A
      [a1, before drawing tree={x=\xleaf{0}}
      ]
      [a2, before drawing tree={x=\xleaf{2}}
      ]
    ]
    [B
      [b1, before drawing tree={x=\xleaf{1}}
      ]
      [b2, before drawing tree={x=\xleaf{3}}
      ]
    ]
  ]
\end{forest}
\endgroup

\end{document}

I guess this is as far as it gets. A shame that it needs the total number of leaves though but I guess it's too complicated to derive that automatically from the tree and then use it inside the before drawing tree expressions.

Note: cfr's updated answer can count leaves now!