[Tex/LaTex] Recursive method to build a tree with tikz

tikz-pgf

I would like to translate the next example of a Bernoulli tree built with pst-tree with tikz but I don't know if it's possible :

\documentclass{article}
\usepackage{pstricks,pst-tree}

\makeatletter

\newcount\@Bernoudepth
\newcount\@Bernoumaxdepth

\newcommand\Bernoutree[8][treemode=R,nodesep=1ex,levelsep=12ex]{%
  % #2 = depth of tree
  % #3 = name for success
  % #4 = name for miss
  % #5 = probability of a success
  % #6 = position of  #5
  % #7 = probability of a miss 
  % #8 = position of #7
  \begingroup
  % initialize  parameters
  \psset{treemode=R,nodesep=1ex,levelsep=12ex}%
  \psset{#1}%
  \@Bernoumaxdepth #2\relax
  \def\@Reussite{#3}%
  \def\@Echec{#4}%
  \def\@probareussite{#5}%
  \def\@Argreussite{#6}%
  % if no parameter of position
  % center position 
  \ifx\empty\@Argreussite
    \def\@Argreussite{0.5}%
  \fi
  \def\@probaechec{#7}%
  \def\@Argechec{#8}
  \ifx\empty\@Argechec
    \def\@Argechec{0.5}%
  \fi
  % First call  (empty root, level 1)
  \pstree{\TR{}}{\@Bernoutree{1}}
  \endgroup
}
\newcommand\@Bernoutree[1]{%
  % #1 = recursive depth 
  % initialize the depth
  \@Bernoudepth #1\relax
  \ifnum\@Bernoudepth=\@Bernoumaxdepth
    % if depth  max is reached
    % we place the two final nodes
    \TR{\@Reussite}\taput[tpos=\@Argreussite]{\@probareussite}
    \TR{\@Echec}\tbput[tpos=\@Argechec]{\@probaechec}
    % it's finished
  \else
    % else we build with a recursive method
    % the two branches of higher level
    \advance\@Bernoudepth \@ne
    \pstree{\TR{\@Reussite}\taput[tpos=\@Argreussite]
           {\@probareussite}}{\@Bernoutree{\the\@Bernoudepth}}
    \pstree{\TR{\@Echec}\tbput[tpos=\@Argechec]
           {\@probaechec}}{\@Bernoutree{\the\@Bernoudepth}}
  \fi
}
\makeatother

\pagestyle{empty}

\begin{document}

\Bernoutree[levelsep=18ex,treenodesize=0pt]{4}{$R$}{$E$}{$p$}{}{$q$}{}

\end{document}

Actually I get the tree with the next method but it's not a recursive method.

\documentclass{scrartcl}
\usepackage{pgf,tikz} 
\usetikzlibrary{trees,arrows} 

\makeatletter
\newcount\tkz@Berndepth
\newdimen\tkz@BernLEN
\tkz@BernLEN=24em 
\def\tkzBernTreeSet#{\pgfqkeys{/berntree}} 

\pgfqkeys{/berntree}{%
  success/.code      = \def\tkz@bern@success{#1},
  miss/.code         = \def\tkz@bern@miss{#1},
  p/.code            = \def\tkz@bern@pbsuccess{#1},
  q/.code            = \def\tkz@bern@pbmiss{#1},
  node success style/.style  = {inner sep=2pt,outer sep=3pt},
  node miss style/.style     = {inner sep=2pt,outer sep=3pt},
  edge style/.style  = {->,>=latex',shorten <= 6pt},
  root style/.style  = {draw,circle},
  success/.initial   = S,
  miss/.initial      = E, 
  p/.initial         = $p$,
  q/.initial         = $1-p$,
  gap/.code          = \def\tkz@bern@gap{#1},
  length/.code       = \def\tkz@bern@length{#1} 
} 

\def\tkz@brntree#1#2{%
  \node[/berntree/root style] {};
\global\advance\tkz@Berndepth 1\relax
\begin{scope}[level distance=\tkz@bern@length,
              level 1/.style={sibling distance=#2}]   
  \node[] (root) at (#1) {}     
  [grow=right]
  child[/berntree/edge style] {%
    node[/berntree/node miss style](tkz@E\the\tkz@Berndepth) {\tkz@bern@miss} 
            edge from parent node[fill=white] {\tkz@bern@pbmiss}}
  child [/berntree/edge style] {%
    node[/berntree/node success style] (tkz@S\the\tkz@Berndepth) {\tkz@bern@success} 
            edge from parent node[fill=white] {\tkz@bern@pbsuccess}
             };
\end{scope}}% 

\def\tkzBernTree{\pgfutil@ifnextchar[{\tkz@BernTree}{\tkz@BernTree[]}}
\def\tkz@BernTree[#1]#2{%
\begingroup  
\pgfqkeys{/berntree}{%
success = S,
miss= E,
node success style/.style  = {inner sep=2pt,outer sep=3pt,draw,minimum width=1.5em,minimum height=1.5em},
node miss style/.style  = {inner sep=2pt,outer sep=3pt,circle,draw,minimum width=1.5em},
p=$p$,
q=$q$,
gap=8cm,
length=3cm} 
\pgfqkeys{/berntree}{#1}
  \tkz@BernLEN=\tkz@bern@gap\relax    
  \tkz@Berndepth 0\relax 
  \node (tkz@S0) at (0,0){}; 
\def\tkz@bn@level{#2} 
 \ifcase\tkz@bn@level%
 \or% 
  \tkz@brntree{tkz@S0}{\tkz@BernLEN} 
 \or% 
   \tkz@brntree{tkz@S0}{\tkz@BernLEN} 
  \divide \tkz@BernLEN by 2 %
 \foreach \nd in {1}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}
 \or%
   \tkz@brntree{tkz@S0}{\tkz@BernLEN}  
   \divide \tkz@BernLEN by 2 %
 \foreach \nd in {1}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}   
  \divide \tkz@BernLEN by 2 %
 \foreach \nd in {2,3}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}} 
 \or% 
   \tkz@brntree{tkz@S0}{\tkz@BernLEN}  
   \divide \tkz@BernLEN by 2 %
 \foreach \nd in {1}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}   
  \divide \tkz@BernLEN by 2 %
 \foreach \nd in {2,3}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}} 
  \divide \tkz@BernLEN by 2 %
 \foreach \nd in {4,5,6,7}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}    
  \or% 
   \tkz@brntree{tkz@S0}{\tkz@BernLEN}  
   \divide \tkz@BernLEN by 2 %
 \foreach \nd in {1}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}   
  \divide \tkz@BernLEN by 2 %
 \foreach \nd in {2,3}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}} 
  \divide \tkz@BernLEN by 2 %
 \foreach \nd in {4,...,7}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}} 
   \divide \tkz@BernLEN by 2 %
 \foreach \nd in {8,...,15}{   
   \tkz@brntree{tkz@S\nd}{\tkz@BernLEN}
   \tkz@brntree{tkz@E\nd}{\tkz@BernLEN}}   
 \fi   
 \endgroup
 }
\makeatother
\begin{document}

 \begin{tikzpicture}[yscale=1.2]
 \tkzBernTree[root style/.style  = {fill,circle,outer sep =1pt,inner sep=2pt}]{4}

 \end{tikzpicture} 

\end{document}

Best Answer

The following is a possible solution. I had to separate the node creation and the labelling of the edges. I've also been thinking of doing this with a lindenmayer system but that failed. Enjoy. (I minimised on style settings and focussed on the nub of the matter.)

The tree creation wasn't so straightforward and I had to fight hard to increment and decrement the TeX counter \depth. In the end I ended up doing this as part of a node style. It also required the placement of a dummy coordinate that incremented the level upon returning from the recursion.

The labelling exploits the fact that tikz labels the children of a parent with the labels (parent-1), (parent-2), ..., where (parent) is the label of the parent.

The rest is pretty much straightforward.

\documentclass{article}
\usepackage{tikz}      
\usetikzlibrary{calc}  

\newcount\depth

\makeatletter
\newcommand*\bernoulliTree[1]{%
    \depth=#1\relax            
    \draw node(root)[bernoulli/root] {}[grow=right] \draw@bernoulli@tree;
    \draw \label@bernoulli@tree{root};                                   
}                                                                        

\def\draw@bernoulli@tree{%
    \ifnum\depth>0        
      child foreach \type/\label in {left child/$S$,right child/$F$} {%
          node[bernoulli/\type]{\label} \draw@bernoulli@tree
      }
      coordinate[bernoulli/increment] (dummy)
   \fi%
}

\def\label@bernoulli@tree#1{%
    \ifnum\depth>0
      ($(#1)!0.5!(#1-1)$) node[fill=white,bernoulli/decrement] {$p$}
      \label@bernoulli@tree{#1-1}
      ($(#1)!0.5!(#1-2)$) node[fill=white] {$1-p$}
      \label@bernoulli@tree{#1-2}
      coordinate[bernoulli/increment] (dummy)
   \fi%
}

\makeatother

\tikzset{bernoulli/.cd,
         root/.style={circle,fill,black},
         decrement/.code=\global\advance\depth by-1\relax,
         increment/.code=\global\advance\depth by 1\relax,
         left child/.style={draw,bernoulli/decrement},
         right child/.style={draw,circle}}

\begin{document}

\begin{tikzpicture}[level distance=2cm,
                    level 1/.style={sibling distance=4cm},
                    level 2/.style={sibling distance=2cm},
                    level 3/.style={sibling distance=1cm}]
\bernoulliTree{3}
\end{tikzpicture}

\end{document}

sample output

Code A (preferred)

\documentclass[tikz]{standalone}
\tikzset{if/.code n args={3}{\pgfmathparse{#1}%
  \ifnum\pgfmathresult=1\pgfkeysalso{#2}\else\pgfkeysalso{#3}\fi}}
\begin{document}
\begin{tikzpicture}[nodes=draw, thick,
  H/.style n args={3}{% #1 = direction, #2=initial length, #3=levels
    if={0<=#3}{
      append after command={\pgfextra{\let\tikzLastnode\tikzlastnode}
        node[HH={#1}{#2}{#3}, shift=(#1+180:#2)] at (\tikzLastnode) {} edge (\tikzLastnode)
        node[HH={#1}{#2}{#3}, shift=(#1:#2)]     at (\tikzLastnode) {} edge (\tikzLastnode)}
    }{}},
  HH/.style n args={3}{
    append after command={\pgfextra{\let\tikzLastnode\tikzlastnode}
      node[H={#1}{#2/2}{#3-1}, shift=(#1+90:#2)] at (\tikzLastnode) {} edge (\tikzLastnode)
      node[H={#1}{#2/2}{#3-1}, shift=(#1-90:#2)] at (\tikzLastnode) {} edge (\tikzLastnode)
    }}]
\node[H={0}{3cm}{3}] {};
\end{tikzpicture}
\end{document}

Code B

\documentclass[tikz]{standalone}
\tikzset{if/.code n args={3}{\pgfmathparse{#1}%
  \ifnum\pgfmathresult=1\pgfkeysalso{#2}\else\pgfkeysalso{#3}\fi}}
\begin{document}
\begin{tikzpicture}[nodes=draw, thick, every pin edge/.style={}, every pin/.style={draw},
H/.style n args={3}{% #1 = direction, #2=initial length, #3=levels
  if={0<=#3}{% .6666em are 2*inner sep, \pgflinewidths are outer seps. Hard-coded values!
    pin={[pin distance=#2,
      pin={[pin distance=#2, H={#1}{(#2-.6666em-\pgflinewidth)/2}{#3-1}]#1+90:},
      pin={[pin distance=#2, H={#1}{(#2-.6666em-\pgflinewidth)/2}{#3-1}]#1-90:}]#1:},
    pin={[pin distance=#2,
      pin={[pin distance=#2, H={#1}{(#2-.6666em-\pgflinewidth)/2}{#3-1}]#1+90:},
      pin={[pin distance=#2, H={#1}{(#2-.6666em-\pgflinewidth)/2}{#3-1}]#1-90:}]#1+180:},
  }{}}]
\node[H={0}{3cm-.6666em-\pgflinewidth}{3}] {};
\end{tikzpicture}
\end{document}

Output

enter image description here

[Tex/LaTex] TikZ – Recursive Arc Drawing

It is not any different than the examples given by other languages. Only a few places where expansion needs to be taken care of. I didn't really go for the code golf but it seems working. And it gets fainter as the recursion depth increases.

\documentclass[tikz]{standalone}
\newcount\recurdepth
\begin{document}
\begin{tikzpicture}[scale=2]
\draw[style=help lines] (0,0) grid[step=0.1cm] (1,0.5);

\def\myrecur#1#2#3#4#5{
\recurdepth=#5
\ifnum\the\recurdepth>1\relax
  \advance\recurdepth by-1\relax
  \edef\tempnum{\number\numexpr#1+#3\relax}%a+b
  \edef\tempden{\number\numexpr#2+#4\relax}%c+d
  \pgfmathparse{\tempnum/\tempden}\edef\temp{\pgfmathresult}%(a+b)/(c+d)

  \node[below=\the\recurdepth*1pt,scale=0.1*\the\recurdepth]at({(\temp)*1cm},0){$\frac{\tempnum}{\tempden}$};
  \draw[ultra thin,opacity=\the\recurdepth/10] ({(\temp)*1cm},0) arc (180:0:{((#3/#4)-\temp)*0.5cm});
  \draw[ultra thin,opacity=\the\recurdepth/10] ({(\temp)*1cm},0) arc (0:180:{(\temp-(#1/#2))*0.5cm});
  \begingroup
    \edef\ttempup{\noexpand\myrecur{\tempnum}{\tempden}{#3}{#4}{\the\recurdepth}}
    \edef\ttempdown{\noexpand\myrecur{#1}{#2}{\tempnum}{\tempden}{\the\recurdepth}}
    \ttempup\ttempdown
  \endgroup
\fi
}

\myrecur{0}{1}{1}{1}{6}

\end{tikzpicture}
\end{document}

enter image description here

Best Answer

Related Solutions

[Tex/LaTex] How to draw the recursive H-Layout tree using Tikz

Code A (preferred)

Code B

Output

[Tex/LaTex] TikZ – Recursive Arc Drawing

Related Question