前に Ruby で Tree 構造を作る記事（参照）を書きましたが、もう少し汎用的に使えるものを作ってみました。
tree.rb
class Node end class Tree class Branch def initialize(parent) @parent = parent #Node:親 @children = [] #Array:子（要素はNode） end attr_accessor :parent, :children end class Something end def initialize(root) @root = root #node @node = [root] #Array:ノード（要素は Node） @lh = {root=>Branch.new(nil)} #Hash:枝（Node=>Branch） end attr_reader :root #配列arで一気にTreeを作る def self.make(ar) raise "Argument is not Array." if ar.class != Array t = Tree.new(ar[0][0]) ar.each do |ar1| ar1[1].each {|child| t.add(ar1[0], child)} end t end #tree図示（半角でないと表示がズレる） def put_out d = -1; st = "" ar = [] dfs(@root) do |node, depth| lfs = "-- #{node} " if d < depth st += lfs ar.push(st.length) print lfs d = depth else l = ar[depth - 1] st = " " * l + lfs print("\n" + st) ar[depth] = st.length d = depth end end puts end #nodeに新しい子どもを付加する def add(node, newchild) raise "Already newchild exists." if @node.include?(newchild) @node << newchild raise "Parent #{node} does not exist." unless @lh[node] @lh[node].children << newchild @lh[newchild] = Branch.new(node) end #node以下を再帰的に消去 def delete(node) raise "can not delete: no node" unless @node.include?(node) @lh[get_parent(node)].children.delete(node) delete1(node) end def delete1(node) ar = get_children(node) ar.each {|child| delete1(child)} unless ar.empty? @node.delete(node) @lh.delete(node) end private :delete1 #node以下を新たな木としてTreeを作る def copy_tree(node) tree = Tree.new(node) dfs(node) do |nd| get_children(nd).each {|child| tree.add(nd, child)} end tree end #node以下に別の木treeを付加する def merge(node, tree) add(node, (tr = tree.root)) tree.dfs(tr) do |nd| tree.get_children(nd).each {|child| add(nd, child)} end end #nodeをnewnodeで置き換える def replace(node, newnode) return if node == newnode @root = newnode if @root == node raise "Already newnode exists." if @node.include?(newnode) raise "Node does not exist." unless (num = @node.index(node)) @lh[newnode] = @lh[node] a = @lh[get_parent(node)] a.children.map! {|i| (i == node) ? newnode : i} if a get_children(node).each {|child| @lh[child].parent = newnode} @lh.delete(node) @node[num] = newnode end #node a と b を入れ替える def exchange(a, b) raise "Argument does not exist." if !@node.include?(a) or !@node.include?(b) return if a == b x = Something.new replace(a, x); replace(b, a); replace(x, b) end #node a以下と b以下を再帰的に交換する def exchange_r(a, b) raise "Argument does not exist." if !@node.include?(a) or !@node.include?(b) return if a == b t1 = copy_tree(a) t2 = copy_tree(b) pa = get_parent(a) pb = get_parent(b) raise "Root can not recursive exchenge." if !pa or !pb delete(a) delete(b) merge(pa, t2) merge(pb, t1) end #nodeが存在すればtrue、しなければfalse def exist?(node) @node.include?(node) end #node以下で最も深い相対的深さを返す（@rootは入れない） def max_depth(node) max = 0 bfs(node) {|nd, d| max = d if max < d} max end #startからgoalまでのnodeの経路を配列に入れて返す def get_nodes(start, goal) ar = [goal] return ar if start == goal node = get_parent(goal) until node == start ar.unshift(node) node = get_parent(node) end ar.unshift(start) ar end #nodeの親nodeを返す def get_parent(node) @lh[node].parent end #nodeの子供たちnodeをArrayで返す def get_children(node) @lh[node].children end #深さ優先探索。見つければ相対的な階層数を返し、見つからなければfalseを返す。ブロックがあればトラバースする。 #トラバースの引数は |node, depth|。ただしdepthは相対的な深さで、省略可能。 def dfs(start, goal=nil) q = [[start, 0]] while !q.empty? node, depth = q.pop yield(node, depth) if block_given? return depth if node == goal get_children(node).reverse_each do |child| q.push([child, depth + 1]) end end false end #幅優先探索。見つければ相対的な階層数を返し、見つからなければfalseを返す。ブロックがあればトラバースする。 #トラバースの引数は |node, depth|。ただしdepthは相対的な深さで、省略可能。 def bfs(start, goal=nil) q = [[start, 0]] while !q.empty? node, depth = q.shift yield(node, depth) if block_given? return depth if node == goal get_children(node).each do |child| q.push([child, depth + 1]) end end false end end
使い方
Node のクラスは何でもいいです。インスタンスのクラスは何でも（別に Node でなくとも）かまいません。
t = Tree.new(:root)
まず Tree を作ります。引数はルート（最上部）になり、ここでは Symbol である :root にしました（別に例えば 1 でもかまいません）。
t.add(:root, "nya"); t.add(:root, "fnyanya") t.add("nya", 4) t.add("fnyanya", 5) t.add(:root, 6) t.add(6, 7) t.add("fnyanya", "nora"); t.add("nora", "konora") t.put_out
Tree#add(a, b) で、aに子供bを追加していきます（bが Tree に既に存在する場合は追加できません）。Tree#put_out で木を表示します（Node の出力が半角英数でないと、表示がズレます）。
-- root -- nya -- 4
-- fnyanya -- 5
-- nora -- konora
-- 6 -- 7 こんな感じです。
p t.bfs(:root, 7) #=>2 p t.bfs("nora", :root) #=>false
Tree#bfs(start, goal) は、幅優先探索でstartからgoalを探します。見つかれば相対的な深さを返し、見つからなければfalseを返します。
Tree#bfs(start) {|node, depth| ...} は、startから幅優先探索でnodeを順にトラバースします。depthは相対的な深さで、省略可能です。
t.dfs(:root) {|node, d| p [node, d]} #[:root, 0] #["nya", 1] #[4, 2] #["fnyanya", 1] #[5, 2] #["nora", 2] #["konora", 3] #[6, 1] #[7, 2]
Tree#dfs(start, goal) と Tree#bfs(start) {|node, depth| ...} は深さ優先探索で、後は Tree#bfs と同じです。
t.delete("fnyanya") t.replace(6, "nyoro") t.get_parent("nya") #=>:root t.get_children("fnyanya") #=>[5, "nora"] t.get_nodes(:root, "konora") #=>[:root, "fnyanya", "nora", "konora"] t.exchange("nora", 6) t.exist?("nora")
Tree#delete(node) はnode以下を再帰的に消去します。Tree#replace(a, b) は a を b に置き換えます。Tree#get_parent(node) は親nodeを与えます。Tree#get_children は子供たちの入った Array を返します。Tree#get_nodes(start, goal) は startからgoalまでのnodeの経路を配列に入れて返します（必ず到達できる必要があります）。Tree#exchange(a, b) はノード a と b を交換します。Tree#exist?(node) は node が存在すればtrue、存在しなければfalseを返します。
t.copy_tree("fnyanya") t.merge(node, tree)
Tree#copy_tree(node) は node 以下を新しい Tree として生成します。
Tree#merge(node, tree) は、node の下に tree をマージします。
t.max_depth(node)
Tree#max_depth(node) は node 以下の最も深い相対的な深さを与えます。
ar = [[:root, ["nya", "fnyanya", 6]], ["nya", [4]], ["fnyanya", [5, "nora"]], ["nora", ["konora"]], [6, [7]]] t = Tree.make(ar) t.put_out
Tree.make(ar) は、配列で Tree を一気に作ります。この例は上のと同じ Tree を作ります。子供は親が登場したあとに与えられるよう、配列の順序に気をつけて下さい。
