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
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