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 



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

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

#insert(x) ⇒ Object

Inserts new element in BSF order



35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/ds/trees/binary_tree.rb', line 35

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 



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

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

#left=(value) ⇒ Object 



12
13
14
 
# File 'lib/ds/trees/binary_tree.rb', line 12

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

#right ⇒ Object 



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

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

#right=(value) ⇒ Object 



24
25
26
 
# File 'lib/ds/trees/binary_tree.rb', line 24

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