Class: DS::BinaryTree

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

Overview

Class implements binary tree

Instance Attribute Summary

Attributes inherited from Tree

#children, #data, #parent

Instance Method Summary collapse

Methods inherited from Tree

#each, #get_leaves, h, #height, #initialize, #izometric?, #leaf?, #leaf_count, #levels, #lowest_height, #mirror!, #sibblings, #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, self)
  @children << subtree
  subtree
end

#insert(x) ⇒ Object

Inserts new element in BSF order



32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/ds/trees/binary_tree.rb', line 32

def insert(x)
  q = SimpleQueue.new
  if @data.nil?
    @data = x
  elsif left.nil?
    self.left = BinaryTree.new(x, self)
  elsif right.nil?
    self.right = BinaryTree.new(x, self)
  else
    q.push left
    q.push right
    insert_next(q, x)
  end
end

#left ⇒ Object

Returns left subtree



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

def left
  @children[0]
end

#left=(value) ⇒ Object

Sets left subtree



17
18
19
 
# File 'lib/ds/trees/binary_tree.rb', line 17

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

#right ⇒ Object

Returns right subtree



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

def right
  @children[1]
end

#right=(value) ⇒ Object

Sets right subtree



27
28
29
 
# File 'lib/ds/trees/binary_tree.rb', line 27

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