This Python package contains a few abstract base classes for tree data structures.
Trees are very common data structure that represents a hierarchy of common nodes.
This package defines abstract base classes for these data structure in order to make code reusable.
Abstract base classes
from abstracttree import to_mermaid
to_mermaid(AbstractTree)
graph TD;
AbstractTree[AbstractTree];
UpTree[UpTree];
Tree[Tree];
MutableTree[MutableTree];
DownTree[DownTree];
Tree[Tree];
MutableTree[MutableTree];
MutableDownTree[MutableDownTree];
MutableTree[MutableTree];
BinaryDownTree[BinaryDownTree]
BinaryTree[BinaryTree]
AbstractTree-->UpTree;
UpTree-->Tree;
Tree-->MutableTree;
AbstractTree-->DownTree;
DownTree-->Tree;
DownTree-->MutableDownTree;
MutableDownTree-->MutableTree;
DownTree-->BinaryDownTree
BinaryDownTree-->BinaryTree
Tree-->BinaryTree
Downtrees are trees that have links to their direct children.
Uptrees are trees that link to their parent.
A Tree has links in both directions.
ABC | Inherits from | Abstract Methods | Mixin Methods |
---|
AbstractTree | | | nid , eqv() |
UpTree | AbstractTree | parent | root , is_root , ancestors , path |
DownTree | AbstractTree | children | nodes , descendants , leaves , levels , is_leaf , transform() , nodes.preorder() , nodes.postorder() , nodes.levelorder() |
Tree | UpTree , DownTree | | siblings |
MutableDownTree | DownTree | add_child() , remove_child() | add_children() |
MutableTree | Tree , MutableDownTree | | detach() |
BinaryDownTree | DownTree | left_child , right_child | children , nodes.inorder() , descendants.inorder() |
BinaryTree | BinaryDownTree , Tree | | |
In your own code, you can inherit from these trees.
For example, if your tree only has links to children:
import abstracttree
from abstracttree import print_tree
class MyTree(abstracttree.DownTree):
def __init__(self, value, children=()):
self.value = value
self._children = children
def __str__(self):
return "MyTree " + str(self.value)
@property
def children(self):
return self._children
tree = MyTree(1, children=[MyTree(2), MyTree(3)])
print_tree(tree)
Adapter
In practice, not all existing tree data structures implement one of these abstract classes.
As a bridge, you can use astree
to convert these trees to a Tree
instance.
However, whenever possible, it's recommended to inherit from Tree
directly for minimal overhead.
Examples:
astree(int)
astree(ast.parse("1 + 1 == 2"))
astree(pathlib.Path("abstracttree"))
astree(anytree.Node())
astree([[1, 2, 3], [4, 5, 6]])
data = {"name": "a",
"children": [
{"name": "b", "children": []},
{"name": "c", "children": []}
]}
astree(data, children=operator.itemgetter["children"])
astree(widget, children=lambda w: w.children(), parent = lambda w: w.parent())
astree(tree.root, children=lambda nid: tree.children(nid), parent=lambda nid: tree.parent(nid))
astree(tree, children=iter, parent=lambda t: t.parent)
inf_binary = astree(0, children=lambda n: (2*n + 1, 2*n + 2))
Utility functions
Pretty printing
tree = astree(seq, children=lambda x: [x[:-2], x[1:]] if x else [])
print_tree(tree)
print(to_string(tree))
Plotting with matplotlib
import matplotlib.pyplot as plt
expr = ast.parse("y = x*x + 1")
plot_tree(expr)
plt.show()
Export to various formats
to_dot(tree)
to_mermaid(tree)
to_latex(tree)
to_image(Path('.'), "filetree.png", how="dot")
to_image(AbstractTree, "class_hierarchy.svg", how="mermaid")
to_pillow(tree).show()
Find distance between nodes
import heapq
from abstracttree import HeapTree, Route
tree = HeapTree([5, 4, 3, 2, 1])
heapq.heapify(tree.heap)
left_child = tree.children[0]
right_child = tree.children[1]
route = Route(left_child, right_child)
print(f"{route.lca = }")
print(f"{route.nodes.count() = }")
print(f"{route.edges.count() = }")
A few concrete tree implementations
Tree visualisation