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

def inorder(node)
  return if node == nil
  inorder(node.left)
  print "#{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

#levelorder(node) ⇒ Object

level order tree traversal



85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/binary_tree.rb', line 85

def levelorder(node)
  return if node == nil
  q = []
  q.push(node)
  while(!q.empty?)
    node = q.shift
    if node.left != nil
      q.push(node.left)
    end
    if node.right != nil
      q.push(node.right)
    end
    print "#{node.data} "
  end
end

#postorder(node) ⇒ Object

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



54
55
56
57
58
59
 
# File 'lib/binary_tree.rb', line 54

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

#postorder_iterative(node) ⇒ Object

Postorder traversal using two stack in binary tree



62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/binary_tree.rb', line 62

def postorder_iterative(node)
  return if node == nil
  s1 = []
  s2 = []
  s1.push(node)
  while(!s1.empty?)
    node = s1.pop    
    s2.push(node)
    if node.left != nil
      s1.push(node.left)
    end
    if node.right != nil
      s1.push(node.right)
    end
  end 
  while(!s2.empty?)
    node = s2.pop
    print "#{node.data} "
  end
  puts ""
end

#preorder(node) ⇒ Object

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



46
47
48
49
50
51
 
# File 'lib/binary_tree.rb', line 46

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

#test_binary_tree ⇒ Object

For test



102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/binary_tree.rb', line 102

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