class AVLTree::BSTreeTraversal

Public Instance Methods

in_order_array(root_node, attribute = nil) click to toggle source
# File lib/ruby-avl/bs_tree_traversal.rb, line 12
def in_order_array(root_node, attribute = nil)
  in_order(root_node, attribute, [])
end
in_order_string(root_node, attribute = nil) click to toggle source
# File lib/ruby-avl/bs_tree_traversal.rb, line 16
def in_order_string(root_node, attribute = nil)
  in_order(root_node, attribute, []).join(', ')    
end
post_order_array(root_node, attribute = nil) click to toggle source
# File lib/ruby-avl/bs_tree_traversal.rb, line 20
def post_order_array(root_node, attribute = nil)
  post_order(root_node, attribute, [])
end
post_order_string(root_node, attribute = nil) click to toggle source
# File lib/ruby-avl/bs_tree_traversal.rb, line 24
def post_order_string(root_node, attribute = nil)
  post_order(root_node, attribute, []).join(', ')
end
pre_order_array(root_node, attribute = nil) click to toggle source
# File lib/ruby-avl/bs_tree_traversal.rb, line 4
def pre_order_array(root_node, attribute = nil)
  pre_order(root_node, attribute, [])
end
pre_order_string(root_node, attribute = nil) click to toggle source
# File lib/ruby-avl/bs_tree_traversal.rb, line 8
def pre_order_string(root_node, attribute = nil)
  pre_order(root_node, attribute, []).join(', ')
end

Private Instance Methods

in_order(node, attribute, node_list) click to toggle source

The idea of inorder traversal is that we visit the nodes in the order left-root-right, meaning for any subtree in the path, left node must be visited first followed by root and right node. Prints the values in ascending order. If attribute is set then it is called as a method on the data stored in the node, and that value is added to the array. If not, the data is added.

# File lib/ruby-avl/bs_tree_traversal.rb, line 49
def in_order(node, attribute, node_list)
  unless node.nil?
    in_order(node.left, attribute, node_list)
    node_list << (attribute ? node.data.send(attribute) : node.data)
    in_order(node.right, attribute, node_list)
  end
  return node_list
end
post_order(node, attribute, node_list) click to toggle source

The idea of postorder traversal is that we visit the nodes in the order left-right-root, meaning for any subtree in the path, left node must be visited first, followed by the right node, and root is not processed until the children are. If attribute is set then it is called as a method on the data stored in the node, and that value is added to the array. If not, the data is added.

# File lib/ruby-avl/bs_tree_traversal.rb, line 63
def post_order(node, attribute, node_list)
  unless node.nil?
    post_order(node.left, attribute, node_list)
    post_order(node.right, attribute, node_list)
    node_list << (attribute ? node.data.send(attribute) : node.data)
  end
  return node_list
end
pre_order(node, attribute, node_list) click to toggle source

The idea of preorder traversal is that we visit the nodes in the order root-left-right, meaning for any subtree in the path, root is processed as the node is visited, left node is visited second, followed by right node. If attribute is set then it is called as a method on the data stored in the node, and that value is added to the array. If not, the data is added.

# File lib/ruby-avl/bs_tree_traversal.rb, line 35
def pre_order(node, attribute, node_list)
  unless node.nil?
    node_list << (attribute ? node.data.send(attribute) : node.data)
    pre_order(node.left, attribute, node_list)
    pre_order(node.right, attribute, node_list)
  end
  return node_list
end