Class: DS::Tree
Direct Known Subclasses
Instance Attribute Summary collapse
-
#children ⇒ Object
readonly
Returns the value of attribute children.
-
#data ⇒ Object
Returns the value of attribute data.
Instance Method Summary collapse
-
#<<(value) ⇒ Object
Inserts a new subtree.
-
#each ⇒ Object
Iterates tree in BFS order.
-
#get_leaves(tree = self) ⇒ Object
Returns leaf list.
-
#h(tree) ⇒ Object
Returns subtree height.
-
#height ⇒ Object
Returns tree height.
-
#initialize(value = nil) ⇒ Tree
constructor
Returns a new tree.
-
#izometric?(other) ⇒ Boolean
Checks if tree is isometric to another tree.
-
#leaf? ⇒ Boolean
Checks if node is leaf.
-
#leaf_count(tree = self) ⇒ Object
Returns the number of leaves for given subtree.
-
#levels ⇒ Object
Returns number of nodes for each tree level.
-
#lowest_height ⇒ Object
Returns node which lies closest to the root.
-
#mirror!(tree = self) ⇒ Object
Mirrors tree.
- #to_a ⇒ Object
-
#width ⇒ Object
Returns tree width.
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.
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.
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 |