Class: Tree::BinaryTreeNode

Inherits:
TreeNode show all
Defined in:
lib/tree/binarytree.rb

Overview

Provides a Binary tree implementation. This node allows only two child nodes (left and right child). It also provides direct access to the left or right child, including assignment to the same.

This inherits from the TreeNode class.

Author:

  • Anupam Sengupta

Core Attributes collapse

Attributes inherited from TreeNode

#content, #has_children?, #has_content?, #is_leaf?, #is_root?, #name, #parent, #parentage, #root

Attributes included from Utils::TreeMetricsHandler

#breadth, #depth, #in_degree, #length, #level, #node_depth, #node_height, #out_degree, #size

Structure Modification collapse

Methods inherited from TreeNode

#<<, #<=>, #[], #breadth_each, #children, #detached_copy, #detached_subtree_copy, #each, #each_leaf, #first_child, #first_sibling, #freeze_tree!, #initialize, #is_first_sibling?, #is_last_sibling?, #is_only_child?, #last_child, #last_sibling, #marshal_dump, #marshal_load, #next_sibling, #postordered_each, #preordered_each, #previous_sibling, #print_tree, #remove!, #remove_all!, #remove_from_parent!, #rename, #rename_child, #replace!, #replace_with, #siblings, #to_s

Methods included from Utils::HashConverter

included, #to_h

Methods included from Utils::TreeMergeHandler

#merge, #merge!

Methods included from Utils::JSONConverter

#as_json, included, #to_json

Methods included from Utils::CamelCaseMethodHandler

included

Methods included from Utils::TreePathHandler

included, #path_as_array, #path_as_string

Methods included from Utils::TreeMetricsHandler

included

Constructor Details

This class inherits a constructor from Tree::TreeNode

Dynamic Method Handling

This class handles dynamic methods through the method_missing method in the class Tree::Utils::CamelCaseMethodHandler

Instance Attribute Details

#is_left_child?Boolean

true if the receiver node is the left child of its parent. Always returns false if it is a root node.

Returns:

  • (Boolean)

    true if this is the left child of its parent.


86
87
88
89
# File 'lib/tree/binarytree.rb', line 86

def is_left_child?
  return false if is_root?
  self == parent.left_child
end

#is_right_child?Boolean (readonly)

true if the receiver node is the right child of its parent. Always returns false if it is a root node.

Returns:

  • (Boolean)

    true if this is the right child of its parent.


96
97
98
99
# File 'lib/tree/binarytree.rb', line 96

def is_right_child?
  return false if is_root?
  self == parent.right_child
end

#left_childTree::BinaryTreeNode

Left child of the receiver node. Note that left Child == first Child.

Returns:

See Also:


63
64
65
# File 'lib/tree/binarytree.rb', line 63

def left_child
  children.first
end

#right_childTree::BinaryTreeNode

Right child of the receiver node. Note that right child == last child unless there is only one child.

Returns nil if the right child does not exist.

Returns:

See Also:


77
78
79
# File 'lib/tree/binarytree.rb', line 77

def right_child
  children[1]
end

Instance Method Details

#add(child) ⇒ Object

Adds the specified child node to the receiver node. The child node's parent is set to be the receiver.

The child nodes are added in the order of addition, i.e., the first child added becomes the left node, and the second child added will be the second node.

If only one child is present, then this will be the left child.

Parameters:

Raises:

  • (ArgumentError)

    This exception is raised if two children are already present.


116
117
118
119
120
# File 'lib/tree/binarytree.rb', line 116

def add(child)
  raise ArgumentError, 'Already has two child nodes' if @children.size == 2

  super(child)
end

#add_from_hash(hashed_subtree) ⇒ Array

Instantiate and insert child nodes from data in a Ruby Hash

This method is used in conjunction with TreeNode.from_hash to provide a convenient way of building and inserting child nodes present in a Ruby hashes.

This method will instantiate a TreeNode instance for each top- level key of the input hash, to be inserted as children of the receiver instance.

Nested hashes are expected and further child nodes will be created and added accordingly. If a hash key is a single value that value will be used as the name for the node. If a hash key is an Array, both node name and content will be populated.

A leaf element of the tree should be represented as a hash key with corresponding value nil or {}.

>

Examples:

root = Tree::TreeNode.new(:A, "Root content!")
root.add_from_hash({:B => {:D => {}}, [:C, "C content!"] => {}})

Parameters:

  • hashed_subtree (Hash)

    The hash of child subtrees.

Returns:

  • (Array)

    Array of child nodes added

Raises:

  • (ArgumentError)

    This exception is raised if hash contains too many children.

  • (ArgumentError)

    This exception is raised if a non-hash is passed.


152
153
154
155
156
# File 'lib/tree/binarytree.rb', line 152

def add_from_hash(hashed_subtree)
  raise ArgumentError, 'Too many children'\
                       if hashed_subtree.size + @children.size > 2
  super(hashed_subtree)
end

#inordered_each(&block) {|node| ... } ⇒ Tree::BinaryTreeNode, Enumerator

Performs in-order traversal (including this node).

noinspection RubyUnusedLocalVariable

Parameters:

  • block (Object)

Yield Parameters:

Returns:

  • (Tree::BinaryTreeNode)

    This node, if a block is given

  • (Enumerator)

    An enumerator on this tree, if a block is not given

See Also:

Since:

  • 0.9.0


173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
# File 'lib/tree/binarytree.rb', line 173

def inordered_each(&block)

  return self.to_enum unless block_given?

  node_stack = []
  current_node = self

  until node_stack.empty? and current_node == nil
    if current_node
      node_stack.push(current_node)
      current_node = current_node.left_child
    else
      current_node = node_stack.pop
      yield current_node
      current_node = current_node.right_child
    end
  end

  self if block_given?

end

#swap_childrenObject

Swaps the left and right child nodes of the receiver node with each other.


247
248
249
# File 'lib/tree/binarytree.rb', line 247

def swap_children
  self.left_child, self.right_child = self.right_child, self.left_child
end