變化樹形結構紅寶石使用嵌套哈希

Question

我有以下的類叫做樹是建立一個簡單的樹

class Tree 
    attr_accessor :children, :node_name 

    def initialize(name, children=[]) 
    @children = children 
    @node_name = name 
    end 

    def visit_all(&block) 
    visit &block 
    children.each {|c| c.visit_all &block} 
    end 

    def visit(&block) 
    block.call self 

    end 
end 

ruby_tree = Tree.new("grandpa", 
    [Tree.new("dad", [Tree.new("child1"), Tree.new("child2")]), 
    Tree.new("uncle", [Tree.new("child3"), Tree.new("child4")])]) 
puts "Visiting a node" 
ruby_tree.visit {|node| puts node.node_name} 
puts 

puts "visiting entire tree" 
ruby_tree.visit_all {|node| puts node.node_name} 

現在什麼，我試圖做的是要能夠創建樹嵌套的哈希值，而不是。例如，對於這一個，這將是：

{'grandpa'=> {'dad'=> {'child 1'=> {}，'child 2'=> {}}，'uncle'= > {'child 3'=> {}，'child 4'=> {}}}}

任何想法可以幫助嗎？

Answer 1

它融化了我的大腦，所以我寫了一個規格爲它：

# encoding: UTF-8 

require 'rspec' # testing/behaviour description framework 
require_relative "../tree.rb" # pull in the actual code 

# Everything in the `describe` block is rspec "tests" 
describe :to_h do 
    # contexts are useful for describing what happens under certain conditions, in the first case, when there is only the top of the tree passed to to_h 
    context "One level deep" do 
    # a let is a way of declaring a variable in rspec (that keeps it useful) 
    let(:ruby_tree) { Tree.new "grandpa" } 
    let(:expected) { {"grandpa" => {} } } 
    subject { ruby_tree.to_h } # this the behaviour you're testing 
    it { should == expected } # it should equal what's in expected above 
    end 
    # The next two contexts are just testing deeper trees. I thought that each depth up to 3 should be tested, as past 3 levels it would be the same as 3. 
    context "Two levels deep" do 
    let(:ruby_tree) { 
     Tree.new("grandpa", 
        [Tree.new("dad"), Tree.new("uncle") ] 
      ) 
    } 
    let(:expected) do 
     {"grandpa" => { 
      "dad" => {}, "uncle" => {} 
     } 
     } 
    end 
    subject { ruby_tree.to_h } 
    it { should == expected } 
    end 
    context "grandchildren" do 
    let(:ruby_tree){ 
     ruby_tree = Tree.new("grandpa", 
     [Tree.new("dad", [Tree.new("child1"), Tree.new("child2")]), 
     Tree.new("uncle", [Tree.new("child3"), Tree.new("child4")])]) 
    } 
    let(:expected) { 
     {'grandpa'=>{'dad'=>{'child1'=>{},'child2'=>{}}, 'uncle'=>{'child3'=>{}, 'child4'=>{}}}} 
    } 
    subject { ruby_tree.to_h } 
    it { should == expected } 
    end 
end 

class Tree 
    def to_h 
    hash ={} # create a hash 
    # `reduce` is a synonym for `inject`, see the other answer for a link to the docs, 
    # but it's a type of fold 
    # http://en.wikipedia.org/wiki/Fold_(higher-order_function), 
    # which will take a list of several objects and 
    # fold them into one (or fewer, but generally one) through application of a function. 
    # It reduces the list through injecting a function, hence the synonyms. 
    # Here, the current node's list of children is folded into one hash by 
    # applying Hash#merge to each child (once the child has been been made 
    # into a one key hash, possibly with children too), and then assigned as 
    # the current node's hash value, with the node_name as the key. 
    hash[@node_name] = children.reduce({}){|mem,c| mem.merge c.to_h} 
    hash # return the hash 
    end 
end 

我敢肯定，這可以做的更好，但它的作品至少。

順便說一句，你提供的散列有一些額外的空間，我不認爲應該在那裏？例如「孩子1」當它應該是「孩子1」，除非你真的想要加入？

Answer 2

class Tree 
    def to_hash 
    { @node_name => @children.inject({}) { |acum, child| acum.merge(child.to_hash) } } 
    end 
end 

p ruby_tree.to_hash 

用於注射here

Answer 3

分解成更簡單的子問題，並使用遞歸見文檔：

def make_node(name,subhash) 
    Tree.new(name,subhash.keys.collect{|k|make_node(k,subhash[k])}) 
end 
def make_root(hash) 
    make_node(hash.keys[0],hash[hash.keys[0]]) 
end 

然後證明它的工作原理：

tree_like_this = make_root({'grandpa' => { 'dad' => {'child 1' => {}, 'child 2' => {} }, 
'uncle' => {'child 3' => {}, 'child 4' => {} } } }) 

puts 'tree like this' 
tree_like_this.visit_all{|n|puts n.node_name} 

這是從練習Seven Languages In Seven Weeks。原來的練習說要把它全部放在initialize。