I try to express datastructures in a form of mathematical functions. For example an array or a dictionary is just a function to me.
Is there a good way to model a tree in terms of functions?
1
-
$\begingroup$ en.wikipedia.org/wiki/Abstract_data_type $\endgroup$– D.W. ♦Commented Feb 5, 2021 at 21:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A tree structure can be completely described by three functions:
- a function that given a node $x$ returns the number of children of that node,
- a function that given a node $x$ and index $i$ returns the $i$th child of that node, and
- a function that given a node $x$ returns an associated value $v$ stored at that node.
