Class: CompSci::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/compsci/tree.rb

Direct Known Subclasses

BinaryTree

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root_node, child_slots: 2) ⇒ Tree

Returns a new instance of Tree.



7
8
9
10
11
 
# File 'lib/compsci/tree.rb', line 7

def initialize(root_node, child_slots: 2)
  @root = root_node
  @child_slots = child_slots
  @open_parent = @root
end

Instance Attribute Details

#child_slots ⇒ Object (readonly)

Returns the value of attribute child_slots.



5
6
7
 
# File 'lib/compsci/tree.rb', line 5

def child_slots
  @child_slots
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



5
6
7
 
# File 'lib/compsci/tree.rb', line 5

def root
  @root
end

Instance Method Details

#bf_search(node: nil, &blk) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
 
# File 'lib/compsci/tree.rb', line 43

def bf_search(node: nil, &blk)
  node ||= @root
  destinations = [node]
  while !destinations.empty?
    node = destinations.shift
    return node if yield node
    destinations += node.children
  end
  nil
end

#df_search(node: nil, &blk) ⇒ Object 



26
27
28
29
30
31
32
33
34
 
# File 'lib/compsci/tree.rb', line 26

def df_search(node: nil, &blk)
  node ||= @root
  return node if yield node
  node.children.each { |c|
    stop_node = self.df_search(node: c, &blk)
    return stop_node if stop_node
  }
  nil
end

#df_search_generic(node: nil, &blk) ⇒ Object 



36
37
38
39
40
41
 
# File 'lib/compsci/tree.rb', line 36

def df_search_generic(node: nil, &blk)
  # Perform pre-order operation
  # children.each { Perform in-order operation }
  # Perform post-order operation
  puts "not defined yet"
end

#open_parent ⇒ Object 



21
22
23
24
 
# File 'lib/compsci/tree.rb', line 21

def open_parent
  return @open_parent if self.open_parent?(@open_parent)
  @open_parent = self.bf_search { |n| self.open_parent?(n) }
end

#open_parent?(node) ⇒ Boolean

Returns:

  • (Boolean) 


17
18
19
 
# File 'lib/compsci/tree.rb', line 17

def open_parent?(node)
  node.children.size < @child_slots
end

#push(value) ⇒ Object 



13
14
15
 
# File 'lib/compsci/tree.rb', line 13

def push(value)
  self.open_parent.new_child value
end