[LRUG] Pruning a tree

Tom Stuart tom at experthuman.com
Tue Jun 28 02:31:12 PDT 2011


On 27 Jun 2011, at 17:32, Andrew Stewart wrote:
> I would like to prune the tree such that the only nodes left are the identified ones and the ones connecting them back to the root.  We ignore any children of identified nodes.

class Node < Struct.new(:value, :children)
  def children
    super || []
  end

  def filter(&predicate)
    filtered_children = children.map { |child| child.filter(&predicate) }.compact
    self.class.new value, filtered_children if !filtered_children.empty? || predicate[value]
  end

  def to_s
    "#{value}#{" -> [#{children.join(', ')}]" unless children.empty?}"
  end
end

--

>> tree = Node.new(2, [Node.new(3, [Node.new(4, [Node.new(5)])]), Node.new(6)])
>> tree.to_s
=> "2 -> [3 -> [4 -> [5]], 6]"
>> tree.filter(&:even?).to_s
=> "2 -> [3 -> [4], 6]"
>> tree.filter(&:odd?).to_s
=> "2 -> [3 -> [4 -> [5]]]"

--

Cheers,
-Tom


More information about the Chat mailing list