Class: BinaryTree

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(data = nil) ⇒ BinaryTree

Returns a new instance of BinaryTree.



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

def initialize(data=nil)
    @data = data
    @left = nil
    @right = nil
end

Instance Attribute Details

#data ⇒ Object (readonly)

Returns the value of attribute data.



2
3
4
 
# File 'lib/binary_tree.rb', line 2

def data
  @data
end

#left ⇒ Object

Returns the value of attribute left.



3
4
5
 
# File 'lib/binary_tree.rb', line 3

def left
  @left
end

#right ⇒ Object

Returns the value of attribute right.



3
4
5
 
# File 'lib/binary_tree.rb', line 3

def right
  @right
end

#root ⇒ Object

Returns the value of attribute root.



3
4
5
 
# File 'lib/binary_tree.rb', line 3

def root
  @root
end

Instance Method Details

#inorder(node) ⇒ Object

print data in inorder form (left, root, right)



38
39
40
41
42
43
44
45
 
# File 'lib/binary_tree.rb', line 38

def inorder(node)
    if node == nil
        return
    end
    inorder(node.left)
    puts "#{node.data}"
    inorder(node.right)
end

#insert(node, data) ⇒ Object

insert data in binary tree node



12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/binary_tree.rb', line 12

def insert(node, data)
    q = []
    if node == nil
        @root = BinaryTree.new(data)
        return @root
    end
    q.push(node)
    while (!q.empty?)
        node = q.shift
        if node.left == nil
            node.left = BinaryTree.new(data)
            break
        else
            q.push(node.left)
        end
        if node.right == nil
            node.right = BinaryTree.new(data)
            break
        else
            q.push(node.right)
        end
    end
    return node
end

#postorder(node) ⇒ Object

print data in postorder for (left, right, root)



58
59
60
61
62
63
64
65
 
# File 'lib/binary_tree.rb', line 58

def postorder(node)
    if node == nil
        return
    end
    postorder(node.left)
    postorder(node.right)
    puts "#{node.data}"            
end

#preorder(node) ⇒ Object

print data in preorder form (root, left, right)



48
49
50
51
52
53
54
55
 
# File 'lib/binary_tree.rb', line 48

def preorder(node)
    if node == nil
        return
    end
    puts "#{node.data}"            
    preorder(node.left)
    preorder(node.right)
end

#test_binary_tree ⇒ Object

For test



68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/binary_tree.rb', line 68

def test_binary_tree
    for i in 1..5 do
        BinaryTree.new.insert(@@root, rand(100))
    end
    puts "inorder : "
    inorder(@root)
    puts "preorder : "
    preorder(@root)
    puts "postorder : "
    postorder(@root)
end