Class: DataStructures::TreeNode

Inherits:
Object
  • Object
show all
Defined in:
lib/datastructures/tree_node.rb

Overview

Implements a Tree data structure. TreeNode represents a single node, and has methods for accessing parents, siblings and children.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(data, parent = nil) ⇒ TreeNode

new TreeNode object. :data is the content of the node, can be any Ruby object :parent optionally specify the parent node. Must be a TreeNode. Not specifying a parent makes this a root node.



13
14
15
16
17
18
 
# File 'lib/datastructures/tree_node.rb', line 13

def initialize(data,parent=nil)
  @data = data
  @parent = nil
  raise "parent must be a TreeNode" unless @parent.nil? || @parent.class == TreeNode
  self.clear
end

Instance Attribute Details

#children ⇒ Object

Returns the value of attribute children.



6
7
8
 
# File 'lib/datastructures/tree_node.rb', line 6

def children
  @children
end

#data ⇒ Object

Returns the value of attribute data.



8
9
10
 
# File 'lib/datastructures/tree_node.rb', line 8

def data
  @data
end

#parent ⇒ Object

Returns the value of attribute parent.



7
8
9
 
# File 'lib/datastructures/tree_node.rb', line 7

def parent
  @parent
end

Instance Method Details

#add_child(child) ⇒ Object Also known as: <<

add a child node. :child the node to add as a child. must be a TreeNode



22
23
24
25
 
# File 'lib/datastructures/tree_node.rb', line 22

def add_child child
  child.parent = self
  @children << child
end

#child_count ⇒ Object

count the direct children of this node



36
37
38
 
# File 'lib/datastructures/tree_node.rb', line 36

def child_count
  @children.size
end

#clear ⇒ Object

remove all children



67
68
69
 
# File 'lib/datastructures/tree_node.rb', line 67

def clear
  @children = Array.new
end

#descendents ⇒ Object

return an array of all descendents



62
63
64
 
# File 'lib/datastructures/tree_node.rb', line 62

def descendents
  @children.map { |child| [child, child.descendents] }.flatten
end

#is_leaf? ⇒ Boolean Also known as: empty?

true if the node is a leaf, i.e. has no children

Returns:

  • (Boolean) 


41
42
43
 
# File 'lib/datastructures/tree_node.rb', line 41

def is_leaf?
  @children.empty?
end

#is_root? ⇒ Boolean

true if this node is root, i.e. has no parent

Returns:

  • (Boolean) 


48
49
50
 
# File 'lib/datastructures/tree_node.rb', line 48

def is_root?
  @parent.nil?
end

#remove_child!(child) ⇒ Object

remove a child node. :child the child node to remove. must be a TreeNode



29
30
31
 
# File 'lib/datastructures/tree_node.rb', line 29

def remove_child! child
  @children.delete child
end

#siblings ⇒ Object

return an array of the siblings of this node. Nil if root.



53
54
55
56
57
58
59
 
# File 'lib/datastructures/tree_node.rb', line 53

def siblings
  if self.is_root?
    nil
  else
    @parent.children.reject { |sibling| sibling.equal? self }
  end
end