3
$\begingroup$

How could I create a recursive tree graph, such as one defined by the following:

A family of trees $T_n$ are defined recursively as follows, for all integers $n \ge 1$.

  • The tree $T_1$ consists of a single node.
  • The tree $T_2$ consists of two nodes: a root node, with a leaf as its only child.
  • The tree $T_n$ for $n \geq 3$ consists of a root node connected to two subtrees below it: the left subtree is $T_{n-1}$, and the right subtree is $T_{n-2}$.

I have tried the following:

Clear[T]
T[n_] := TreeGraph[{n}, {n}, VertexLabels -> "Name"] /; n == 1;
T[n_] := TreeGraph[{n, n - 1}, {n -> n - 1}, VertexLabels -> "Name"] /; n == 2;
T[n_] := TreeGraph[{n, T[n - 1], T[n - 2]}, {n -> T[n - 1], n -> T[n - 2]}, VertexLabels -> "Name"] /; n >= 3;

However, the trees that are drawn are disconnected and look like so when evaluating T[4]: T[4]

$\endgroup$
  • $\begingroup$ Did I understand correctly your are looking for a binary tree for n>=3 ? $\endgroup$ – penguin77 Apr 5 '15 at 22:37
2
$\begingroup$

If your are looking for a Binary tree than this may work for you:

 fnBTree[n_] := 
 CompleteKaryTree[Sequence @@ # , VertexLabels -> "Name"] &  /@ 
  Join[{{1, 1}, {2, 1}}, Table[{i + 1, 2}, {i, n - 2}]]

Call fnBTree with n=4

fnBTree[4]

enter image description here

| improve this answer | |
$\endgroup$
4
$\begingroup$

Just for fun to do recursively in contrast to in-built binary graphs,

e[n_] := {n <-> 2 n, n <-> 2 n + 1};
gf[grp_, n_, opts : OptionsPattern[]] := Module[{vl, ne, ng},
   vl = Sort@VertexList[grp];
   ne = Flatten[e /@ vl[[-n ;;]]];
   ng = EdgeAdd[VertexAdd[grp, ne[[All, 2]]], ne];
   Graph[VertexList[ng], EdgeList[ng], 
    FilterRules[{opts}, Options[Graph]]]
   ];
func[0, opts : OptionsPattern[]] := Graph[{0}, {}, opts];
func[n_, op : OptionsPattern[]] := 
 First@Nest[{gf[#[[1]], 2^(#[[2]] + 1), op], #[[2]] + 
      1} &, {Graph[{0 <-> 1}, op], -1}, n - 1]

Visualizing:

tab = Framed[#, ImageSize -> {200, 200}] & /@ 
  Table[func[j, GraphLayout -> "RadialDrawing", 
    VertexLabels -> "Name", VertexStyle -> Red], {j, 0, 5}]

enter image description here

I am sure there are nicer ways.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.