philiprehberger-tree
Generic tree data structure with traversal, search, and serialization
Requirements
- Ruby >= 3.1
Installation
Add to your Gemfile:
gem "philiprehberger-tree"Or install directly:
gem install philiprehberger-treeUsage
require "philiprehberger/tree"
root = Philiprehberger::Tree::Node.new('root')
child = root.add_child('child')
child.add_child('grandchild')
root.size # => 3
root.height # => 2
root.leaf? # => false
child.depth # => 1Traversal
root.each_dfs { |node| puts node.value } # depth-first pre-order
root.each_bfs { |node| puts node.value } # breadth-first
root.each_post_order { |node| puts node.value } # depth-first post-orderSearch and Path Finding
node = root.find { |n| n.value == 'grandchild' }
path = root.path_to('grandchild')
path.map(&:value) # => ['root', 'child', 'grandchild']Serialization
root.to_h
# => { value: 'root', children: [{ value: 'child', children: [...] }] }
puts root.print_tree
# root
# └── child
# └── grandchildSubtree Extraction
copy = child.subtree # deep copy, detached from parent
copy.parent # => nilEquality
tree1 = Philiprehberger::Tree::Node.new('a')
tree2 = Philiprehberger::Tree::Node.new('a')
tree1 == tree2 # => true (structural equality)Ancestors and Siblings
grandchild.ancestors.map(&:value) # => ['child', 'root']
child.siblings.map(&:value) # => ['other_child']Leaf Collection
root.leaves.map(&:value) # => ['grandchild']API
Node
| Method | Description |
|---|---|
.new(value) |
Create a new tree node |
#add_child(value) |
Add a child node and return it |
#remove_child(value) |
Remove a child by value |
#children |
Array of child nodes |
#parent |
Parent node or nil |
#root? |
True if node has no parent |
#leaf? |
True if node has no children |
#depth |
Distance from root |
#height |
Height of subtree |
#size |
Total nodes in subtree |
#each_dfs |
Depth-first pre-order iteration |
#each_bfs |
Breadth-first iteration |
#each_post_order |
Depth-first post-order iteration |
#find { |n| } |
Find first node matching predicate |
#path_to(value) |
Array of nodes from root to target |
#leaves |
All leaf nodes in subtree |
#subtree |
Deep copy of node and descendants |
#== |
Structural equality comparison |
#ancestors |
Array of ancestors from parent to root |
#siblings |
Sibling nodes excluding self |
#to_h |
Serialize subtree to hash |
#print_tree |
Visual string representation |
Development
bundle install
bundle exec rspec
bundle exec rubocopSupport
If you find this project useful: