Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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

   *
  / \
 *   *
/ \   \
share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.