rubytreen-ary-tree

The "Ruby" way of doing an n-ary tree


I'm writing a Ruby script and would like to use a n-ary tree data structure.

Is there a good implementation that is available as source code? Thanks.


Solution

  • To expand on Otto's answer, an easy way of getting a Hash to auto-vivify arrays is to use the default value block with Hash::new, like so:

    node_children = Hash.new { |_node_children, node_key| _node_children[node_key] = [] }
    

    But really, the code depends on what you want to do with your arrays. You can either set them up with Hashes and Arrays, or make some classes:

    class Node
        attr_accessor :value, :children
        def initialize(value, children=[])
            @value = value
            @children = children
        end
        def to_s(indent=0)
            value_s = @value.to_s
            sub_indent = indent + value_s.length
            value_s + @children.map { |child| " - " + child.to_s(sub_indent + 3) }.join("\n" + ' ' * sub_indent)
        end
    end
    
    ROOT = Node.new('root', %w{ farleft left center right farright }.map { |str| Node.new(str) } )
    puts "Original Tree"
    puts ROOT
    puts
    
    ROOT.children.each do |node| 
        node.children = %w{ one two three four }.map { |str| Node.new(node.value + ':' + str) }
    end
    puts "New Tree"
    puts ROOT
    puts
    

    This code, for example, gives:

    Original Tree
    root - farleft
         - left
         - center
         - right
         - farright
    
    New Tree
    root - farleft - farleft:one
                   - farleft:two
                   - farleft:three
                   - farleft:four
         - left - left:one
                - left:two
                - left:three
                - left:four
         - center - center:one
                  - center:two
                  - center:three
                  - center:four
         - right - right:one
                 - right:two
                 - right:three
                 - right:four
         - farright - farright:one
                    - farright:two
                    - farright:three
                    - farright:four