###无极树的组建与拆分

所谓无极树，个人理解是一种无限深/无限广的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
35
36
37
38
39
40
let tree = {
	name:"a",
	child:[
		{
			name:"b",
			child:[{
				name:"d"
			},{
				name:"e"
			},{
				name:"f"
			},{
				name:"g",
				child:[
					{
						name:"h"
					},{
						name:"i",
						child:[
							{
								name:"j"
							},{
								name:"k",
								child:[
									{
										name:"l"
									},{
										name:"m"
									},
								]
							},
						]
					},
				]
			}]
		},{
			name:"c"
		},
	]
}

问题1：

将此无极树，拆分为一个一维数组，每个项都有自己的name和parent，代表他的父级

思路，递归处理tree，如果包含child数组，且数组长度大于0，则递归执行makeArr方法，否则推入数组，代码如下；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let arr = [];
function makeArr(obj,parent){
	if(obj&&obj.child&&obj.child.length>0){
		obj.child.forEach((item)=>{
			makeArr(item,obj.name)
		})
		delete obj.child
		arr.push({
			...obj,
			parent:parent
		});
	}else{
		arr.push({
			...obj,
			parent:parent
		});
	}
}
makeArr(tree,null);
console.log(arr,'拆分为数组');//此时为已拆分后的数组

问题2

将一个包含name与parent的数组（问题1的结果），转化成一个无极树；

思路，将数组解为一个队列，做一个while循环，每次对数组的第一个项进行处理，符合条件的，插入tree对应位置，并从数组移出此项，不符合条件的，放入数组最后一项，代码如下；

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
let arr = [{"name":"d","parent":"b"},{"name":"e","parent":"b"},{"name":"f","parent":"b"},{"name":"h","parent":"g"},{"name":"j","parent":"i"},{"name":"l","parent":"k"},{"name":"m","parent":"k"},{"name":"k","parent":"i"},{"name":"i","parent":"g"},{"name":"g","parent":"b"},{"name":"b","parent":"a"},{"name":"c","parent":"a"},{"name":"a","parent":null}]
let tree2 = {};
while (arr.length>0&&arr[0]){//此题arr为上方1的答案
	findDeepTree(tree2,(result,obj)=>{
		if(obj){//用于把父级为null那一层拿出来，也就是根级别的
			tree2 = obj
		}
		if(result){
			arr.shift();
		}else{
			arr.push(arr.shift());
		}
	})
}
function findDeepTree(obj,callback){
	obj.child=obj.child||[];
	let item = arr[0]
	if(obj.name == item.parent){
		if(item.parent==null){
			obj = {
				...item,
				child:[]
			}
			callback(true,obj)
		}else{
			obj.child.push(item);
			callback(true)
		}
	}else if(obj.child.length>0){
		obj.child.forEach((objChildItem)=>{
			findDeepTree(objChildItem,callback)
		})
	}else{
		callback(false)
	}
}

console.log(tree2,'合成后的tree')//此时为将数组合并后的无极树