To get the content onto the slide, I rotated it 90 degrees and reduced the space around each cell and used a smaller font.
\documentclass[10pt]{beamer}
\usetheme{CambridgeUS} % theme
\usepackage{tikz}
\long\def\aa{\relax}%
\long\def\ab{\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{a}
child{node{a}};
\end{tikzpicture} }
\long\def\ac{\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{a}
child{node{b}};
\end{tikzpicture} }
\long\def\ad{\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{b}
child{node{a}};
\end{tikzpicture} }
\long\def\ae{ \begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{b}
child{node{a}};
\end{tikzpicture} }
\long\def\af{ \begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{b}
child{node{a}}child{node{a}} ;
\end{tikzpicture} }
\long\def\ag{ \begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{b}
child{node{b}}child{node{a}} ;
\end{tikzpicture} }
\long\def\ah{ \begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node(a1){a}
child{node(b1){b}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture}}
\long\def\ai{\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{a}
child{node(a2){a} child{node{b}}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture} }
\long\def\ba{\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node(a1){a}
child{node(b1){b}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture}}
\long\def\ca{\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{a}
child{node(a2){a} child{node{b}}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture} }
\begin{document}
\begin{frame}\footnotesize
\renewcommand{\tabcolsep}{.05cm}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}\hline
\aa&$a$&$b$&\ab&\ac&\ad&\ae&\af&\ag&$\hdots$&\ah&\ai&$\hdots$\\ \hline
\ba& 1 & 2 & 0 & 0 & 0 & 0& 0& 1&$\hdots$& 1& 0&$\hdots$\\ \hline
\ca& 1 & 2 & 0 & 1 & 0 & 0& 0& 1&$\hdots$& 0& 1&$\hdots$\\ \hline
\end{tabular}
\end{frame}
\tikzset{grow'=right}
\begin{tabular}{|l|l|l|}
\hline
% line 1
&
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node(a1){a}
child{node(b1){b}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture}
&
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{a}
child{node(a2){a} child{node{b}}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture}
\\ \hline
%line 2
$a$ & 1 & 1 \\ \hline
%line 3
$b$ & 2 & 2 \\ \hline
%line 4
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{a}
child{node{a}};
\end{tikzpicture}
& 0 & 0 \\ \hline
%line 4
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{a}
child{node{b}};
\end{tikzpicture}
& 0 & 1 \\ \hline
%line 5
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{b}
child{node{a}};
\end{tikzpicture}
& 0 & 0 \\ \hline
%line 6
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{b}
child{node{a}};
\end{tikzpicture}
& 0 & 0 \\ \hline
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{b}
child{node{a}}child{node{a}} ;
\end{tikzpicture}
& 0 & 0 \\ \hline
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{b}
child{node{b}}child{node{a}} ;
\end{tikzpicture}
& 1 & 1 \\ \hline
$\vdots$ & $\vdots$ & $\vdots$ \\ \hline
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node(a1){a}
child{node(b1){b}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture} & 1 & 0 \\ \hline
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{a}
child{node(a2){a} child{node{b}}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture} & 0 & 1 \\ \hline
$\vdots$ & $\vdots$ & $\vdots$ \\ \hline
\end{tabular}
\end{document}

Here is an alternate version where the orientation is the same as yours but the spacing has been tightened up. With a check of the Tikz manual some of the duplicate parameters can be set globally to tighten up the code.
\documentclass[10pt]{beamer}
\usetheme{CambridgeUS} % theme
\usepackage{tikz}
\begin{document}\tiny
\renewcommand{\arraystretch}{.5}
\begin{frame}
\begin{tabular}{|l|l|l|}
\hline
% line 1
&
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node(a1){a}
child{node(b1){b}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture}
&
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{a}
child{node(a2){a} child{node{b}}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture}
\\ \hline
%line 2
$a$ & 1 & 1 \\ \hline
%line 3
$b$ & 2 & 2 \\ \hline
%line 4
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{a}
child{node{a}};
\end{tikzpicture}
& 0 & 0 \\ \hline
%line 4
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{a}
child{node{b}};
\end{tikzpicture}
& 0 & 1 \\ \hline
%line 5
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{b}
child{node{a}};
\end{tikzpicture}
& 0 & 0 \\ \hline
%line 6
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.5]
\node{b}
child{node{a}};
\end{tikzpicture}
& 0 & 0 \\ \hline
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{b}
child{node{a}}child{node{a}} ;
\end{tikzpicture}
& 0 & 0 \\ \hline
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{b}
child{node{b}}child{node{a}} ;
\end{tikzpicture}
& 1 & 1 \\ \hline
$\vdots$ & $\vdots$ & $\vdots$ \\ \hline
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node(a1){a}
child{node(b1){b}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture} & 1 & 0 \\ \hline
\begin{tikzpicture} [every fit/.style={ellipse,draw,red,inner sep=-2pt},scale=0.25]
\node{a}
child{node(a2){a} child{node{b}}}
child{node{b} child{node{b}} child{node{a}}};
\end{tikzpicture} & 0 & 1 \\ \hline
$\vdots$ & $\vdots$ & $\vdots$ \\ \hline
\end{tabular}
\end{frame}
\end{document}
