Verzweigungs- und Bindungsbaum in Tikz

Question 1

Ich würde eines der spezialisierten Pakete zum Zeichnen von Bäumen verwenden. Genauer gesagt würde ich forestoder verwenden, falls das nicht geht tikz-qtree. Wenn Sie dies tun, können Sie Bäume sehr präzise und einfach angeben und problemlos sicherstellen, dass sie einheitlich formatiert sind.

Im Falle von Forest übernimmt das Paket auch einen Großteil der Layoutarbeit für Sie, obwohl Beschriftungen nicht auf diese Weise behandelt werden, sodass dieser besondere Vorteil für Bäume dieser besonderen Art möglicherweise nicht von großem Nutzen ist.

Hier ist ein Beispiel, das einen branch and boundStil für „Forest“ definiert. Bei Anwendung auf einen Baum passiert Folgendes:

tree node, Sund thickwerden auf alle Knoten im Baum angewendet und deren Inhalt wird im Mathematikmodus eingestellt;
die Kanten sind auch thick;
Dem Baum wird etwas Platz hinzugefügt, um die Äste und Ebenen zu verteilen.
nachdem der Baum analysiert wurde, wird der Inhalt jedes Knotens an jedem Doppelpunkt aufgeteilt: <left label>:<node content>:<right label>:<edge label>;
- Der Teil vor dem ersten Doppelpunkt wird zur linken Beschriftung (bei 170). Der nächste Teil wird als Inhalt des Hauptknotens festgelegt (mit tree node, im Mathematikmodus usw.). Der dritte Teil wird als rechte Beschriftung (bei 10) festgelegt. Der letzte Teil wird zur Beschriftung des Zweigs: links vom Mittelpunkt für einen linken Zweig und rechts für einen rechten.
der Inhalt der Randbeschriftungen kann entweder im Textmodus ( text branch labels) oder im Mathematikmodus ( maths branch labels) eingestellt werden;
- Präfixe und Suffixe können mit einem der folgenden
  - set branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}
  - set maths branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}
  - set text branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}
Unter jedem Blatt des Baumes wird eine horizontale Linie gezeichnet.

Dann können wir Ihren zweiten Baum spezifizieren, der jetzt im Lichte der Kommentare bearbeitet wurde, um die Kantenbeschriftungen je nach Ebene zu variieren, mit

\begin{forest}
  branch and bound,
  where level=1{
    set branch labels={x\leq}{}{x\geq}{},
  }{
    if level=2{
      set branch labels={}{\geq y}{}{\leq y},
    }{},
  }
  [1055.56:S:950
    [1000:S_1:950:5
    ]
    [1033:S_2:950:6
      [1033:{S_2,1}:950:1]
      [950:{S_2,2}:1033:2]
    ]
  ]
\end{forest}

Das ist offensichtlich deutlich prägnanter und erzeugt

Ich kenne die Kriterien für diese Art von Baum nicht, daher muss dies möglicherweise ein wenig optimiert werden, damit es gut funktioniert. Beispielsweise haben die Kantenbeschriftungen möglicherweise nicht immer die Form x\leqund x\req, oder es gibt manchmal nur ein oder mehr als zwei untergeordnete Elemente. Dies sollte jedoch zumindest die potenzielle Leistungsfähigkeit dieses Ansatzes veranschaulichen.

Vollständiger Code:

\documentclass[border=10pt]{standalone}
\usepackage{forest}
\tikzset{
  tree node/.style = {align=center, inner sep=0pt, font = \scriptsize},
  S/.style = {draw, circle, minimum size = 8mm, top color=white, bottom color=blue!20},
  tree node label/.style={font=\scriptsize},
}
\forestset{
  declare toks={left branch prefix}{},
  declare toks={right branch prefix}{},
  declare toks={left branch suffix}{},
  declare toks={right branch suffix}{},
  tree node left label/.style={
    label=170:#1,
  },
  tree node right label/.style={
    label=10:#1,
  },
  maths branch labels/.style={
    branch label/.style={
      if n=1{
        edge label={node [left, midway] {$\forestoption{left branch prefix}##1\forestoption{left branch suffix}$}},
      }{
        edge label={node [right, midway] {$\forestoption{right branch prefix}##1\forestoption{right branch suffix}$}},
      }
    },
  },
  text branch labels/.style={
    branch label/.style={
      if n=1{
        edge label={node [left, midway] {\foresteoption{left branch prefix}##1\forestoption{left branch suffix}}},
      }{
        edge label={node [right, midway] {\forestoption{right branch prefix}##1\forestoption{right branch suffix}}},
      }
    },
  },
  text branch labels,
  set branch labels/.style n args=4{%
    left branch prefix={#1},
    left branch suffix={#2},
    right branch prefix={#3},
    right branch suffix={#4},
  },
  set maths branch labels/.style n args=4{
    maths branch labels,
    set branch labels={#1}{#2}{#3}{#4},
  },
  set text branch labels/.style n args=4{
    text branch labels,
    set branch labels={#1}{#2}{#3}{#4},
  },
  branch and bound/.style={
    /tikz/every label/.append style=tree node label,
    maths branch labels,
    for tree={
      tree node,
      S,
      math content,
      s sep'+=20mm,
      l sep'+=5mm,
      thick,
      edge+={thick},
    },
    before typesetting nodes={
      for tree={
        split option={content}{:}{tree node left label,content,tree node right label,branch label},
      },
    },
    where n children=0{
      tikz+={
        \draw [thick]  ([yshift=-10pt, xshift=-2.5pt].south west) -- ([yshift=-10pt, xshift=2.5pt].south east);
      }
    }{},
  },
}
\begin{document}
\begin{forest}
  branch and bound,
  where level=1{
    set branch labels={x\leq}{}{x\geq}{},
  }{
    if level=2{
      set branch labels={}{\geq y}{}{\leq y},
    }{},
  }
  [1055.56:S:950
    [1000:S_1:950:5
    ]
    [1033:S_2:950:6
      [1033:{S_2,1}:950:1]
      [950:{S_2,2}:1033:2]
    ]
  ]
\end{forest}
\end{document}

Answer