class Tree::BinaryTreeNode
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 {Tree::TreeNode} class.
@author Anupam Sengupta
Public Instance Methods
Source
# File lib/tree/binarytree.rb, line 119 def add(child) raise ArgumentError, 'Already has two child nodes' if @children.size == 2 super(child) end
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.
@param [Tree::BinaryTreeNode] child The child to add.
@raise [ArgumentError] This exception is raised if two children are
already present.
Tree::TreeNode#add
Source
# File lib/tree/binarytree.rb, line 154 def add_from_hash(hashed_subtree) raise ArgumentError, 'Too many children'\ if hashed_subtree.size + @children.size > 2 super(hashed_subtree) end
Instantiate and insert child nodes from data in a Ruby Hash
This method is used in conjunction with {Tree::TreeNode.from_hash} to provide a convenient way of building and inserting child nodes present in a Ruby hashes.
This method will instantiate a {Tree::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 {}.
@example
root = Tree::TreeNode.new(:A, "Root content!") root.add_from_hash({:B => {:D => {}}, [:C, "C content!"] => {}})
@param [Hash] hashed_subtree The hash of child subtrees.
@raise [ArgumentError] This exception is raised if hash contains too
many children.
>¶ ↑
@raise [ArgumentError] This exception is raised if a non-hash is passed. @return [Array] Array of child nodes added
Tree::Utils::HashConverter#add_from_hash
Source
# File lib/tree/binarytree.rb, line 174 def inordered_each return to_enum unless block_given? node_stack = [] current_node = self until node_stack.empty? && 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
Performs in-order traversal (including this node).
@yieldparam node [Tree::BinaryTreeNode] Each node (in-order).
@return [Tree::BinaryTreeNode] This node, if a block is given @return [Enumerator] An enumerator on this tree, if a block is not given
@since 0.9.0
@see each
@see preordered_each
@see postordered_each
noinspection RubyUnusedLocalVariable
Source
# File lib/tree/binarytree.rb, line 60 def left_child children.first end
@!attribute [rw] left_child
Left child of the receiver node. Note that left Child == first Child.
@return [Tree::BinaryTreeNode] The left most (or first) child.
@see right_child
Source
# File lib/tree/binarytree.rb, line 227 def left_child=(child) set_child_at child, 0 end
Sets the left child of the receiver node. If a previous child existed, it is replaced.
@param [Tree::BinaryTreeNode] child The child to add as the left-side
node.
@return [Tree::BinaryTreeNode] The assigned child node.
@see left_child
@see right_child=
Source
# File lib/tree/binarytree.rb, line 83 def left_child? return false if root? self == parent.left_child end
@!attribute left_child
? true
if the receiver node is the left child of its parent. Always returns false
if it is a root node.
@return [Boolean] true
if this is the left child of its parent.
Source
# File lib/tree/binarytree.rb, line 74 def right_child children[1] end
@!attribute [rw] right_child
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.
@return [Tree::BinaryTreeNode] The right child, or nil
if the right side
child does not exist.
@see left_child
Source
# File lib/tree/binarytree.rb, line 241 def right_child=(child) set_child_at child, 1 end
Sets the right child of the receiver node. If a previous child existed, it is replaced.
@param [Tree::BinaryTreeNode] child The child to add as the right-side
node.
@return [Tree::BinaryTreeNode] The assigned child node.
@see right_child
@see left_child=
Source
# File lib/tree/binarytree.rb, line 96 def right_child? return false if root? self == parent.right_child end
@!attribute [r] right_child
? true
if the receiver node is the right child of its parent. Always returns false
if it is a root node.
@return [Boolean] true
if this is the right child of its parent.
Source
# File lib/tree/binarytree.rb, line 246 def swap_children self.left_child, self.right_child = right_child, left_child end
Swaps the left and right child nodes of the receiver node with each other.
Protected Instance Methods
Source
# File lib/tree/binarytree.rb, line 205 def set_child_at(child, at_index) raise ArgumentError 'A binary tree cannot have more than two children.'\ unless (0..1).include? at_index @children[at_index] = child @children_hash[child.name] = child if child # Assign the name mapping child.parent = self if child child end
A protected method to allow insertion of child nodes at the specified location. Note that this method allows insertion of nil
nodes.
@param [Tree::BinaryTreeNode] child The child to add at the specified
location.
@param [Integer] at_index The location to add the entry at (0 or 1).
@return [Tree::BinaryTreeNode] The added child.
@raise [ArgumentError] If the index is out of limits.