[pst-tree] Special nodes for binary trees
Denis Girou
Denis.Girou at idris.fr
Tue Jun 1 21:50:50 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.
-----------------------------------------------------------------------------
>>>>> "D.G." == Denis Girou <Denis.Girou at idris.fr> writes:
D.G.> Some months ago, Peter Bartke <bartke at inf.fu-berlin.de> ask me a question
D.G.> concerning some binary trees to show algebric expression analysis. It is easy
D.G.> to understand with his following example:
D.G.> ...
D.G.> But as I found the problem interesting, and a solution for it probably
D.G.> possible to extend to other situations, I look at it again these last days.
D.G.> In fact, as I primarily guessed, the solution is easy, and just require to
D.G.> change conveniently and at the right moment the positions of the nodes.
I receive some questions asking for explanations on the code I sent on
Sunday evening, to draw these special kinds of trees. It is true that for
people using trees, this is interesting to understand. So, I'll try to give
some detailed comments.
First, I make minor modifications in the code I sent on Sunday. This is
exactly similar, but a little cleaner. I modify the node redefinition in
\TriBoxNode using the fact that \pssucc is at this time the same than
\pspred-\the\psnodecnt. And I also implement the predecessor node redefinition
for each node (take care that we manage here binary trees only) as a hook in
\end@@treenode. The advantage is that we have not any more to use a special
node (the \TrX I used before), but we can use for instance a normal \Tr one.
Some comments on this code:
* Each node has a name contained in the \pssucc macro. It has the form
T-n1-n2-...-nk where "ni" are integers, and the names are unique for each
node. "nk" is given by the \pnodecnt counter, which vary from 0 to the number
of nodes of the level. And "k" is the number of predecessor levels above the
node, including it.
* The \pspred macro contain the predecessor node for the relevant one.
* After a node is drawn, the connection is drawn between itself and it
predecessor, using the \psedge macro (see beta documentation, page 41).
* So, for the kind of trees we have:
+ We define a non terminal node as a picture of three small boxes.
+ It name will be in \pssucc, as usual.
+ We also define two additional nodes. One named
L-\pspred-\the\psnodecnt is in the center of the left small box, and one named
R-\pspred-\the\psnodecnt is in the center of the right one.
+ \pspred-\the\psnodecnt will be the content of the name of this node
(contained in \pssucc, _when the node will have been drawn_).
+ After drawing the node (the line \Tr{\TriBox{#1}} in the
\TriBoxNode macro), we change it position (as node), redefining \pssucc has
L-\pssucc. So, later, the connection between it and it first son will not
start at the center of the tribox, but in the center of the left one.
+ After drawing a node and it connection, we redefine the position of
the predecessor node, using the hook \PsTreeNodeAfterHook, which redefine
\pspred as R-\pspred. So, we move the node of the predecessor from the left
small box to the right one, for it later right subtree management (before to
do it, many other subtrees are possibly to be managed).
I also give a modified version of this code, to print the definitions of the
nodes inside the boxes. It must clarify how it work.
Interested people could also look at the third code, and verify that they
understand this technic... It is another example, using the same principle,
this time to draw some simple linked or double linked lists. The advantage of
building them as trees is that the connections can be automatized.
D.G.
..............................................................................
\documentclass[12pt]{article}
\usepackage{pst-tree}
\makeatletter
\def\end@@treenode{%
\pstree at bboxadjust
\gdef\pstree at bboxadjust{}%
\ifpsshowbbox\pstree at showbbox\fi
\pstree at node
\endgroup
\ifnum\pstreelevel>\z@
\pstree at edge{\pspred}{\pssucc}%
\expandafter\pst at shortput
\else
\expandafter\ignorespaces
\fi
% D.G. modification begin - May. 31, 1999
\PsTreeNodeAfterHook}
% D.G. modification end
\def\PsTreeNodeAfterHook{}
\makeatother
\SpecialCoor
\newcommand{\TriBox}[1]{%
% \pspred-\the\psnodecnt will be \pssucc when the node will be drawn
\begin{pspicture}(3,1)
\psgrid[subgriddiv=0,gridlabels=0](3,1)
\dotnode*[dotscale=1.5](0.5,0.5){L-\pspred-\the\psnodecnt}
\rput[c](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}
\Tr{\TriBox{#1}}
\pnode(L-\pssucc){\pssucc}}}
\pagestyle{empty}
\begin{document}
\renewcommand{\PsTreeNodeAfterHook}{\pnode(R-\pspred){\pspred}}
\psset{unit=0.5,treesep=4,levelsep=2,nodesepB=0.2,ref=t}
\pstree{\TriBoxNode{*}}
{\Tr{1}
\Tr{2}}
\hfill
\pstree{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\Tr{1}
\Tr{2}}
\Tr{3}}
\hfill
\pstree{\TriBoxNode{*}}
{\Tr{1}
\pstree{\TriBoxNode{+}}
{\Tr{2}
\Tr{3}}}
\hspace{3cm}
\pstree{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\pstree{\TriBoxNode{/}}
{\Tr{1}
\Tr{2}}
\Tr{3}}
\Tr{4}}
\pstree[thislevelsep=1]
{\Tr{}}
{\pstree{\TriBoxNode{*}}
{\Tr{1}
\pstree{\TriBoxNode{+}}
{\Tr{2}
\Tr{3}}}}
\hfill
\pstree[thislevelsep=1]
{\Tr{}}
{\pstree{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\Tr{1}
\Tr{2}}
\Tr{3}}}
\pstree[thislevelsep=1]
{\Tr{}}
{\pstree{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\Tr{1}
\Tr{2}}
\pstree{\TriBoxNode{-}}
{\Tr{3}
\Tr{4}}}}
\pstree[thislevelsep=1]
{\Tr{}}
{\pstree{\TriBoxNode{*}}
{\pstree{\TriBoxNode{+}}
{\Tr{1}
\pstree{\TriBoxNode{-}}
{\Tr{2}
\Tr{3}}}
\pstree{\TriBoxNode{-}}
{\pstree{\TriBoxNode{/}}
{\Tr{4}
\Tr{5}}
\Tr{6}}}}
\end{document}
..............................................................................
\documentclass[12pt,a4paper]{article}
\usepackage{pst-tree}
\usepackage{lscape}
\usepackage[width=21cm,height=29.7cm]{geometry}
\makeatletter
\def\end@@treenode{%
\pstree at bboxadjust
\gdef\pstree at bboxadjust{}%
\ifpsshowbbox\pstree at showbbox\fi
\pstree at node
\endgroup
\ifnum\pstreelevel>\z@
\pstree at edge{\pspred}{\pssucc}%
\expandafter\pst at shortput
\else
\expandafter\ignorespaces
\fi
% D.G. modification begin - May. 31, 1999
\PsTreeNodeAfterHook}
% D.G. modification end
\def\PsTreeNodeAfterHook{}
\makeatother
\SpecialCoor
\newcommand{\TriBox}{%
\begin{pspicture}(7,2)
\psframe(2,2)
\rput[c](1,1.5){\scriptsize\texttt{L-\pspred-\the\psnodecnt}}
\dotnode*[dotscale=3](1,1){L-\pspred-\the\psnodecnt}
\psframe(2,0)(5,2)
\rput[c](3.5,1){%
\setlength{\tabcolsep}{0.5mm}
\scriptsize
\begin{tabular}{lll}
\textbackslash\texttt{pspred} &:& \texttt{\pspred}\\
% \pssucc will be updated later
\textbackslash\texttt{pssucc} &:& \texttt{\pspred-\the\psnodecnt}\\
\textbackslash\texttt{pnodecnt} &:& \texttt{\the\psnodecnt}
\end{tabular}}
\psframe(5,0)(7,2)
\rput[c](6,1.5){\scriptsize\texttt{R-\pspred-\the\psnodecnt}}
\dotnode*[dotscale=3](6,1){R-\pspred-\the\psnodecnt}
\end{pspicture}}
% A tree node, with three boxes
\newcommand{\TriBoxNode}{%
\Tr{\TriBox}
\pnode(L-\pssucc){\pssucc}}
\pagestyle{empty}
\begin{document}
\renewcommand{\PsTreeNodeAfterHook}{\pnode(R-\pspred){\pspred}}
\psset{dimen=middle,treesep=0.5,levelsep=3,ref=t}
\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}
\vspace{1cm}
\pstree{\TriBoxNode}
{\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}
\TriBoxNode}
\vspace{1cm}
\pstree{\TriBoxNode}
{\TriBoxNode
\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}}
\pstree[thislevelsep=1]
{\Tr{}}
{\pstree{\TriBoxNode}
{\TriBoxNode
\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}}}
\vspace{1cm}
\pstree[thislevelsep=1]
{\Tr{}}
{\pstree{\TriBoxNode}
{\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}
\TriBoxNode}}
\begin{landscape}
\pstree{\TriBoxNode}
{\pstree{\TriBoxNode}
{\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}
\TriBoxNode}
\TriBoxNode}
\end{landscape}
\begin{landscape}
\scaleboxto(27,0){%
\pstree[thislevelsep=1]
{\Tr{}}
{\pstree{\TriBoxNode}
{\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}
\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}}}
}
\end{landscape}
\begin{landscape}
\scaleboxto(27,9){%
\pstree[thislevelsep=1]
{\Tr{}}
{\pstree{\TriBoxNode}
{\pstree{\TriBoxNode}
{\TriBoxNode
\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}}
\pstree{\TriBoxNode}
{\pstree{\TriBoxNode}
{\TriBoxNode
\TriBoxNode}
\TriBoxNode}}}
}
\end{landscape}
\end{document}
..............................................................................
\documentclass[12pt]{article}
\usepackage{pst-tree}
\makeatletter
\def\end@@treenode{%
\pstree at bboxadjust
\gdef\pstree at bboxadjust{}%
\ifpsshowbbox\pstree at showbbox\fi
\pstree at node
\endgroup
\ifnum\pstreelevel>\z@
\pstree at edge{\pspred}{\pssucc}%
\expandafter\pst at shortput
\else
\expandafter\ignorespaces
\fi
% D.G. modification begin - May. 31, 1999
\PsTreeNodeAfterHook}
% D.G. modification end
\def\PsTreeNodeAfterHook{}
\makeatother
\SpecialCoor
\newcommand{\LinkedList}[1]{%
\begin{pspicture}(2,1)
\psgrid[subgriddiv=0,gridlabels=0](2,1)
\rput(0.5,0.5){\LARGE $#1$}
% \pspred-\the\psnodecnt will be \pssucc when the node will be drawn
\pnode(1.5,0.5){R-\pspred-\the\psnodecnt}
\end{pspicture}}
\newcommand{\DoubleLinkedList}[1]{%
\begin{pspicture}(3,1)
\psgrid[subgriddiv=0,gridlabels=0](3,1)
\rput(0.5,0.5){\LARGE $#1$}
% \pspred-\the\psnodecnt will be \pssucc when the node will be drawn
\pnode(1.5,0.5){L1-\pspred-\the\psnodecnt}
\pnode(1.75,0){L2-\pspred-\the\psnodecnt}
\pnode(2.5,0.5){R-\pspred-\the\psnodecnt}
\end{pspicture}}
% Tree node for linked or double linked list
\newcommand{\LinkedListNode}[1]{\Tr{\LinkedList{#1}}}
\newcommand{\DoubleLinkedListNode}[1]{\Tr{\DoubleLinkedList{#1}}}
\setlength{\parindent}{0cm}
\pagestyle{empty}
\begin{document}
\renewcommand{\PsTreeNodeAfterHook}{\pnode(R-\pspred){\pspred}}
\psset{treemode=R,treesep=4,arrows=->,arrowscale=2}
\pstree[levelsep=3]
{\LinkedListNode{c_4}}
{\pstree{\LinkedListNode{c_3}}
{\pstree{\LinkedListNode{c_2}}
{\LinkedListNode{c_1}}}}
\vspace{2cm}
\makeatletter
\renewcommand{\PsTreeNodeAfterHook}{%
\pnode(R-\pssucc){\pssucc}
\edef\@tempa{T}%
\if\pspred\@tempa
\else
\pcbar[angle=-90,armB=0.75,linecolor=red](L1-\pssucc)(L2-\pspred)
\fi}
\makeatother
\pstree[levelsep=4]
{\DoubleLinkedListNode{c_4}}
{\pstree{\DoubleLinkedListNode{c_3}}
{\pstree{\DoubleLinkedListNode{c_2}}
{\DoubleLinkedListNode{c_1}}}}
\end{document}
-----------------------------------------------------------------------------
The list interface (subscription, information, access to the archives) is on:
http://www.tug.org/cgi-bin/lwgate/pstricks
Otherway to unsubscribe, send mail to pstricks-request at mail.tug.org
with a blank subject and in body the line unsubscribe <email-address>
-----------------------------------------------------------------------------
More information about the PSTricks
mailing list