项目中再一次遇到一个需求，需要遍历一个树形数据结构里的某一个节点，然后删除。感觉类似的逻辑已经写过n的n次方次了。所以这次打算封装一个通用场景下，对树形数据结构的遍历函数。本着封装新功能前，先去github上搜刮的原则，我找到了本文的猪脚 tree-crawl。
| 项目名称 | tree-crawl |
|---|---|
| 项目地址 | https://github.com/ngryman/tree-crawl |
| cnpm地址 | https://npm.taobao.org/package/tree-crawl |
| npm地址 | https://www.npmjs.com/package/tree-crawl |
之所以要提供npm地址，是由于github上的项目本人编译了好几次，都没有成功的找到dist目录。所以源文件需要通过 npm i tree-crawl然后去/dist目录里去找。
这里是官网缺失的/dist目录的内容
-
发现提供的这两个文件在某些webapck下会import失败。直接看最底下源码
-
下面是对官网文档稍作补充
-
假如要遍历的数据结构是这样的
const list = [ { name:"刘荣华" }, { name:"张四", subs:[ { name:"张思毅", subs:[ { name:"张陀螺" } ] } ] } ]- 那么应该以这种形式传入
crawl( {subs:list}, (node,context)=>{ console.log(node.name) }, { getChildren: node => node.subs } ) //输出一个undefiined以及所有name //可以猜测一下这个undefined是怎么来的
-
- 附官网api
import crawl from 'tree-crawl'
// traverse the tree in pre-order
crawl(tree, console.log)
crawl(tree, console.log, { order: 'pre' })
// traverse the tree in post-order
crawl(tree, console.log, { order: 'post' })
// traverse the tree using `childNodes` as the children key
crawl(tree, console.log, { getChildren: node => node.childNodes })
// skip a node and its children
crawl(tree, (node, context) => {
if ('foo' === node.type) {
context.skip()
}
})
// stop the walk
crawl(tree, (node, context) => {
if ('foo' === node.type) {
context.break()
}
})
// remove a node
crawl(tree, (node, context) => {
if ('foo' === node.type) {
context.parent.children.splice(context.index, 1)
context.remove()
}
})
// replace a node
crawl(tree, (node, context) => {
if ('foo' === node.type) {
const node = {
type: 'new node',
children: [
{ type: 'new leaf' }
]
}
context.parent.children[context.index] = node
context.replace(node)
}
})
//发现提供的官方/dist在webpack项目下会import失败，没办法，贴源码
function Context(flags, cursor) {
this.flags = flags;
this.cursor = cursor;
}
Context.prototype = {
skip: function skip() {
this.flags.skip = true;
},
break: function _break() {
this.flags.break = true;
},
remove: function remove() {
this.flags.remove = true;
},
replace: function replace(node) {
this.flags.replace = node;
},
get parent() {
return this.cursor.parent;
},
get depth() {
return this.cursor.depth;
},
get level() {
return this.cursor.depth + 1;
},
get index() {
return this.cursor.index;
}
};
function ContextFactory(flags, cursor) {
return new Context(flags, cursor);
}
function Stack(initial) {
this.xs = [initial];
this.top = 0;
}
Stack.prototype = {
push: function push(x) {
this.top++;
if (this.top < this.xs.length) {
this.xs[this.top] = x;
} else {
this.xs.push(x);
}
},
pushArrayReverse: function pushArrayReverse(xs) {
for (var i = xs.length - 1; i >= 0; i--) {
this.push(xs[i]);
}
},
pop: function pop() {
var x = this.peek();
this.top--;
return x;
},
peek: function peek() {
return this.xs[this.top];
},
isEmpty: function isEmpty() {
return -1 === this.top;
}
};
function QueueFactory(initial) {
return new Stack(initial);
}
function DfsCursor() {
this.depth = 0;
this.stack = QueueFactory({ node: null, index: -1 });
}
DfsCursor.prototype = {
moveDown: function moveDown(node) {
this.depth++;
this.stack.push({ node: node, index: 0 });
},
moveUp: function moveUp() {
this.depth--;
this.stack.pop();
},
moveNext: function moveNext() {
this.stack.peek().index++;
},
get parent() {
return this.stack.peek().node;
},
get index() {
return this.stack.peek().index;
}
};
function CursorFactory() {
return new DfsCursor();
}
function Flags() {
this.break = false;
this.skip = false;
this.remove = false;
this.replace = null;
}
Flags.prototype = {
reset: function reset() {
this.break = false;
this.skip = false;
this.remove = false;
this.replace = null;
}
};
function FlagsFactory() {
return new Flags();
}
function isNotEmpty(xs) {
return xs && 0 !== xs.length;
}
function dfsPre(root, iteratee, getChildren) {
var flags = FlagsFactory();
var cursor = CursorFactory();
var context = ContextFactory(flags, cursor);
var stack = QueueFactory(root);
var dummy = Object.assign({}, root);
while (!stack.isEmpty()) {
var node = stack.pop();
if (node === dummy) {
cursor.moveUp();
continue;
}
flags.reset();
iteratee(node, context);
if (flags.break) break;
if (flags.remove) continue;
cursor.moveNext();
if (!flags.skip) {
if (flags.replace) {
node = flags.replace;
}
var children = getChildren(node);
if (isNotEmpty(children)) {
stack.push(dummy);
stack.pushArrayReverse(children);
cursor.moveDown(node);
}
}
}
}
function dfsPost(root, iteratee, getChildren) {
var flags = FlagsFactory();
var cursor = CursorFactory();
var context = ContextFactory(flags, cursor);
var stack = QueueFactory(root);
var ancestors = QueueFactory(null);
while (!stack.isEmpty()) {
var node = stack.peek();
var parent = ancestors.peek();
var children = getChildren(node);
flags.reset();
if (node === parent || !isNotEmpty(children)) {
if (node === parent) {
ancestors.pop();
cursor.moveUp();
}
stack.pop();
iteratee(node, context);
if (flags.break) break;
if (flags.remove) continue;
cursor.moveNext();
} else {
ancestors.push(node);
cursor.moveDown(node);
stack.pushArrayReverse(children);
}
}
}
var THRESHOLD = 32768;
function Queue(initial) {
this.xs = [initial];
this.top = 0;
this.maxLength = 0;
}
Queue.prototype = {
enqueue: function enqueue(x) {
this.xs.push(x);
},
enqueueMultiple: function enqueueMultiple(xs) {
for (var i = 0, len = xs.length; i < len; i++) {
this.enqueue(xs[i]);
}
},
dequeue: function dequeue() {
var x = this.peek();
this.top++;
if (this.top === THRESHOLD) {
this.xs = this.xs.slice(this.top);
this.top = 0;
}
return x;
},
peek: function peek() {
return this.xs[this.top];
},
isEmpty: function isEmpty() {
return this.top === this.xs.length;
}
};
function QueueFactory$1(initial) {
return new Queue(initial);
}
function BfsCursor() {
this.depth = 0;
this.index = -1;
this.queue = QueueFactory$1({ node: null, arity: 1 });
this.levelNodes = 1;
this.nextLevelNodes = 0;
}
BfsCursor.prototype = {
store: function store(node, arity) {
this.queue.enqueue({ node: node, arity: arity });
this.nextLevelNodes += arity;
},
moveNext: function moveNext() {
this.index++;
},
moveForward: function moveForward() {
this.queue.peek().arity--;
this.levelNodes--;
if (0 === this.queue.peek().arity) {
this.index = 0;
this.queue.dequeue();
}
if (0 === this.levelNodes) {
this.depth++;
this.levelNodes = this.nextLevelNodes;
this.nextLevelNodes = 0;
}
},
get parent() {
return this.queue.peek().node;
}
};
function CursorFactory$1() {
return new BfsCursor();
}
function bfs(root, iteratee, getChildren) {
var flags = FlagsFactory();
var cursor = CursorFactory$1();
var context = ContextFactory(flags, cursor);
var queue = QueueFactory$1(root);
while (!queue.isEmpty()) {
var node = queue.dequeue();
flags.reset();
iteratee(node, context);
if (flags.break) break;
if (!flags.remove) {
cursor.moveNext();
if (flags.replace) {
node = flags.replace;
}
if (!flags.skip) {
var children = getChildren(node);
if (isNotEmpty(children)) {
queue.enqueueMultiple(children);
cursor.store(node, children.length);
}
}
}
cursor.moveForward();
}
}
var defaultGetChildren = function defaultGetChildren(node) {
return node.children;
};
function crawl(root, iteratee, options) {
if (null == root) return;
options = options || {};
var order = options.order || 'pre';
var getChildren = options.getChildren || defaultGetChildren;
if ('pre' === order) {
dfsPre(root, iteratee, getChildren);
} else if ('post' === order) {
dfsPost(root, iteratee, getChildren);
} else if ('bfs' === order) {
bfs(root, iteratee, getChildren);
}
}
export default crawl;
