Content Table

字符串构建树

练习树的算法时,使用代码手动构造树比较麻烦,容易出错,用 JSON 来表示也不够方便,用直观的字符串来表示一颗树更简单 (用缩进来表示节点的父子关系),例如:

1
2
3
4
5
6
7
8
9
10
11
1
2
3
5
6
4
7
9
10
8
11

下面就解析这个字符串生成一棵树:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
* 缩进数量,每 4 个空格作为一个缩进
*
* @param {String} line 字符串
* @return {Int} 返回缩进的个数
*/
function countIndent(line) {
return (line.lastIndexOf(' ') + 1) / 4;
}

/**
* 使用树结构的字符串构建树
*
* @param {String} treeContent 树结构的字符串
* @return {JSON} 返回树的根节点
*/
function buildTree(treeContent) {
// 1. 按行分割,每一行是一个节点信息
// 2. 数组的第一个元素构造根节点
// 3. 从数组的第二个元素开始
// 3.1 构造一个节点,加入到节点的数组中
// 3.2 在节点数组中从后往前查找最近一个比当前节点少一个缩进的节点,此节点为当前节点的父节点

// [1] 按行分割,每一行是一个节点信息
var lines = treeContent.split('\n').filter(line => line.length > 0);

if (lines.length === 0) {
return null;
}

// [2] 数组的第一个元素构造根节点
var root = { id: parseInt(lines[0]), indent: 0 };
var nodes = [root];

for (let i = 1; i < lines.length; i++) {
// [3.1] 构造一个节点,加入到节点的数组中
var indent = countIndent(lines[i]);
var node = { id: parseInt(lines[i]), indent: indent };
nodes.push(node);

// [3.2] 在节点数组中从后往前查找最近一个比当前节点少一个缩进的节点,此节点为当前节点的父节点
for (let j = nodes.length-1; j >= 0; j--) {
if (nodes[j].indent === indent-1) {
nodes[j].children = nodes[j].children || [];
nodes[j].children.push(node);
break;
}
}
}

return root;
}

// 树结构的字符串 (缩进使用 4 个空格)
var treeContent = `
1
2
3
5
6
4
7
9
10
8
11
`;

var treeRoot = buildTree(treeContent);
console.log(JSON.stringify(treeRoot));