class BinaryTree
Attributes
data[R]
left[RW]
right[RW]
root[RW]
Public Class Methods
new(data=nil)
click to toggle source
# File lib/binary_tree.rb, line 5 def initialize(data=nil) @data = data @left = nil @right = nil end
Public Instance Methods
inorder(node)
click to toggle source
print data in inorder form (left, root, right)
# 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)
click to toggle source
insert data in binary tree node
# 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)
click to toggle source
level order tree traversal
# 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)
click to toggle source
print data in postorder for (left, right, root)
# 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)
click to toggle source
Postorder traversal using two stack in binary tree
# 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)
click to toggle source
print data in preorder form (root, left, right)
# 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()
click to toggle source
For test
# 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