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