Ramo e árvore amarrada em tikz

Question 1

Eu usaria um dos pacotes especializados para desenho de árvores. Mais especificamente, eu usaria forestou, na sua falta, tikz-qtree. Se você fizer isso, poderá especificar árvores de forma muito concisa e simples e garantir facilmente que elas sejam formatadas de forma consistente.

No caso de Forest, o pacote também fará grande parte do trabalho de layout para você, embora os rótulos não sejam tratados desta forma, portanto esta vantagem específica pode não ser muito benéfica para árvores deste tipo específico.

Aqui está um exemplo que define um branch and boundestilo para Forest. Quando aplicado a uma árvore, acontece o seguinte:

tree node, Se thicksão aplicados a todos os nós da árvore e o conteúdo é definido no modo matemático;
as bordas também são thick;
um pouco de espaço é adicionado à árvore para espaçar os galhos e os níveis;
depois que a árvore é analisada, o conteúdo de cada nó é dividido em cada dois pontos: <left label>:<node content>:<right label>:<edge label>;
- A parte antes dos primeiros dois pontos se torna o rótulo esquerdo (em 170). A próxima parte é definida como o conteúdo do nó principal (com tree node, no modo matemático, etc.). A terceira parte é definida como o rótulo direito (em 10). A parte final se torna o rótulo do ramo: à esquerda do ponto médio para um ramo à esquerda e à direita para um ramo à direita.
o conteúdo dos rótulos das bordas pode ser definido no modo de texto ( text branch labels) ou no modo matemático ( maths branch labels);
- prefixos e sufixos podem ser adicionados usando um dos
  - 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>}
uma linha horizontal é desenhada sob cada folha da árvore.

Então podemos especificar o que considero ser a sua segunda árvore, agora editada à luz dos comentários para variar os rótulos das bordas de acordo com o nível, com

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

que é obviamente um pouco mais conciso e produz

Não sei quais são os critérios para esse tipo de árvore, então pode ser necessário alguns ajustes para funcionar bem. Por exemplo, talvez os rótulos das bordas nem sempre tenham o formato x\leqe x\req, ou talvez às vezes haja apenas um ou mais de dois filhos. No entanto, isto deve pelo menos ilustrar o poder potencial desta abordagem.

Código completo:

\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