Class: DS::TreeWalker

Inherits:
Object
  • Object
show all
Defined in:
lib/ds/trees/tree_walker.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree = nil) ⇒ TreeWalker

Creates new tree iterator.



9
10
11
12
 
# File 'lib/ds/trees/tree_walker.rb', line 9

def initialize(tree=nil)
  @visited = [] 
  @tree = tree
end

Instance Attribute Details

#tree ⇒ Object

Returns the value of attribute tree.



5
6
7
 
# File 'lib/ds/trees/tree_walker.rb', line 5

def tree
  @tree
end

#visited ⇒ Object

Returns the value of attribute visited.



4
5
6
 
# File 'lib/ds/trees/tree_walker.rb', line 4

def visited
  @visited
end

Instance Method Details

#recalculate!(tree, order, memo = nil, &block) ⇒ Object

Recalculates tree by evaluating block on every node.



84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/ds/trees/tree_walker.rb', line 84

def recalculate!(tree,order,memo=nil,&block)
  if tree

    case order
    when :postorder
      
      arr =  tree.children.map{ |t| recalculate!(t,order,memo,&block) }
      result =  block.call(arr.push tree.data)
      tree.data = result


    when :preorder
        
      tree.data = yield tree, memo
      memo = tree.data

      tree.children.each do |t|
        recalculate!(t,order,memo,&block)
      end

    when :inorder
      raise ArgumentError unless  self.tree.is_a? BinaryTree
      recalculate!(tree.left,order,&block)

        tree.data = yield tree.memo
        memo = tree.data

      recalculate!(tree.right,order,memo,&block)

    end
  end
end

#reset ⇒ Object

Resets tree walker.



61
62
63
64
 
# File 'lib/ds/trees/tree_walker.rb', line 61

def reset
  @visited.clear
  self
end

#summarize(direction = :bottomup) ⇒ Object

Summarize tree



120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/ds/trees/tree_walker.rb', line 120

def summarize(direction=:bottomup)

  case direction
  when :bottomup
    recalculate!(self.tree,:postorder,0){|ar| ar.inject(0){|x,memo| memo += x}}
    self.tree
  when :topdown
    recalculate!(self.tree,:preorder,0){|x,memo| memo = memo+x.data} 
    self.tree
  end
end

#traverse(order = :bfs, &block) ⇒ Object

Traversing tree in given order: bfs - Breadth-first search - default postorder - postorder search preorder - preorder search inorder - inorder search - only for Binary Trees

If block is given, passes each visited subtree to block. Returns values of nodes in given order



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/ds/trees/tree_walker.rb', line 24

def traverse(order=:bfs,&block)
  reset 
  tree = @tree

  case order
  when :bfs
    traverse_bfs &block
  when :postorder
    walk(tree,:postorder,&block)
  when :preorder
    walk(tree,:preorder, &block)
  when (:inorder)
    raise ArgumentError unless tree.kind_of? BinaryTree
    walk(tree,order,&block)
  end

  return visited
end

#traverse_bfs ⇒ Object

Traverses tree in BFS order.



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/ds/trees/tree_walker.rb', line 44

def traverse_bfs
  q = Queue.new
  q.push @tree
  
  loop do
    break if q.empty?
    node = q.shift
    if block_given?
      yield node
    else
      @visited << node.data
    end
    node.children.each{ |n| q.push n } if node.children
  end
end

#traverse_with_h(tree, height = nil, &block) ⇒ Object 



68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/ds/trees/tree_walker.rb', line 68

def traverse_with_h(tree,height=nil,&block)

  tree.children.each do |t|
    traverse_with_h(t,height+1,&block)
  end

  if block_given?
    yield tree, height
  else 
    @visited << tree.data
  end

end