☰

二叉树生成器的前缀表达式

tag-icon • tag-icon tikz-pgf
二叉树生成器的前缀表达式

我有一些前缀表达式太长，无法手动创建自己的二叉树。我想知道是否有一个 latex 包可以解析我的表达式并自动创建二叉树？

举个较小的例子；

*-J%J2+21

我想要一棵像这样自动创建的二叉树。

在此处输入图片描述

因此我的终端是 {J, 0, 1, 2, 3}，我的函数是 {%, /, *, -, +}。鉴于这么多信息，以及每个函数的参数量为 2，终端显然为 0，我希望有一个包可以为我做到这一点？或者也许有人知道一个软件可以将这样的表达式格式化为 tikz 图片代码。

答案1

大多数好的树绘制包（特别是tikz-qtree和forest）都接受某种形式的括号结构，因此绘制这些树非常简单。

以下是包含这两个包的示例：

\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}

代码输出

为了实现自动化，这里有一个基本算法，您可以用您喜欢的语言来实现它，或者对于集成解决方案，可以在 Lua 中实现它并使用 LuaTeX。

从代数表达式创建二叉树

答案2

因此，在听取了 Alan 的回答后，我用 C（Win）编写了一个小程序，可以进行预排序遍历，效果很好。完成我的论文（本文就是为此而写的）后，我将编写一个合适的软件，以便其他人可以更轻松地使用它（即使用输入和自动乳胶编译），但现在这里是“黑客”。

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); 
        }
    }

在表达式 char* 的声明中，它给出这个输出；

[./ [.+ [./ [.* [.\% [.+ [.- 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 ]]]]

当采用这种格式时；

\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}

给出这个输出！

在此处输入图片描述

感谢您的帮助@Alan Munn！

相关内容