# [pst-tree] Special nodes for binary trees

Denis Girou Denis.Girou at idris.fr
Sun May 30 23:37:32 CEST 1999

-----------------------------------------------------------------------------
This is the PSTricks mailing list, devoted to discussions about computational
graphics in (La)TeX using the PSTricks package from Timothy van Zandt.
For help using this mailing list, see instructions at the end of message.
-----------------------------------------------------------------------------

Some months ago, Peter Bartke <bartke at inf.fu-berlin.de> ask me a question
concerning some binary trees to show algebric expression analysis. It is easy
to understand with his following example:

\documentclass[12pt]{article}

\usepackage{pst-tree}

\pagestyle{empty}

\newcommand{\tribox}[4]{%
\multips(1,0){3}{\psframe[dimen=middle](1,1)}
\rput(0.5,0.5){\dotnode*{#1}}
\rput(1.5,0.5){#2}\pnode(1.5,1){#4}
\rput(2.5,0.5){\dotnode*{#3}}}

\begin{document}

\psset{unit=0.5}

\begin{pspicture}(6,5)
\rput(4.5,5){\rnode{p}{}}
\rput(3,3){\tribox{a}{$*$}{b}{c}}
\rput(1,1){\tribox{d}{$+$}{e}{f}}
\rput(0,0){\rnode[nodesep=3pt]{s}{$1$}}
\rput(5,0){\rnode[nodesep=3pt]{t}{$2$}}
\rput(7,2){\rnode[nodesep=3pt]{u}{$3$}}
\ncline{p}{c}
\ncline{a}{f}
\ncline{b}{u}
\ncline{d}{s}
\ncline{e}{t}
\end{pspicture}

\end{document}

We obviously see that this has a clear binary tree structure, with special
nodes of boxes with three parts. All the difficulty come from the positions
in the nodes where the connections must be attached.

This is a specially interested question, as the structure of the tree is
clear and the need real. But as far as I know it doesn't exist such example
and, even if the result is simple, it is not so easy to found the good way
to change the position of the nodes, as it must be done dynamically. I take
time to look for a solution when Peter Bartke ask me the question some months
ago, but I must say that I didn't succeed to found one (only some
approximative one, which give a correct result only for very simple cases...).

But as I found the problem interesting, and a solution for it probably
possible to extend to other situations, I look at it again these last days.
In fact, as I primarily guessed, the solution is easy, and just require to
change conveniently and at the right moment the positions of the nodes.

\documentclass[12pt]{article}

\usepackage{pst-tree}

\SpecialCoor

\newcommand{\TriBox}[1]{%
\begin{pspicture}(3,1)
\psgrid[subgriddiv=0,gridlabels=0](3,1)
\dotnode*[dotscale=1.5](0.5,0.5){L-\pspred-\the\psnodecnt}
\rput(1.5,0.5){$#1$}
\dotnode*[dotscale=1.5](2.5,0.5){R-\pspred-\the\psnodecnt}
\end{pspicture}}

% A tree node, with three boxes
\newcommand{\TriBoxNode}[1]{{%
\psset{nodesepB=0}
\TrX{\TriBox{#1}}
\pnode(L-\pspred-\the\psnodecnt){\pssucc}}}

% A \Tr macro, updating the position of the node above
\newcommand{\TrX}[1]{%
\Tr[ref=t]{#1}
\pnode(R-\pspred){\pspred}}

\pagestyle{empty}

\begin{document}

\psset{unit=0.5,treesep=4,levelsep=2,nodesepB=0.2}

\pstree{\TriBoxNode{*}}
{\TrX{1}
\TrX{2}}
\hfill
\pstree{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\TrX{1}
\TrX{2}}
\TrX{3}}
\hfill
\pstree{\TriBoxNode{*}}
{\TrX{1}
\pstree{\TriBoxNode{+}}
{\TrX{2}
\TrX{3}}}

\hspace{3cm}
\pstree{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\pstree{\TriBoxNode{/}}
{\TrX{1}
\TrX{2}}
\TrX{3}}
\TrX{4}}

\pstree[levelsep=1]
{\Tr{}}
{\pstree[levelsep=2]
{\TriBoxNode{*}}
{\TrX{1}
\pstree{\TriBoxNode{+}}
{\TrX{2}
\TrX{3}}}}
\hfill
\pstree[levelsep=1]
{\Tr{}}
{\pstree[levelsep=2]
{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\TrX{1}
\TrX{2}}
\TrX{3}}}

\pstree[levelsep=1]
{\Tr{}}
{\pstree[levelsep=2]
{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\TrX{1}
\TrX{2}}
\pstree{\TriBoxNode{-}}
{\TrX{3}
\TrX{4}}}}

\pstree[levelsep=1]
{\Tr{}}
{\pstree[levelsep=2]
{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\TrX{1}
\pstree{\TriBoxNode{-}}
{\TrX{2}
\TrX{3}}}
\pstree{\TriBoxNode{-}}
{\pstree{\TriBoxNode{/}}
{\TrX{4}
\TrX{5}}
\TrX{6}}}}

\end{document}

D.G.

-----------------------------------------------------------------------------