如何用PHP获取所有可能的决策树

这是一个PHP版本,它返回由数组组成的树集合.

function AllBinaryTrees($size = 0)
{
  // empty tree, size=0
  if ($size === 0) { return array(null); }

  // otherwise take 1 from the size for the root of the current subtree and
  // split the rest over the subtrees in every possible way
  $trees = array();
  $size --;

  for ($leftsize=0; $leftsize <= $size; $leftsize ++)
  {
     foreach(AllBinaryTrees($leftsize) as $left)
       foreach(AllBinaryTrees($size-$leftsize) as $right)
       {
          // add the new tree to the collection
          $trees[] = array('left' => $left, 'right' => $right);
       }
  }
  return $trees;
}

请注意,这不是最有效的方法,因为我们一次又一次地生成给定大小的子树,因此缓存它们会更好.我们可以将这个函数包装在一个类中,该类为每个大小的树保留缓存.