KO | EN

GitLite

Minimalist Open Source Repository Search Engine

gitlite — search

#developer-tools #typescript #claude-code #codex #dsh #dsh-plugin #ai-agent #ai-agents #deepseek-harness #agent-skills #macos #cli

phptree

★ 98 Open GitHub ↗

An implementation of tree data structure

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

[![Latest Stable Version][latest stable version]][1]
 [![GitHub stars][github stars]][1]
 [![Total Downloads][total downloads]][1]
 [![GitHub Workflow Status][github workflow status]][2]
 [![Scrutinizer code quality][code quality]][3]
 [![Type Coverage][type coverage]][4]
 [![Code Coverage][code coverage]][3]
 [![Mutation testing badge][mutation badge url]][mutation badge link]
 [![License][license]][1]
 [![Donate!][donate github]][5]

# PhpTree

## Description

A PHP implementation of tree data structure.

It provides different trees implementations:
* **Node**: The base class.
* **N-ary node**: (or K-ary tree) extends the base class and allows you to specify the capacity of a node, the maximum children a node can have.
* **Value node**: extends the N-ary node and allows you to attach a value to the node.
* **KeyValue node**: extends the Value node and allows you to attach a key and a value to the node.
* **Trie node**: extends the KeyValue node, a simple [Trie tree](https://en.wikipedia.org/wiki/Trie).
* **Auto-balanced node**: extends the N-ary node and tries to keep the tree as symetric as possible. It automatically balance all the children as soon as they are added.
* **Merkle node**: a tree in which every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.

[4 trees traversal algorithms](https://en.wikipedia.org/wiki/Tree_traversal):
* **In order**
* **Post order**
* **Pre order**
* **Breadth first**

Exporters and importers:
* **Ascii**: Export a tree into an ascii graphic, just for swag and visualisation fun.
* **Graph**: Export a tree into a Graph using the [graphp/graphp](https://github.com/graphp/graph) library.
* **GraphViz**: Export a tree into a script in [GraphViz](http://www.graphviz.org/) format.
* **Text**: Export a tree into a simple string, easy for storing in a database.
* **nikic/php-ast**: Import a tree from an AST generated by the PHP extension [AST](https://github.com/nikic/php-ast).
* **nikic/php-parser**: Import a tree from an AST generated by [nikic/php-parser](https://github.com/nikic/php-parser).
* **microsoft/tolerant-php-parser**: Import a tree from an AST generated by [microsoft/tolerant-php-parser](https://github.com/microsoft/tolerant-php-parser).

Modifier:
* **Reverse**: To reverse a tree, all the children are mirrored.

## Documentation

Blog post: [https://not-a-number.io/2018/phptree-a-fast-tree-implementation](https://not-a-number.io/2018/phptree-a-fast-tree-implementation)

## Changelog

See [CHANGELOG.MD][phptree changelog]

## Requirements

* PHP >= 7.1

## Installation

```composer require loophp/phptree```

## Optional packages

* [drupol/launcher](https://github.com/drupol/launcher): To automatically open a resource using the proper application on your operating system.
* [graphp/graphp](https://github.com/graphp/graph): To export a tree into a Graph.

## Usage

```php
<?php

declare(strict_types = 1);

use loophp\phptree\Exporter\Gv;
use loophp\phptree\Exporter\Image;
use loophp\phptree\Node\ValueNode;
use loophp\phptree\Exporter\Text;
use loophp\launcher\Launcher;

include './vendor/autoload.php';

// Create the root node.
$tree = new ValueNode('root', 2);

$nodes = [];
foreach (\range('A', 'Z') as $v) {
    $nodes[] = new ValueNode($v, 2);
}

// Add children to the root node.
$tree->add(...$nodes);

// Export to text.
$textExporter = new Text();
$textExporter->export($tree); // [root[A[C[G[O][P]][H[Q][R]]][D[I[S][T]][J[U][V]]]][B[E[K[W][X]][L[Y][Z]]][F[M][N]]]]⏎

// Export to a GraphViz script with the Gv exporter
$graphvizExporter = new Gv();
$dotScript = $graphvizExporter->export($tree);
file_put_contents('tree.dot', $dotScript);
// Then do "dot -Tsvg tree.dot -o tree.svg" to export in SVG.

// Or use the Image exporter that does it for you.
$imageExporter = new Image();
$imageContent = $imageExporter->setFormat('png')->export($tree);
file_put_contents('tree.png', $imageContent);

// If you want to launch the image, you can use an optional package.
// do: composer require drupol/launcher
// then:
Launcher::open('tree.png');
```

## Code quality, tests and benchmarks

Every time changes are introduced into the library, [Github](https://github.com/loophp/phptree/actions) run the tests and the benchmarks.

The library has tests written with [PHPSpec](http://www.phpspec.net/).
Feel free to check them out in the `spec` directory. Run `composer phpspec` to trigger the tests.

Before each commit some inspections are executed with [GrumPHP](https://github.com/phpro/grumphp), run `./vendor/bin/grumphp run` to check manually.

[PHPBench](https://github.com/phpbench/phpbench) is used to benchmark the library, to run the benchmarks: `composer bench`

[PHPInfection](https://github.com/infection/infection) is used to ensure that your code is properly tested, run `composer infection` to test your code.

## Contributing

Feel free to contribute by sending pull requests. We are a
usually very responsive team and we will help you going
through your pull request from the beginning to the end.

For some reasons, if you can't contribute to the code and
willing to help, sponsoring is a good, sound and safe way
to show us some gratitude for the hours we invested in this
package.

Sponsor me on [Github][5] and/or any of [the contributors][6].

## Changelog

See [CHANGELOG.md][43] for a changelog based on [git commits][44].

For more detailed changelogs, please check [the release changelogs][45].

[phptree changelog]: https://github.com/loophp/phptree/blob/master/CHANGELOG.md
[1]: https://packagist.org/packages/loophp/phptree
[2]: https://github.com/loophp/phptree/actions
[latest stable version]: https://img.shields.io/packagist/v/loophp/phptree.svg?style=flat-square
[github stars]: https://img.shields.io/github/stars/loophp/phptree.svg?style=flat-square
[total downloads]: https://img.shields.io/packagist/dt/loophp/phptree.svg?style=flat-square
[github workflow status]: https://img.shields.io/github/workflow/status/loophp/phptree/Unit%20tests?style=flat-square
[code quality]: https://img.shields.io/scrutinizer/quality/g/loophp/phptree/master.svg?style=flat-square
[3]: https://scrutinizer-ci.com/g/loophp/phptree/?branch=master
[type coverage]: https://img.shields.io/badge/dynamic/json?style=flat-square&color=color&label=Type%20coverage&query=message&url=https%3A%2F%2Fshepherd.dev%2Fgithub%2Floophp%2Fphptree%2Fcoverage
[4]: https://shepherd.dev/github/loophp/phptree
[5]: https://github.com/sponsors/drupol
[6]: https://github.com/loophp/phptree/graphs/contributors
[code coverage]: https://img.shields.io/scrutinizer/coverage/g/loophp/phptree/master.svg?style=flat-square
[license]: https://img.shields.io/packagist/l/loophp/phptree.svg?style=flat-square
[donate github]: https://img.shields.io/badge/Sponsor-Github-brightgreen.svg?style=flat-square
[donate paypal]: https://img.shields.io/badge/Sponsor-Paypal-brightgreen.svg?style=flat-square
[mutation badge url]: https://img.shields.io/endpoint?style=flat-square&url=https%3A%2F%2Fbadge-api.stryker-mutator.io%2Fgithub.com%2Floophp%2Fphptree%2Fmaster
[mutation badge link]: https://dashboard.stryker-mutator.io/reports/github.com/loophp/phptree/master
[43]: https://github.com/loophp/phptree/blob/master/CHANGELOG.md
[44]: https://github.com/loophp/phptree/commits/master
[45]: https://github.com/loophp/phptree/releases

phptree

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README