Javascript实现树结构

叁歲伎倆 2022-08-21 07:55 170阅读 0赞

#####     #####

##### 树节点属性  Node #####

*     data：节点值
 *     parent ：指向节点的父节点
 *    children：指向节点的孩子节点

##### Tree 属性与方法 #####

*     \_root  ：树的根节点
 *    traverseDF(callback) ：深度遍历
 *   traverseBF(callback)：广度遍历

##### 树的实现 #####

##### 树节点定义： #####

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

##### 树的构造函数： #####

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

## 树的方法 ##

*  traverseDF(callback)
 *  traverseBF(callback)
 *  contains(data, traversal)
 *  add(child, parent)
 *  `remove(node, parent)`

1 of 5: `traverseDF(callback)`

Tree.prototype.traverseDF = function(callback) {
    			(function traverse(currentNode) {
    				var i,len;
    				var children = currentNode.children;
    				for(i=0,len = children.length;i<len;i++) {
    					traverse(children[i]);
    				}
    				callback(currentNode);
    			})(this._root);
    		    }

2 of 5: `traverseBF(callback)`

Tree.prototype.traverseBF = function(callback) {
    			var queue = [],
    			    i,
    			    len;
    			queue.push(this._root);
    			while(queue.length) {
    				var cur = queue.shift();
    				callback(cur);
    				for(i=0,len = cur.children.length; i < len;i++) {
    					queue.push(cur.children[i]);
    				}
    			}
    		}

3 of 5: `contains(callback, traversal)`

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

例如：

tree.contains(function(node){
                    if (node.data === 'two') {
                       console.log(node);
                    }
               }, tree.traverseBF);

4 of 5: `add(data, toData, traversal)`

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 an unexist parent');
    			}
    		}

5 of 5:  `remove(data, fromData, traversal)`

Tree.prototype.remove = function(data, fromData, traversal) {
    			var tree = this,
    				parent = null,
    				childToRemove = null,
    				i,len,children,
    				index;
    
    			var	callback = function(node) {
    					if(node.data === fromData) {
    						parent = node;
    					}
    				}
    			this.contains(callback, traversal);
    			if(parent) {
    				index = findIndex(parent.children, data);
    				console.log(index);
    				if(index === undefined) {
    					throw new Error("Node to remove does not exist");
    				}else {
    					childToRemove = parent.children.splice(index, 1);
    				}
    			}
    			console.log(childToRemove);
    			return childToRemove;
    		}

例如：

原文地址：http://code.tutsplus.com/articles/data-structures-with-javascript-tree--cms-23393