How about this:
\documentclass{article} \usepackage{tikz-qtree} \usepackage{tikz} \usetikzlibrary{calc} \begin{document} \begin{tikzpicture}[grow'=right] \tikzset{level distance=2cm} \tikzset{sibling distance=1cm} \tikzset{every tree node/.style={anchor=base west}} \Tree[.\node (a) {a}; [.\node (b) {b}; [.\node (d) {d}; ] [.\node (e) {e}; ] ] [.\node (c) {c}; [.\node (f) {f}; ] [.\node (g) {g}; ] ] ] \node[red] at ($0.33*(a)+0.33*(b)+0.33*(c)$) {\textbf{OR}}; \node[red] at ($0.33*(b)+0.33*(d)+0.33*(e)$) {\textbf{AND}}; \node[red] at ($0.33*(c)+0.33*(f)+0.33*(g)$) {\textbf{OR}}; \end{tikzpicture} \end{document}

I used the possibility to add named nodes in a qtree (see the manual, section 4). Then I used the calc library provided by TikZ to compute a coordiante "in the middle", which is basically the weighted average of the coordinates around it (with equal weights, thus 0.33).
Edit 1: Here's a variant drawing an arc, it uses Jasper Loy's answer to this question:
\documentclass{article} \usepackage{tikz-qtree} \usepackage{tikz} \usetikzlibrary{calc} \usepackage{tkz-euclide} \usetkzobj{all} \newcommand{\sparc}[8]% vertex, first child, last child, relative radius, text, text options, draw options, shift { \coordinate (firstarm) at ($(#1)!#4!(#2)$); \coordinate (lastarm) at ($(#1)!#4!(#3)$); \tkzDrawArc[#7](#1,lastarm)(firstarm) \node[#6] at ($(#1)+(#8)$) {#5}; } \begin{document} \begin{tikzpicture}[grow'=right] \tikzset{level distance=2cm} \tikzset{sibling distance=1cm} \tikzset{every tree node/.style={anchor=base west}} \Tree[.\node (a) {a}; [.\node (b) {b}; [.\node (d) {d}; ] [.\node (e) {e}; ] [.\node (e2) {e$_2$}; ] [.\node (e3) {e$_3$}; ] ] [.\node (c) {c}; [.\node (f) {f}; ] [.\node (g) {g}; ] [.\node (h) {h}; ] ] ] \sparc{a}{b}{c}{0.7}{OR}{red}{ultra thick,color=blue!50!cyan}{1.5,0} \sparc{b}{d}{e3}{0.6}{AND}{yellow,circle,fill=green!50!gray}{ultra thick,color=red!50!orange}{1,0} \sparc{c}{f}{h}{0.6}{OR}{blue,circle,fill=blue!50!gray,fill opacity=0.3,text opacity=1}{ultra thick,color=green!30!gray}{1,0} \end{tikzpicture} \end{document}

Edit 2: the small gaps in the arcs are due to the fact that always the .center of the nodes is used for computation. For a left-to right graph, this would be better:
\newcommand{\sparc}[8]% vertex, first child, last child, relative radius, text, text options, draw options, shift { \coordinate (firstarm) at ($(#1.east)!#4!(#2.west)$); \coordinate (lastarm) at ($(#1.east)!#4!(#3.west)$); \coordinate (vertex) at (#1.east); \tkzDrawArc[#7](vertex,lastarm)(firstarm) \node[#6] at ($(#1)+(#8)$) {#5}; }
