Class: DS::BinaryTree

Inherits:
Tree
  • Object
show all
Defined in:
lib/ds/trees/binary_tree.rb

Direct Known Subclasses

BinarySearchTree

Instance Attribute Summary

Attributes inherited from Tree

#children, #data

Instance Method Summary collapse

Methods inherited from Tree

#each, #get_leaves, h, #height, #initialize, #izometric?, #leaf?, #leaf_count, #levels, #lowest_height, #mirror!, #to_a, #width

Constructor Details

This class inherits a constructor from DS::Tree

Instance Method Details

#<<(value) ⇒ Object

Inserts a new subtree.



5
6
7
8
9
 
# File 'lib/ds/trees/binary_tree.rb', line 5

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

#insert(x) ⇒ Object

Inserts new element in BSF order



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/ds/trees/binary_tree.rb', line 41

def insert(x)
  q = Queue.new
  if @data == nil
    @data = x
  elsif self.left == nil
    self.left = BinaryTree.new(x)
  elsif self.right == nil
    self.right = BinaryTree.new(x)
  else
    q.push self.left
    q.push self.right
    loop do
      node = q.shift
      if node.left == nil
        node.insert(x)
        break
      else 
        q.push node.left
      end
      if node.right == nil
        node.insert(x)
        break
      else
        q.push node.right
      end
    end
  end
end

#left ⇒ Object

Returns left subtree



12
13
14
15
16
17
18
 
# File 'lib/ds/trees/binary_tree.rb', line 12

def left
  if @children.empty?
    nil
  else
    @children[0]
  end
end

#left=(value) ⇒ Object

Sets left subtree



21
22
23
 
# File 'lib/ds/trees/binary_tree.rb', line 21

def left=(value)
  @children[0] = value
end

#right ⇒ Object

Returns right subtree



26
27
28
29
30
31
32
 
# File 'lib/ds/trees/binary_tree.rb', line 26

def right
  if @children.empty?
    nil
  else
    @children[1]
  end
end

#right=(value) ⇒ Object

Sets right subtree



35
36
37
 
# File 'lib/ds/trees/binary_tree.rb', line 35

def right=(value)
  @children[1] = value
end