Stars: 545
Forks: 63
Pull Requests: 205
Issues: 19
Watchers: 13
Last Updated: 2023-09-14 11:28:18
A basic but flexible tree data structure for php and a fluent tree builder implementation.
License: MIT License
Languages: PHP, Makefile
In Tree you can find a basic but flexible tree data structure for php together with and an handful Builder class, that enables you to build tree in a fluent way.
The Tree\Node\NodeInterface
interface abstracts the concept of a tree node. In Tree
a Node has essentially two things:
a set of children (that implements the same NodeInterface
interface) and a value.
On the other hand, the Tree\Node\Node
gives a straight implementation for that interface.
use Tree\Node\Node;
$node = new Node('foo');
Each node has a value property, that can be any php value.
$node->setValue('my value');
echo $node->getValue(); //Prints 'my value'
$child1 = new Node('child1');
$child2 = new Node('child2');
$node
->addChild($child1)
->addChild($child2);
$node->removeChild($child1);
$children = $node->getChildren();
$node->setChildren([new Node('foo'), new Node('bar')]);
$node->removeAllChildren();
A leaf is a node with no children.
$node->isLeaf();
A child is a node that has a parent.
$node->isChild();
Reference to the parent node is automatically managed by child-modifiers methods
$root->addChild($node = new Node('child'));
$node->getParent(); // Returns $root
$root = (new Node('root'))
->addChild($child = new Node('child'))
->addChild($grandChild = new Node('grandchild'))
;
$grandchild->getAncestors(); // Returns [$root, $child]
getAncestorsAndSelf
retrieves ancestors of a node with the current node included.$root = $node->root();
$root = (new Node('root'))
->addChild($child1 = new Node('child1'))
->addChild($child2 = new Node('child2'))
->addChild($child3 = new Node('child3'))
;
$child2->getNeighbors(); // Returns [$child1, $child3]
getNeighborsAndSelf
retrieves neighbors of current node and the node itself.$node->getSize();
$node->getDepth();
$node->getHeight();
The builder provides a convenient way to build trees. It is provided by the Builder
class,
but you can implement your own builder making an implementation of the BuilderInterface
class.
Let's see how to build the following tree, where the nodes label are represents nodes values:
A
/ \
B C
/|\
D E F
/|
G H
And here is the code:
$builder = new Tree\Builder\NodeBuilder;
$builder
->value('A')
->leaf('B')
->tree('C')
->tree('D')
->leaf('G')
->leaf('H')
->end()
->leaf('E')
->leaf('F')
->end()
;
$nodeA = $builder->getNode();
The example should be self-explanatory, but here you are a brief description of the methods used above.
Set the value of the current node to $value
Add to the current node a new child whose value is $value
.
Add to the current node a new child whose value is $value
, and set the new node as the builder current node.
Returns to the context the builder was before the call to tree
method,
i.e. make the builder go one level up.
Returns the current node.
You can obtain the yield of a tree (i.e. the list of leaves in a pre-order traversal) using the YieldVisitor.
For example, if $node
is the tree built above, then
use Tree\Visitor\YieldVisitor;
$visitor = new YieldVisitor;
$yield = $node->accept($visitor);
// $yield will contain nodes B, G, H, E, F
You can walk a tree in pre-order:
use Tree\Visitor\PreOrderVisitor;
$visitor = new PreOrderVisitor;
$yield = $node->accept($visitor);
// $yield will contain nodes A, B, C, D, G, H, E, F
You can walk a tree in post-order:
use Tree\Visitor\PostOrderVisitor;
$visitor = new PostOrderVisitor;
$yield = $node->accept($visitor);
// $yield will contain nodes B, G, H, D, E, F, C, A
Run
$ composer require nicmart/tree
phpunit
Please have a look at CHANGELOG.md
.
Please have a look at CONTRIBUTING.md
.
This package is licensed using the MIT License.
Please have a look at LICENSE.md
.