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 have some prefix expressions which are too long to feasibly create my own binary trees by hand. I was wondering if there was a latex package which could parse my expressions and automatically create a binary tree?

Take for example a smaller expression;

* - J % J 2 + 2 1

I want a binary tree automatically created like so.

enter image description here

So my terminals are {J, 0, 1, 2, 3} and my functions are {%, /, *, -, +}. I'm hoping given this much information and the fact that the arity of each function is 2, and terminals obviously 0, that there is a package which could do this for me? Or maybe someone knows of a piece of software which can format an expression like this into tikz picture code.

share|improve this question
    
Welcome to TeX.SX! –  Heiko Oberdiek Apr 6 at 15:08

2 Answers 2

up vote 8 down vote accepted

Most of the good tree drawing packages (in particular tikz-qtree and forest) accept some form of a bracketed structure, so drawing these trees is quite simple.

Here's an example with both packages:

\documentclass{article}
\usepackage{forest}
\usepackage{tikz-qtree}
\begin{document}
\begin{forest}
prefix tree/.style={for tree={draw,circle,minimum size=2em,edge=->}}
[*,prefix tree [- [J  [\%  [ J ] [ 2 ] ]] [+ [ 2 ] [ 1 ] ]]]
\end{forest}
\begin{tikzpicture}[every tree node/.style={draw,circle,minimum size=2em},
edge from parent/.style={draw, ->,edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}}]
\Tree [.* [.- [.J  [.\%   J   2  ]] [.+  2   1 ]]]
\end{tikzpicture}
\end{document}

output of code

To automate this, here's a basic algorithm which you could implement in your favourite language, or for an integrated solution, implement it in Lua and use LuaTeX.

Create a binary tree from an algebraic expression

share|improve this answer
    
Brilliant. Just what I was looking for. I think I will make a short C program. I will post a link when I have implemented it! Thank You! –  philleonard Apr 6 at 15:48

So after following Alan's answer, I wrote a small program in C (Win) that does a pre-order traversal and it worked a treat. After I finish my dissertation (which this is for), I will write a proper piece of software so it can be used easier by others (i.e. with inputs and automatic latex compilation) but for now here is the "hack".

void create_tex(char*);
int pointer = 0;
char *expression = "/+/*%+-J2*21+J%23%%-3J3++*21+J%23+/-022+0-03-*-++0-030*0J-03++0-030J++*21+J%23-+%+-J2*21+J%23*%+J%23*-++0-030*0J-03+J%23//-3J33\0";

    int main()
    {
        char tex_tree[2048];
        create_tex(tex_tree);
        getch();
        return 0;
    }

    void create_tex(char* tex_tree) {
        char a = expression[pointer];
        if (a == '\0')
            return;
        if (a == '+' || a == '*' || a == '/' || a == '-' || a == '%') {
            if (a == '%') 
                printf("[.\\%c ", a); 
            else
                printf("[.%c ", a); 
            pointer++;
            create_tex(tex_tree);
            pointer++;
            create_tex(tex_tree);
            printf("]");
        }
        else {
            printf("%c ", a); 
        }
    }

On that declaration of the expression char* it gives this output;

[./ [.+ [./ [.* [.\% [.+ [.- J 2 ][.* 2 1 ]][.+ J [.\% 2 3 ]]][.\% [.\% [.- 3 J ]3 ][.+ [.+ [.* 2 1 ][.+ J [.\% 2 3 ]]][.+ [./ [.- 0 2 ]2 ][.+ 0 [.- 0 3 ]]]]]][.- [.* [.- [.+ [.+ 0 [.- 0 3 ]]0 ][.* 0 J ]][.- 0 3 ]][.+ [.+ 0 [.- 0 3 ]]0 ]]]J ][.+ [.+ [.* 2 1 ][.+ J [.\% 2 3 ]]][.- [.+ [.\% [.+ [.- J 2 ][.* 2 1 ]][.+ J [.\% 2 3 ]]][.* [.\% [.+ J [.\% 2 3 ]][.* [.- [.+ [.+ 0 [.- 0 3 ]]0 ][.* 0 J ]][.- 0 3 ]]][.+ J [.\% 2 3 ]]]][./ [./ [.- 3 J ]3 ]3 ]]]]

which when put in this format;

\begin{sidewaysfigure}
\resizebox{700pt}{!}{
\begin{tikzpicture}[every tree node/.style={draw,circle,minimum size=1em},
edge from parent/.style={draw, ->,edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}}]
\Tree [./ [.+ [./ [.* [.\% [.+ [.- J 2 ][.* 2 1 ]][.+ J [.\% 2 3 ]]][.\% [.\% [.- 3 J ]3 ][.+ [.+ [.* 2 1 ][.+ J [.\% 2 3 ]]][.+ [./ [.- 0 2 ]2 ][.+ 0 [.- 0 3 ]]]]]][.- [.* [.- [.+ [.+ 0 [.- 0 3 ]]0 ][.* 0 J ]][.- 0 3 ]][.+ [.+ 0 [.- 0 3 ]]0 ]]]J ][.+ [.+ [.* 2 1 ][.+ J [.\% 2 3 ]]][.- [.+ [.\% [.+ [.- J 2 ][.* 2 1 ]][.+ J [.\% 2 3 ]]][.* [.\% [.+ J [.\% 2 3 ]][.* [.- [.+ [.+ 0 [.- 0 3 ]]0 ][.* 0 J ]][.- 0 3 ]]][.+ J [.\% 2 3 ]]]][./ [./ [.- 3 J ]3 ]3 ]]]]
\end{tikzpicture}
}
\end{sidewaysfigure}

Gives this output!

enter image description here

Thanks for your help @Alan Munn!

share|improve this answer

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.