class Kaninchen::DataStructure::Tree

Attributes

root[R]

Public Class Methods

new(value) click to toggle source
# File lib/kaninchen/data_structure/tree.rb, line 11
def initialize(value)
  if value.is_a? Kaninchen::DataStructure::Node
    @root = value
  else
    @root = Kaninchen::DataStructure::Node.new value
  end
  @root.send(:set_tree_node_data, tree: self)
end

Public Instance Methods

each_node(type = :preorder) { |root| ... } click to toggle source
# File lib/kaninchen/data_structure/tree/each_node.rb, line 6
def each_node(type = :preorder)
  case
  when %i[preorder depth_first].include?(type)
    yield self.root
    recursive_preorder_loop(self.root) { |node| yield node }
  when type === :inorder
    recursive_inorder_loop(first_leaf, :left_most) { |node| yield node }
  when type === :postorder
    recursive_postorder_loop(self.root) { |node| yield node }
  when %i[levelorder breadth_first].include?(type)
    yield self.root
    recursive_levelorder_loop(self.root) { |node| yield node }
  end
end
each_node_with_index(type = :preorder) { |node, index| ... } click to toggle source
# File lib/kaninchen/data_structure/tree/each_node.rb, line 21
def each_node_with_index(type = :preorder)
  index = 0
  self.each_node(type) do |node|
    yield node, index
    index += 1
  end
end
height() click to toggle source
# File lib/kaninchen/data_structure/tree/properties.rb, line 10
def height
  self.nodes(:preorder).map do |node|
    count = 1
    until node.parent.nil?
      count += 1
      node = node.parent
    end
    count
  end.max
end
inspect()
Alias for: to_s
leaves() click to toggle source
# File lib/kaninchen/data_structure/tree/properties.rb, line 6
def leaves
  self.nodes(:preorder).select { |node| node.children.empty? }
end
node_values(type = nil) click to toggle source
# File lib/kaninchen/data_structure/tree/nodes.rb, line 16
def node_values(type = nil)
  if type.nil?
    { self.root.value => recursive_get_struct_value(self.root) }
  else
    nodes(type).map(&:value)
  end
end
nodes(type = nil) click to toggle source
# File lib/kaninchen/data_structure/tree/nodes.rb, line 6
def nodes(type = nil)
  if type.nil?
    { self.root => recursive_get_struct(self.root) }
  else
    result = []
    each_node(type) { |node| result.push(node) }
    result
  end
end
to_s() click to toggle source
# File lib/kaninchen/data_structure/tree.rb, line 20
def to_s
  "<Tree root=\"#{root}\" height=\"#{height}\">"
end
Also aliased as: inspect

Private Instance Methods

first_leaf() click to toggle source
# File lib/kaninchen/data_structure/tree/properties.rb, line 23
def first_leaf
  self.each_node(:preorder) { |node| return node if node.children.empty? }
end
recursive_get_struct(node) click to toggle source
# File lib/kaninchen/data_structure/tree/nodes.rb, line 26
def recursive_get_struct(node)
  result = {}
  node.children.each do |child_node|
    result[child_node] = recursive_get_struct(child_node)
  end
  result.empty? ? nil : result 
end
recursive_get_struct_value(node) click to toggle source
# File lib/kaninchen/data_structure/tree/nodes.rb, line 34
def recursive_get_struct_value(node)
  result = {}
  node.children.each do |child_node|
    result[child_node.value] = recursive_get_struct_value(child_node)
  end
  result.empty? ? nil : result
end
recursive_inorder_loop(node, current_role, end_node = nil) { |node| ... } click to toggle source
# File lib/kaninchen/data_structure/tree/each_node.rb, line 38
def recursive_inorder_loop(node, current_role, end_node = nil)
  yield node
  case current_role
  when :left_most
    until node === end_node or node.root?
      recursive_inorder_loop(node.parent, :right_recursive, end_node) { |n| yield n } unless node.parent === end_node
      node = node.parent
    end
  when :right_recursive
    node.send(:right_children).each do |child_node|
      left_most_child = child_node.send(:left_most_child)
      recursive_inorder_loop(left_most_child, :left_most, end_node = node) { |n| yield n }
    end
  end
end
recursive_levelorder_loop(node) { |child_node| ... } click to toggle source
# File lib/kaninchen/data_structure/tree/each_node.rb, line 64
def recursive_levelorder_loop(node)
  children = node.children
  children.each { |child_node| yield child_node }
  children.each { |child_node| recursive_levelorder_loop(child_node) { |n| yield n } }
end
recursive_postorder_loop(node) { |n| ... } click to toggle source
# File lib/kaninchen/data_structure/tree/each_node.rb, line 54
def recursive_postorder_loop(node)
  unless node.leaf?
    recursive_postorder_loop(node.left_child) { |n| yield n }
    node.send(:right_children).each do |child_node|
      recursive_postorder_loop(child_node) { |n| yield n }
    end
  end
  yield node
end
recursive_preorder_loop(parent_node) { |child_node| ... } click to toggle source
# File lib/kaninchen/data_structure/tree/each_node.rb, line 31
def recursive_preorder_loop(parent_node)
  parent_node.children.each do |child_node|
    yield child_node
    recursive_preorder_loop(child_node) { |node| yield node }
  end
end