11

Is there a clever way to draw an Eulerian walk around a tree? My current solution is quite clumsy...

\documentclass[aspectratio=169]{beamer}
\usepackage[utf8]{inputenc}
\usetheme{moloch}

\usepackage{tikz}
\usepackage{forest}
\usetikzlibrary{arrows.meta}
\begin{document}
    \begin{frame}
 \begin{forest}
   [-
     [$\div$, tikz+={
         \draw [-Latex, mLightBrown, thick, rounded corners] 
           (-.5,0) to (-1.6,-1) 
               to (-2.5,-2.3)
               to (-3.1,-4.5)
               to (-3.1,-4.9)
               to (-2.5,-4.9)
               to (-2.3,-4)
               to (-2.1,-4.9)
               to (-1.8,-4.9)
               to (-1.8,-4.5)
               to (-2.2,-3.3)
               to (-2,-2.7)
               to (-1.8,-3.7)
               to (-1.4,-3.7)
               to (-1.5,-2.7)
               to (-1.8,-2.2)
               to (-1.3,-1.3)
               to (-.8,-2.2)
               to (-1.5,-4.3)
               to (-1.5,-4.9)
               to (-1.1,-4.9)
               to (-.9,-4)
               to (-.7,-4.9)
               to (-.3,-4.9)
               to (-.3,-4.5)
               to (-.7,-3.3)
               to (-.5,-2.7)
               to (-.3,-3.7)
               to (0,-3.7)
               to (0,-3)
               to (-.9,-1.2)
               to (0,-.2)
               to (.9,-1.2)
               to (0.3,-3)
               to (0.3,-3.7)
               to (.8,-3.7)
               to (.9,-2.7)
               to (1.1,-3.5)
               to (.6,-4.9)
               to (1.2,-4.9)
               to (1.3,-4)
               to (1.4,-4.9)
               to (1.8,-4.9)
               to (1.1,-2)
               to (1.3,-1.4)
               to (1.5,-2.5)
               to (1.9,-2.5)
               to (1.9,-2)
               to (1.3,-.7)
               to (.5,0);
         }
       [$\times$
         [$+$
           [3]
           [1]
         ]
         [3]
       ]
       [$+$
         [$-$
           [9]
           [5]
         ]
         [2]
       ]
     ]
     [$+$
       [$\times$
         [3]
         [$-$
           [7]
           [4]
         ]
       ]
       [6]
     ]
   ]
 \end{forest}
    \end{frame}
\end{document}

and yields the following:

eulerian walk around tree screenshot

0

2 Answers 2

10

This should work for any tree where every node has either zero or two children. It could be adapted for other cases, but I did not account for those here.

I would have liked to have defined some kind of step rather than doing it mechanically, but I'm not sure how to do something similar to tree, since tree and friends are defined in terms of internal commands.

The basic strategy is to define a custom toks register, outer walk, which we use to accumulate parts of the path we want to draw. We basically draw around the tree by taking advantage of the regularities in its structure: we know the order in which forest processes nodes in step tree and so we add bits to the path (1) for each node and (2) for each leaf. In the latter case, we figure out whether this is a first or second child, in order to add the various additions to the path in the appropriate places. We then add the final node, which we know is the root node, and feed the contents of outer walk to a \path command via tikz+.

Anyway, the upshot is that euler is a mechanical style and not clever at all, but it does let you write

\begin{forest}
  for tree={
    math content,
  },
  euler,
  [-
    [\div
      [\times
        [+
          [3]
          [1]
        ]
        [3]
      ]
      [+
        [-
          [9]
          [5]
        ]
        [2]
      ]
    ]
    [+
      [\times
        [3]
        [-
          [7]
          [4]
        ]
      ]
      [6]
    ]
  ]
\end{forest}

to produce

euler style applied to tree

\documentclass[border=10pt,11pt]{standalone}
\usepackage[utf8]{inputenc}
\usepackage{forest}
\usetikzlibrary{arrows.meta}
% ateb: https://tex.stackexchange.com/a/712007/ addaswyd o gwestiwn Arne: https://tex.stackexchange.com/q/711954/
\begin{document}
\forestset{
  declare toks register={outer walk},
  outer walk={},
  euler/.style={
    before drawing tree={
      for tree={
        outer walk+/.process={Ow{name}{(##1.west) -- }},
        if={>On={n children}{0}}{
          outer walk+/.process={Ow{name}{(##1.south west) -- (##1.south east) -- (##1.east) -- }},
          if n=2{
            Nodewalk={}{while={> On= On> & {n}{2} {level}{1} }{u}}{outer walk+/.process={Ow{name}{(##1.east) -- }}},
            if n=1{
              outer walk+/.process={Ow{!u.name}{(##1.south)  --  }},
            }{},
          }{
            outer walk+/.process={Ow{!u.name}{(##1.south) -- }},
          },
        } {}
      },
      outer walk+/.process={Ow{name}{(##1.east)}},
      typeout/.register=outer walk,
      tikz+={
        \path [draw=brown!50!orange,-Latex,rounded corners] \foresteregister{outer walk};
      },
    },
  },
}
\begin{forest}
  for tree={
    math content,
  },
  euler,
  [-
    [\div
      [\times
        [+
          [3]
          [1]
        ]
        [3]
      ]
      [+
        [-
          [9]
          [5]
        ]
        [2]
      ]
    ]
    [+
      [\times
        [3]
        [-
          [7]
          [4]
        ]
      ]
      [6]
    ]
  ]
\end{forest}
\end{document}
8

This isn't automated, but you can use the forest node internal id (accessible with \forestoption{id} to give each node a name. Then use those names to draw a path that fits the nodes better.

I added a macro \leaf to draw around the bottoms of the leaves and keep the code a bit cleaner.

enter image description here

\documentclass{article}

\usepackage{forest}
\usetikzlibrary{arrows.meta}
\tikzset{euler/.style={thick, orange, rounded corners, -Latex}}
\newcommand{\leaf}[1]{(N-#1.north west)--(N-#1.south west)--(N-#1.south east)--(N-#1.north east)}

\begin{document}

\begin{forest}
for tree={math content, name=N-\forestoption{id}}
[-[\div[\times[+[3][1]][3]][+[-[9][5]][2]]][+[\times[3][-[7][4]]][6]]]
\draw[euler] (N-2.west)--(N-3.west)--(N-4.west)--(N-5.west)--\leaf{6}
    --(N-5.south)--\leaf{7}--(N-5.east)--(N-4.south)--\leaf{8}
    --(N-4.east)--(N-3.south)--(N-9.west)--(N-10.west)--\leaf{11}
    --(N-10.south)--\leaf{12}--(N-10.east)--(N-9.south)--\leaf{13}
    --(N-9.east)--(N-3.east)--(N-2.south)--(N-14.west)--(N-15.west)--\leaf{16}
    --(N-15.south)--(N-17.west)--\leaf{18}--(N-17.south)--\leaf{19}
    --(N-17.east)--(N-15.east)--(N-14.south)--\leaf{20}--(N-14.east)--(N-2.east);
\end{forest}

\end{document}

Just so you can see how the internal numbering of nodes works, here is each node with its contents replaced by its internal id.

enter image description here

To get this image, replace the for tree with this code:

for tree={math content, name=N-\forestoption{id}, delay={content=\forestoption{id}}}

You must log in to answer this question.

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