Shulou(Shulou.com)05/31 Report--

This article mainly explains "javascript how to create a multi-tree", the content of the article is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "javascript how to create a multi-tree" bar!

1. Create a node

The data is stored as a node:

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

2. Create trees

Trees are used to connect nodes, like the trunk of a real-world tree, extending many branches.

Class MultiwayTree {constructor () {this._root = null;}}

3. Add a node

Function add (data, toData, traversal) {let node = new Node (data) / / the first time added to the root node / / the return value is this, so it is convenient to add the node if (this._root = null) {this._root = node; return this;} let parent = null, callback = function (node) {if (node.data = = toData) {parent = node; return true;}} / / find the parent node according to the traversal method (described later in the traversal method), and then add the node to the children array of the parent node / the lookup method contains will talk about this.contains (callback, traversal); if (parent) {parent.children.push (node); node.parent = parent; return this;} else {throw new Error ('Cannot add node to a non-existent parent.');}}

4. Depth first traversal

Depth priority will try to find it from the child node first, and then from the sibling node, which is suitable for cases with large data depth, such as file directory.

Function traverseDF (callback) {let stack = [], found = false; stack.unshift (this._root); let currentNode = stack.shift (); while (! found & & currentNode) {/ / decide whether to continue looking for found = callback (currentNode) = = true after finding the first one based on the return value of the callback function. True: false; if (! found) {/ / every time you put the child node at the top of the stack, the next search will find the child node stack.unshift (.. currentNode.children); currentNode = stack.shift ();}

5. Breadth-first traversal

Breadth first traversal will give priority to finding sibling nodes and looking down layer by layer, which is suitable for more sub-items, such as company position level.

Function traverseBF (callback) {let queue = [], found = false; queue.push (this._root); let currentNode = queue.shift (); while (! found & & currentNode) {/ / decide whether to continue looking for found = callback (currentNode) = = true after finding the first one based on the return value of the callback function. True: false; if (! found) {/ / each time the child node is placed at the end of the queue, the next search will first find the sibling node queue.push (... currentNode.children) currentNode = queue.shift ();}

6. Include nodes

Function contains (callback, traversal) {traversal.call (this, callback);}

The callback function algorithm can be implemented by itself according to the situation, and it has high flexibility.

7. Remove nodes

/ / return the removed node function remove (data, fromData, traversal) {let parent = null, childToRemove = null, callback = function (node) {if (node.data = fromData) {parent = node; return true;}}; this.contains (callback, traversal); if (parent) {let index = this._findIndex (parent.children, data) If (index < 0) {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;}

_ findIndex implementation:

Function _ findIndex (arr, data) {let index =-1; for (let I = 0, len = arr.length; I < len; iTunes +) {if (arr [I] .data = data) {index = I; break;}} return index;}

Complete algorithm

Class Node {constructor (data) {this.data = data; this.parent = null; this.children = [];}} class MultiwayTree {constructor () {this._root = null;} / / depth-first traversal traverseDF (callback) {let stack = [], found = false; stack.unshift (this._root); let currentNode = stack.shift () While (! found & & currentNode) {found = callback (currentNode) = true? True: false; if (! found) {stack.unshift (.. currentNode.children); currentNode = stack.shift ();} / / breadth-first traversal traverseBF (callback) {let queue = [], found = false; queue.push (this._root); let currentNode = queue.shift (); while (! found & & currentNode) {found = callback (currentNode) = = true? True: false; if (! found) {queue.push (... currentNode.children) currentNode = queue.shift ();} contains (callback, traversal) {traversal.call (this, callback);} add (data, toData, traversal) {let node = new Node (data) if (this._root = = null) {this._root = node; return this } let parent = null, callback = function (node) {if (node.data = toData) {parent = node; return true;}}; this.contains (callback, traversal); if (parent) {parent.children.push (node); node.parent = parent; return this } else {throw new Error ('Cannot add node to a non-existent parent.');}} remove (data, fromData, traversal) {let parent = null, childToRemove = null, callback = function (node) {if (node.data = = fromData) {parent = node; return true;}}; this.contains (callback, traversal) If (parent) {let index = this._findIndex (parent.children, data); if (index < 0) {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;} _ findIndex (arr, data) {let index =-1 For (let I = 0, len = arr.length; I < len; iTunes +) {if (arr [I] .data = data) {index = I; break;}} return index;}}

Console test code

Var tree = new MultiwayTree () Tree.add ('a') .add ('baked,' ajar, tree.traverseBF) .add ('cased,' ajar, tree.traverseBF) .add ('dashed,' axed, tree.traverseBF) .add ('eBay,' baked, tree.traverseBF) .add ('faded,' baked, tree.traverseBF) .add ('gelled,' clocked, tree.traverseBF) .add ('hacked,' c') Tree.traverseBF) .add ('iTunes,' dudes, tree.traverseBF) Console.group ('traverseDF'); tree.traverseDF (function (node) {console.log (node.data);}); console.groupEnd (' traverseDF'); console.group ('traverseBF'); tree.traverseBF (function (node) {console.log (node.data);}); console.groupEnd (' traverseBF'); / / depth first search console.group ('contains1'); tree.contains (function (node) {console.log (node.data)) If (node.data = ='f') {return true;}}, tree.traverseDF); console.groupEnd ('contains1') / / breadth first search console.group (' contains2'); tree.contains (function (node) {console.log (node.data); if (node.data ='f') {return true;}, tree.traverseBF); console.groupEnd ('contains2'); tree.remove (' gathers, 'cages, tree.traverseBF)

The running effect is as follows:

Thank you for your reading, the above is the content of "how to create a multi-tree in javascript". After the study of this article, I believe you have a deeper understanding of how to create a multi-tree in javascript, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.