A tree is a data structure consisting of a set of linked nodes that represent a hierarchical tree structure. Each node is linked to others via parent-children relationship. The first node in the tree is the root, whereas nodes without any children are the leaves.
Each node in a tree data structure must have the following properties:
key
: The key of the nodevalue
: The value of the nodeparent
: The parent of the node (null
if there is none)children
: An array of pointers to the node's childrenThe main operations of a tree data structure are:
insert
: Inserts a node as a child of the given parent noderemove
: Removes a node and its children from the treefind
: Retrieves a given nodepreOrderTraversal
: Traverses the tree by recursively traversing each node followed by its childrenpostOrderTraversal
: Traverses the tree by recursively traversing each node's children followed by the nodeclass TreeNode {
constructor(key, value = key, parent = null) {
this.key = key;
this.value = value;
this.parent = parent;
this.children = [];
}
get isLeaf() {
return this.children.length === 0;
}
get hasChildren() {
return !this.isLeaf;
}
}
class Tree {
constructor(key, value = key) {
this.root = new TreeNode(key, value);
}
*preOrderTraversal(node = this.root) {
yield node;
if (node.children.length) {
for (let child of node.children) {
yield* this.preOrderTraversal(child);
}
}
}
*postOrderTraversal(node = this.root) {
if (node.children.length) {
for (let child of node.children) {
yield* this.postOrderTraversal(child);
}
}
yield node;
}
insert(parentNodeKey, key, value = key) {
for (let node of this.preOrderTraversal()) {
if (node.key === parentNodeKey) {
node.children.push(new TreeNode(key, value, node));
return true;
}
}
return false;
}
remove(key) {
for (let node of this.preOrderTraversal()) {
const filtered = node.children.filter(c => c.key !== key);
if (filtered.length !== node.children.length) {
node.children = filtered;
return true;
}
}
return false;
}
find(key) {
for (let node of this.preOrderTraversal()) {
if (node.key === key) return node;
}
return undefined;
}
}
class
for the TreeNode
with a constructor
that initializes the appropriate key
, value
, parent
and children
properties.isLeaf
getter, that uses Array.prototype.length
to check if children
is empty.hasChildren
getter, that is the reverse of the isLeaf
getter.class
for the Tree
with a constructor
that initializes the root
of the tree.preOrderTraversal()
generator method that traverses the tree in pre-order, using the yield*
syntax to recursively delegate traversal to itself.postOrderTraversal()
generator method that traverses the tree in post-order, using the yield*
syntax to recursively delegate traversal to itself.insert()
method, that uses the preOrderTraversal()
method and Array.prototype.push()
to add a new TreeNode
to the tree.remove()
method, that uses the preOrderTraversal()
method and Array.prototype.filter()
to remove a TreeNode
from the tree.find()
method, that uses the preOrderTraversal()
method to retrieve the given node in the tree.const tree = new Tree(1, 'AB');
tree.insert(1, 11, 'AC');
tree.insert(1, 12, 'BC');
tree.insert(12, 121, 'BG');
[...tree.preOrderTraversal()].map(x => x.value);
// ['AB', 'AC', 'BC', 'BCG']
tree.root.value; // 'AB'
tree.root.hasChildren; // true
tree.find(12).isLeaf; // false
tree.find(121).isLeaf; // true
tree.find(121).parent.value; // 'BC'
tree.remove(12);
[...tree.postOrderTraversal()].map(x => x.value);
// ['AC', 'AB']
JavaScript, Object
A binary tree is a data structure consisting of a set of linked nodes representing a hierarchical tree structure, in which each node can have at most two children.
JavaScript, Object
A binary search tree is a data structure consisting of a set of ordered linked nodes representing a hierarchical tree structure, in which each node can have at most two children.
JavaScript, Object
A graph is a data structure consisting of a set of vertices connected by a set of edges.