JS 中遍历树

发表于   |   分类于   |     |   阅读次数

本文回顾一下遍历树的几种方式：递归遍历，非递归深度优先遍历，非递归广度优先遍历。


如上图，在 JavaScript 中可以用 object 表示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
let tree = {
    value: 0,
    children: [{
        value: 11,
        children: [{
        	value: 21,
        	children: [{
        		value: 31,
        		children: []
        	}, {
        		value: 32,
        		children: []
        	}, {
        		value: 33,
        		children: []
        	}]
        }, {
        	value: 22,
        	children: []
        }]
    }, {
        value: 12,
        children: [{
        	value: 23,
        	children: []
        }, {
        	value: 24,
        	children: []
        }]
    }, {
        value: 13,
        children: []
    }]
}

递归遍历

1
2
3
4
5
6
7
8
9
var recursiveTraverse = function (node, action) {
	if (!node || !node.children) { return; }
	action(node.value);
	node.children.forEach(function(item, index) {
		recursiveTraverse(item, action);
	});
}
// 递归实现
recursiveTraverse(tree, console.log);

输出结果：
0
11
21
31
32
33
22
12
23
24
13

非递归深度优先遍历（借助栈实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var nonRecursiveDepthFirstTraversal = function (node, action) {
	if (!node || !node.children) { return; }
	var _stack = []; // 借助一个栈
	_stack.unshift(node);
	while (_stack.length) {
		let _curNode = _stack.shift(); // 推出栈顶元素
		action(_curNode.value);
		// 将子节点依次放入到栈顶
		// _curNode.children.forEach(function (item, index) {
		// 	_stack.unshift(item);
		// })
		if (_curNode.children.length) {
			_stack = _curNode.children.concat(_stack);
		}
	}
}
// 非递归深度优先遍历
nonRecursiveDepthFirstTraversal(tree, console.log);

输出结果：
0
11
21
31
32
33
22
12
23
24
13

非递归广度优先遍历（借助队列实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var nonRecursiveWidthFirstTraversal = function (node, action) {
	if (!node || !node.children) { return; }
	var _queue = []; // 借助一个队列
	_queue.push(node);
	while (_queue.length) {
		let _curNode = _queue.shift(); // 推出队头元素
		action(_curNode.value);
		// 将子节点依次推入队列中
		// _curNode.children.forEach(function (item, index) {
		// 	_queue.push(item);
		// })
		if (_curNode.children.length) {
			_queue = _queue.concat(_curNode.children);
		}
	}
}
// 非递归宽度优先遍历
nonRecursiveWidthFirstTraversal(tree, console.log);

输出结果：
0
11
12
13
21
22
23
24
31
32
33