A tree organizes data into nodes linked by parent-child relationships. One node serves as the root; each branch repeats the same structure, making recursion a natural way to process the whole hierarchy. section 3.5
A JavaScript tree
A Node stores a value, a parent, and an array of children. append connects a child to its parent, so a hierarchy can be assembled fluently: church.append(rosser).append(turing).append(kleene); kleene.append(nelson).append(constable); rosser.append(mendelson).append(sacks); turing.append(gandy). Tree.map can then recursively apply a function to every node, such as Tree.map(church, p => p.fullname). section 3.5
A recursive tree operation follows a simple pattern:
- Process the current node. section 3.5
- Apply the same operation to each child. section 3.5
- Stop when a node has no children. section 3.5
class Tree {
constructor(root) {
this._root = root;
}
static map(node, fn, tree = null) { #1
node.value = fn(node.value); #2
if(tree === null) {
tree = new Tree(node); #3
}
if(node.hasChildren()) { #4
_.map(node.children, function (child) { #5
Tree.map(child, fn, tree); #6
});
}
return tree;
}
get root() {
return this._root;
}
}
Inspect the recursive Tree.map implementation, which transforms a node and descends through its children. section 3.5
