JavaScript data structure: tree

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

Each instance of Node contains three attributes, data, parent and children. The first property holds data related to this node, such as "village head". The second attribute points to a node (in js, the equals sign, such as this.parent = someOtherNode, which implements the pointer, okay). What value transfer will be expanded in detail. Pointer implementations in other algorithms are similar.

function Tree(data) {
    var node = new Node(data);
    this._root = node;
}

Tree contains two lines of code, the first line creates an instance node of Node, and the second line assigns the node to this._root. It initializes a tree and gives it a root node.
Definitions of Tree and Node require very little code, but that code is enough to simulate a hierarchical data structure. To illustrate this, we can create instances of Tree (indirectly, Node) with a little test data:

var tree = new Tree('CEO');


tree._root;
// Return {data:'CEO', parent: null, children: []}

In the presence of parents and children, we can add nodes to the child nodes of _root, and assign the parent nodes of these child nodes to _root.

Tree Method

Next, we add the following five methods to the tree:

Tree

1. traverseDF(callback)

2. traverseBF(callback)

3. contains(data,traversal)

4. add(child,parent)

5. remove(node,parent)

These methods all need to traverse the tree. We first implement the traversal methods.

First: traverseDF(callback)

Tree depth-first traversal:

Tree.prototype.traverseDF = function(callback) {

    // A recursive, immediate execution function
    (function recurse(currentNode) {
        // Step 2
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // Step 3
            recurse(currentNode.children[i]);
        }

        // Step 4
        callback(currentNode);

        // First execute
    })(this._root);

};

traverseDF(callback) has a callback parameter. As the name implies, callback is a function that will be called later in traverseDF(callback).

The traverseDF(callback) contains a function called recurse. Recurse means recursion. It's a recursive function. In other words, it calls itself and ends automatically (under certain conditions). Notice step * in the code comment above, and I'll use them to describe how the recurse function traverses the entire tree:

1. First, execute: recurse, with the root node of the tree as the parameter. At this point, currentNode points to the root node.

2. Step 2: Enter a for loop and iterate over each child of current Node (e.g., root node), starting with the first.

3. Step 3: Within the for loop, call recurse and refer to a child node of currentNode. Which child node depends on the iteration of the for loop.

4. Step 4: When currentNode has no more children, exit the for loop and call the callback function passed in when traverseDf(callback) is called.

The second step (self-termination), the third step (self-invocation), and the fourth step (callback function) are repeated until we traverse all the nodes of the tree.

A complete description of recursion requires an entire article, which is beyond the scope of this article. Readers can experiment with the above traverse DF (callback) to try to understand how it works.

The following example illustrates how a tree is traversed by traverse DF (callback).
First, we create a tree to traverse. The following method is not good, but it can play an illustrative role. The ideal way is to use the add(value) that will be implemented later in Part 4.

/*

Build a tree with the following structure

one
├── two
│   ├── five
│   └── six
├── three
└── four
    └── seven

*/

var tree = new Tree('one');

tree._root.children.push(new Node('two'));
tree._root.children[0].parent = tree;

tree._root.children.push(new Node('three'));
tree._root.children[1].parent = tree;

tree._root.children.push(new Node('four'));
tree._root.children[2].parent = tree;

tree._root.children[0].children.push(new Node('five'));
tree._root.children[0].children[0].parent = tree._root.children[0];

tree._root.children[0].children.push(new Node('six'));
tree._root.children[0].children[1].parent = tree._root.children[0];

tree._root.children[2].children.push(new Node('seven'));
tree._root.children[2].children[0].parent = tree._root.children[2];

Then we call traverseDF(callback):

tree.traverseDF(function(node) {
    console.log(node.data)
});
/*

logs the following strings to the console(That won't turn over.

'five'
'six'
'two'
'three'
'seven'
'four'
'one'

*/

Second: traverse BF (callback)

This method is used for breadth-first traversal.
Depth-first and width-first traversal orders are different. We use the tree used in traverse BF (callback) to prove this:

/*

 tree

 one (depth: 0)
 ├── two (depth: 1)
 │   ├── five (depth: 2)
 │   └── six (depth: 2)
 ├── three (depth: 1)
 └── four (depth: 1)
     └── seven (depth: 2)

 */

Then the same callback function is passed in:

tree.traverseBF(function(node) {
    console.log(node.data)
});

/*

logs the following strings to the console

'one'
'two'
'three'
'four'
'five'
'six'
'seven'

*/

The above log and tree structures have illustrated the breadth-first traversal pattern. Start at the root node, then go down to the next layer, traversing all the nodes in this layer from left to right. Repeat until you reach the bottom.

Now that we have the concept, let's implement the code:

Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();

    queue.enqueue(this._root);

    currentNode = queue.dequeue();

    while(currentNode){
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            queue.enqueue(currentNode.children[i]);
        }

        callback(currentNode);
        currentNode = queue.dequeue();
    }
};

The definition of traverse BF (callback) contains a lot of logic, and the author explains a lot here. I don't feel helpful in understanding the code.
Trying to explain, the root node calculates the first level:

1. Starting from the root node, currentNode is the root node at this time.

2. For the first time, while traverses all the child nodes of current Node to advance the queue. (By this time the second tier has traversed, and will be executed in turn in the while loop, first in first out)

   1. Execute the callback function and pass in currentNode.

   2. CurrtNode is assigned to the first child node in the second layer.

3. Second while: For current Node, all the children of the first child node in the second layer are traversed and pushed into the queue. Note that this is the first part of the third floor.

   1. Execute the callback function and pass in currentNode.

   2. CurrtNode is assigned to the second child node in the second layer.

4. Third while: For currentNode, all the children of the second child node in the second layer are traversed and pushed into the queue. Note that this is the second part of the third floor.

   1. Execute the callback function and pass in currentNode.

   2. CurrtNode is assigned to the third child node of the second layer.

5. Last few while
   At this time, there is no next layer. It will not enter the for loop. It is right to pass the remaining nodes in the queue to the callback function in turn.

So it's clear.

Third: contains(callback,traversal)

This method is used to search for a specific value in the tree. In order to use the two traversals we defined earlier, include (callback, traversal) can accept two parameters, the value to be found, and the traversal to be performed.

Tree.prototype.contains = function(callback, traversal) {
    traversal.call(this, callback);
};

The first parameter of the call method binds traversal to the tree where contains(callback,traversal) is called, and the second parameter is a function called on each node.
The following function is understood by all of you, and I feel that the original author's explanation is contrary.

// tree is an example of a root node
tree.contains(function(node){
    if (node.data === 'two') {
        console.log(node);
    }
}, tree.traverseBF);

Fourth: add(data, toData, traversal)

Now we'll find another way to add it.

Tree.prototype.add = function(data, toData, traversal) {
    //Instance of a node
    var child = new Node(data),
        parent = null,
        //Looking for Dad Function
        callback = function(node) {
            if (node.data === toData) {
                parent = node;
            }
        };
        //Executing the Father Finding Function in some way
    this.contains(callback, traversal);
    //Did you find it?
    if (parent) {
      //Find it, take it, confess to your father
        parent.children.push(child);
        child.parent = parent;
    } else {
      //No, wrong: No dad.
        throw new Error('Cannot add node to a non-existent parent.');
    }
};

The annotations are clear.

var tree = new Tree('CEO');

tree.add('VP of Happiness', 'CEO', tree.traverseBF);

/*

our tree

'CEO'
└── 'VP of Happiness'

*/

var tree = new Tree('CEO');

tree.add('VP of Happiness', 'CEO', tree.traverseBF);
tree.add('VP of Finance', 'CEO', tree.traverseBF);
tree.add('VP of Sadness', 'CEO', tree.traverseBF);

tree.add('Director of Puppies', 'VP of Finance', tree.traverseBF);
tree.add('Manager of Puppies', 'Director of Puppies', tree.traverseBF);

/*

 tree

 'CEO'
 ├── 'VP of Happiness'
 ├── 'VP of Finance'
 │   ├── 'Director of Puppies'
 │   └── 'Manager of Puppies'
 └── 'VP of Sadness'

 */

Fifth: remove(data, fromData, traversal)

Similarly, the deletion method:

Tree.prototype.remove = function(data, fromData, traversal) {
    var tree = this,
        parent = null,
        childToRemove = null,
        index;
        //Because it is to delete a value under a certain data, we first define looking for a dad.
    var callback = function(node) {
        if (node.data === fromData) {
            parent = node;
        }
    };
      //Look for Dad in some way
    this.contains(callback, traversal);
      //Does Dad exist?
    if (parent) {
        //Existence, the ranking of dolls
        index = findIndex(parent.children, data);
        //Have you found it?
        if (index === undefined) {
          //My sister is looking for it.
            throw new Error('Node to remove does not exist.');
        } else {
          //Find it, kill it, raise your head.
            childToRemove = parent.children.splice(index, 1);
        }
    } else {
      //Daddy does not exist, report a mistake
        throw new Error('Parent does not exist.');
    }
    //Take the lead in handing over errors
    return childToRemove;
};

function findIndex(arr, data) {
    var index;
    //Traversing through a data daddy's doll, if equal, returns the doll's ranking, otherwise the returned index equals undefined
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }

    return index;
}

At the end of the paper, the author releases a family photo:

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

function Tree(data) {
    var node = new Node(data);
    this._root = node;
}

Tree.prototype.traverseDF = function(callback) {

    // this is a recurse and immediately-invoking function
    (function recurse(currentNode) {
        // step 2
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // step 3
            recurse(currentNode.children[i]);
        }

        // step 4
        callback(currentNode);

        // step 1
    })(this._root);

};

Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();

    queue.enqueue(this._root);

    currentTree = queue.dequeue();

    while(currentTree){
        for (var i = 0, length = currentTree.children.length; i < length; i++) {
            queue.enqueue(currentTree.children[i]);
        }

        callback(currentTree);
        currentTree = queue.dequeue();
    }
};

Tree.prototype.contains = function(callback, traversal) {
    traversal.call(this, callback);
};

Tree.prototype.add = function(data, toData, traversal) {
    var child = new Node(data),
        parent = null,
        callback = function(node) {
            if (node.data === toData) {
                parent = node;
            }
        };

    this.contains(callback, traversal);

    if (parent) {
        parent.children.push(child);
        child.parent = parent;
    } else {
        throw new Error('Cannot add node to a non-existent parent.');
    }
};

Tree.prototype.remove = function(data, fromData, traversal) {
    var tree = this,
        parent = null,
        childToRemove = null,
        index;

    var callback = function(node) {
        if (node.data === fromData) {
            parent = node;
        }
    };

    this.contains(callback, traversal);

    if (parent) {
        index = findIndex(parent.children, data);

        if (index === undefined) {
            throw new Error('Node to remove does not exist.');
        } else {
            childToRemove = parent.children.splice(index, 1);
        }
    } else {
        throw new Error('Parent does not exist.');
    }

    return childToRemove;
};

function findIndex(arr, data) {
    var index;

    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }

    return index;
}