Class: DS::Tree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/ds/trees/tree.rb

Direct Known Subclasses

BinaryTree

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value = nil) ⇒ Tree

Returns a new tree.



10
11
12
13
 
# File 'lib/ds/trees/tree.rb', line 10

def initialize(value=nil)
  @data = value
  @children = []
end

Instance Attribute Details

#children ⇒ Object (readonly)

Returns the value of attribute children.



7
8
9
 
# File 'lib/ds/trees/tree.rb', line 7

def children
  @children
end

#data ⇒ Object

Returns the value of attribute data.



6
7
8
 
# File 'lib/ds/trees/tree.rb', line 6

def data
  @data
end

Instance Method Details

#<<(value) ⇒ Object

Inserts a new subtree.



16
17
18
19
20
 
# File 'lib/ds/trees/tree.rb', line 16

def << (value)
  subtree = Tree.new(value)
  @children << subtree
  return subtree
end

#each ⇒ Object

Iterates tree in BFS order.



108
109
110
 
# File 'lib/ds/trees/tree.rb', line 108

def each
  TreeWalker.new(self).traverse{ |t| yield t }
end

#get_leaves(tree = self) ⇒ Object

Returns leaf list.



28
29
30
31
32
33
 
# File 'lib/ds/trees/tree.rb', line 28

def get_leaves(tree=self)
  list = List.new
  walker = TreeWalker.new(self)
  walker.traverse(:postorder){|t| list.append(t) if t.leaf? }
  list
end

#h(tree) ⇒ Object

Returns subtree height.



67
68
69
70
71
72
73
 
# File 'lib/ds/trees/tree.rb', line 67

def h(tree)
  unless tree.leaf?
    tree.children.map{|t| h(t) }.max + 1
  else
    1
  end
end

#height ⇒ Object

Returns tree height.



76
77
78
 
# File 'lib/ds/trees/tree.rb', line 76

def height
  h(self)
end

#izometric?(other) ⇒ Boolean

Checks if tree is isometric to another tree.

Returns:

  • (Boolean) 


94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/ds/trees/tree.rb', line 94

def izometric?(other)
  tree = self
  unless tree.leaf? and other.leaf?
    if tree.children.size == other.children.size
      tree.children.each_with_index{|t,i| return false unless t.izometric?(other.children[i])}
    else
      return false
    end
  end
  return true
end

#leaf? ⇒ Boolean

Checks if node is leaf.

Returns:

  • (Boolean) 


23
24
25
 
# File 'lib/ds/trees/tree.rb', line 23

def leaf?
  self.children.empty?
end

#leaf_count(tree = self) ⇒ Object

Returns the number of leaves for given subtree.



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

def leaf_count(tree=self)
  if tree.leaf?
    1
  else
    tree.children.inject(0){|m,t| m += leaf_count(t)} 
  end
end

#levels ⇒ Object

Returns number of nodes for each tree level. 2=>4, 3=>5



47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/ds/trees/tree.rb', line 47

def levels
  walker = TreeWalker.new(self)
  nodes={}

  walker.traverse_with_h(self,1) do |t,level|
    if nodes[level] 
      nodes[level] += 1
    else
      nodes[level] = 1
    end
  end
  nodes
end

#lowest_height ⇒ Object

Returns node which lies closest to the root.



81
82
83
 
# File 'lib/ds/trees/tree.rb', line 81

def lowest_height
  find{ |node| node.leaf? }.data
end

#mirror!(tree = self) ⇒ Object

Mirrors tree.



86
87
88
89
90
91
 
# File 'lib/ds/trees/tree.rb', line 86

def mirror!(tree=self)
  unless tree.leaf?
    tree.children.reverse!
    tree.children.each{|t| mirror!(t)}
  end
end

#to_a ⇒ Object 



112
113
114
 
# File 'lib/ds/trees/tree.rb', line 112

def to_a
  map{ |node| node.data }
end

#width ⇒ Object

Returns tree width.



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

def width
    levels.values.max
end