Class: BinaryTree

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

Constant Summary collapse

@@root = 
nil

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

Instance Method Details

#inorder(node) ⇒ Object

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



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

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
 
# File 'lib/binary_tree.rb', line 12

def insert(node, data)
    q = []
    if node == nil
        @@root = BinaryTree.new(data)
        return
    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
end

#postorder(node) ⇒ Object

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



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

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)



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

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

#test_binary_tree ⇒ Object 



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

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