10

I'm drawing some binary search trees using pstricks and pstree, but I don't see anything in the docs to push a node to one side. In a binary search tree, every child must be either right or left, but if there's only one child then pstree will hang it straight down.

   *
  / \
 *   *
/ \  |

should be

   *
  / \
 *   *
/ \   \

3 Answers 3

5

Putting a nil node is not tricky but rather good maths. Adding manually some space would be ugly.

In pstree you manipulate (ordered) n-ary trees so there is no notion of left or right child node. You can only give a list of child nodes (ordered).

Think of how you will implement binary trees (t := () | (t, t)) with ordered n-ary trees (t := list of trees). The two following binary trees are different.

  *          *
 /     !=     \
*              *

While they are equal as n-ary trees. You need to explicitly encode the skip of the left child node to simulate that in n-ary trees.

The pstree creators proposed you a distinguished \Tn node (nil node) for that purpose.

\pstree{\TR{a}}{
  \Tn
  \TR{b}
}

Just like when a missing information is an information.

5

use \Tn for a "null node" ...

\documentclass{article}
\usepackage{pst-tree}
\begin{document}

\pstree[levelsep=25pt]{\Tcircle{10}}{
    \pstree{\Tcircle{1}}{
        \Tn
        \pstree{\Tcircle{5}}{\Tcircle{4}{\Tn}}
    }
    \pstree{\Tcircle{16}}{
        \Tn
        \pstree{\Tcircle{17}}{
            \Tn
            \Tcircle{21}
        }
    }
}

\end{document}

enter image description here

3

I resorted to inserting invisible nodes ({\psset{linestyle=none}\TR{}}) into the tree, which pushes the other node towards one side. It worked for what I needed, but is a bit hackish and behaves like an invisble node, not as a well-defined offset to one side. (For example, in the rendered image, it would be a hassle to shift that 4 further right where it should be.)

\pstree[levelsep=25pt]{\Tcircle{10}}
{
    \pstree{\Tcircle{1}}
    {
        {\psset{linestyle=none}\TR{}}
        \pstree{\Tcircle{5}}
        {
            \Tcircle{4}
            {\psset{linestyle=none}\TR{}}
        }
    }
    \pstree{\Tcircle{16}}
    {
        {\psset{linestyle=none}\TR{}}
        \pstree{\Tcircle{17}}
        {
            {\psset{linestyle=none}\TR{}}
            \Tcircle{21}
        }
    }
}

Gives

  10
 /      1    16
 \            5     17
 /            4          21

BST using pstricks and pstree

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .