JavaScript实现无序多叉树先序遍历的效果
首先，感觉这个题目有点太高大上了，我还是用人话来解释一下吧。
借用一张解决问题过程中看到的图，我需要解决的问题和这张图中描述的有些不同，不同处在于——我只需实现无序多叉树，不需要实现图中第二步的“兄弟节点横向排序”，而是直接跳到第三步的先序遍历。看起来还是不太清楚对不对？那就请看官移步下文到的具体问题吧( •̀∀•́ )
数据与实现效果
数据我做了简化，差不多就是下面这样子的：
var dataArr= [
{
pid: "11",
id: "111",
fullName: "一级分类1下的子分类1-1下的子分类1-1-1"
},
{
pid: "21",
id: "211",
fullName: "一级分类2下的子分类2-1下的子分类2-1-1"
},
{
pid: "21",
id: "213",
fullName: "一级分类2下的子分类2-1下的子分类2-1-3"
},
{
pid: "0",
id: "5",
fullName: "一级分类5"
},
{
pid: "213",
id: "2131",
fullName: "一级分类2下的子分类2-1下的子分类2-1-3下的子分类2-1-3-1"
},
{
pid: "1",
id: "13",
fullName: "一级分类1下的子分类1-3"
},
{
pid: "22",
id: "221",
fullName: "一级分类2下的子分类2-2下的子分类2-2-1"
},
{
pid: "21",
id: "212",
fullName: "一级分类2下的子分类2-1下的子分类2-1-2"
},
{
pid: "0",
id: "1",
fullName: "一级分类1"
},
{
pid: "0",
id: "2",
fullName: "一级分类2"
},
{
pid: "0",
id: "3",
fullName: "一级分类3"
},
{
pid: "1",
id: "11",
fullName: "一级分类1下的子分类1-1"
},
{
pid: "1",
id: "12",
fullName: "一级分类1下的子分类1-2"
},
{
pid: "2",
id: "21",
fullName: "一级分类2下的子分类2-1"
},
{
pid: "2",
id: "22",
fullName: "一级分类2下的子分类2-2"
},
{
pid: "212",
id: "2121",
fullName: "一级分类2下的子分类2-1下的子分类2-1-2下的子分类2-1-2-1"
},
{
pid: "2131",
id: "21311",
fullName: "一级分类2下的子分类2-1下的子分类2-1-3下的子分类2-1-3-1下的子分类2-1-3-1-1"
},
{
pid: "212",
id: "2122",
fullName: "一级分类2下的子分类2-1下的子分类2-1-2下的子分类2-1-2-2"
},
{
pid: "2121",
id: "21211",
fullName: "一级分类2下的子分类2-1下的子分类2-1-2下的子分类2-1-2-1下的子分类2-1-2-1-1"
}
];
数据被包含在一个叫“dataArr”的数组里，每个数据实际上都是一个对象，每个对象有三个属性，其中“fullName”属性在此处没用，只不过我懒得删了。。。起到关键作用的只有两个属性”pid”和“id”，数据之间存在父子关系，”id”是数据唯一的标识，”pid”是该数据的父级数据的”pid”，其中”pid”为“0”的是一级分类，他们没有父级数据了。
要实现什么效果呢？其实是一个排序的问题，就是像这样的：
注意看id那一列，每个数据的父级一定在该数据的前面，且与它的父级是相连的，这里描述得不太准确，举个例子，比如说这样的一个排序：
1>1-1>1-2>1-1-1
虽然每个数据的父级都在自己的前面，但是1-1和1-1-1之间却不是相连的，正确的应该是：
1>1-1>1-1-1>1-2
其实在意识到这个问题可以转换为树的遍历问题之前，我苦思冥想，夜不能寐，头晕脑胀，克服了种种艰难困苦，历经了九九八十一难，发现，哎，就是想不出来!后经高人指点，方才如醍醐灌顶般恍然大悟，啊哈 (^o^)/ 这不就是个无序多叉树的先序遍历问题吗！高兴了5秒钟，想了3秒钟，就傻了，虽然知道了这是什么问题，然而我还是不会写啊T_T，于是我就开始搜，搜啊搜，看到了上面那张图的发源地：多叉树结合JavaScript树形控件实现无限级树形菜单（一种构建多级有序树形结构JSON（或XML）数据源的方法）瞄了一眼，嗯！要实现的效果差不多！那张图也特别好，看得很明白！可是，数据格式不一样，而且，好像看不懂，怎么还有java，说好的JavaScript呢，我等渣渣不会java啊~好吧我说着玩的，刚才瞄第二眼的时候感觉大致的意思还是明白的，我是看到下面评论说文章说的方法不太好我就不想看了。然后我就接着搜，没有搜到满意的结果，时间也到了周五晚的9点多了，我只好收拾收拾，回到没网的宿舍，在大雪纷飞的京城一隅宅了两天，捧着kindle狂看了几部文学作品，码农的身份不能成为没有文学素养的借口。与此同时继续思考解决问题的方法，但都是些模糊的碎片，没有连贯的思路。
转眼就到了今天，星期一，因为在这个问题上耽误了挺长时间，我决定整理一下思路，直接问带我的导师了（公司给每个新员工都分配一个导师，真是极好极好的）。导师说啊，说了什么呢？看下面的解决思路吧( •̀∀•́ )
解决思路
导师说的解题思路是：首先，创建一个空的数组“finalArr”作为最终的数组，先根据一级分类的”pid”为0，找出一级分类，放入数组，然后，循环这个数组，找出该数组中每个数据的子数据，放到对应数据的后面，然后依次循环。
有点绕，就拿“id”为“1”的数据举个例子，由于它的”pid”为“0”，所以它在第一步之后便被放入了“finalArr”数组中，在第二步对“finalArr”进行循环的时候就会找出“id”为“1”的数据的子集：“id”为“13”、“11”、“12”的数据（我在题目里就说了，这是“无序多叉树”，所以兄弟节点之间的顺序不必管），然后将得到的新数组中的数据插入最终数组“finalArr”中“id”为“1”的数据后面，然后再对得到的新数组 执行同样的循环。
嗯，我一听，明白了，可是，道理我都懂，却仍过不好这一生，啊不，串戏了，是道理我都懂，却还是不知道怎么写啊，导师让我先写两三级的数据试试看，我⊙﹏⊙点了点头，先在纸上画了画，然后在电脑上敲了敲，一看结果，╭(°A°`)╮！！！说好只试个两三级的呢！怎么全都出来了！一时间我的心情就像在焦金流石的夏日钻进了空调房，开心得我偷笑了好几分钟！那么我是怎么实现的呢？请看接着往下看吧( •̀∀•́ )
具体代码及分析
整体代码如下：
//包含数据的数组
var dataArr = [
{
pid: "11",
id: "111",
fullName: "一级分类1下的子分类1-1下的子分类1-1-1"
},
{
pid: "21",
id: "211",
fullName: "一级分类2下的子分类2-1下的子分类2-1-1"
},
{
pid: "21",
id: "213",
fullName: "一级分类2下的子分类2-1下的子分类2-1-3"
},
{
pid: "0",
id: "5",
fullName: "一级分类5"
},
{
pid: "213",
id: "2131",
fullName: "一级分类2下的子分类2-1下的子分类2-1-3下的子分类2-1-3-1"
},
{
pid: "1",
id: "13",
fullName: "一级分类1下的子分类1-3"
},
{
pid: "22",
id: "221",
fullName: "一级分类2下的子分类2-2下的子分类2-2-1"
},
{
pid: "21",
id: "212",
fullName: "一级分类2下的子分类2-1下的子分类2-1-2"
},
{
pid: "0",
id: "1",
fullName: "一级分类1"
},
{
pid: "0",
id: "2",
fullName: "一级分类2"
},
{
pid: "0",
id: "3",
fullName: "一级分类3"
},
{
pid: "1",
id: "11",
fullName: "一级分类1下的子分类1-1"
},
{
pid: "1",
id: "12",
fullName: "一级分类1下的子分类1-2"
},
{
pid: "2",
id: "21",
fullName: "一级分类2下的子分类2-1"
},
{
pid: "2",
id: "22",
fullName: "一级分类2下的子分类2-2"
},
{
pid: "212",
id: "2121",
fullName: "一级分类2下的子分类2-1下的子分类2-1-2下的子分类2-1-2-1"
},
{
pid: "2131",
id: "21311",
fullName: "一级分类2下的子分类2-1下的子分类2-1-3下的子分类2-1-3-1下的子分类2-1-3-1-1"
},
{
pid: "212",
id: "2122",
fullName: "一级分类2下的子分类2-1下的子分类2-1-2下的子分类2-1-2-2"
},
{
pid: "2121",
id: "21211",
fullName: "一级分类2下的子分类2-1下的子分类2-1-2下的子分类2-1-2-1下的子分类2-1-2-1-1"
}
];
//创建一个空数组作为最终的数组
var finalArr = [];
//根据"pid"获取一级分类的数据，放入最终的数组
for (var i = 0; i < dataArr.length; i++) {
var self = dataArr[i];
if (self.pid == 0) {
finalArr.push(self);
};
};
//获取某个数据的子级数据的函数
function getChildArr(data){
var chlidArr = [];
for (var i = 0; i < dataArr.length; i++) {
var self = dataArr[i];
if (self.pid == data.id) {
chlidArr.push(self);
};
};
return chlidArr;
}
//根据内容获取对应下标（由于数据类型的特殊性，不需考虑数组中有重复值的情况）
function getIndex(val, arr){
for (var i = 0; i < arr.length; i++) {
var self = arr[i];
var index = i;
if (val.id == self.id) {
return index;
};
};
}
//这里是重点，在下方细讲
for(var i = 0; i < finalArr.length; i++){
var self = finalArr[i];
var chlidArr = getChildArr(self);
for (var j = 0; j < chlidArr.length; j++) {
var index = getIndex(self, finalArr);
var that = chlidArr[j];
var inx = j+index+1;
finalArr.splice(inx, 0 , that);
};
}
//为什么留下这个调试的语句呢？因为我觉得它挺好用的，数据多的情况下以表格的形式看，一目了然，但它也有比较坑的地方——属性较多时，有些关键属性也可能被它傲娇地忽略掉了( •ิ_• ิ)
console.table(finalArr);
这里着重讲一下最后一段代码，首先，要明确的是，在进行这段循环之前，”finalArr”中存储的是一级分类对应的那几个数据，按照代码进行的顺序，接下来，假设执行循环的第一个数据是”id”为”1”的数据，在具体代码中，”self”就是当前的这个”id”为”1”的数据，毫无疑问，“chlidArr”就是以”id”为“13”、“11”、“12”的数据组成的数组，这样进入内层循环。
内层循环是针对子级数据组成的数组进行的，那么假设这个数组的第一个数据是”id”为”11“的数据，一起来看看执行了这次循环之后都有什么变化。
首先，”index”是当前的父级元素，即”id”为”1”的元素在最终数组”finalArr”中的下标值，要它干嘛，可以吃吗？嗯，其实不可以吃，但是，有它才能定位到当前父级元素的位置啊，这样才知道应该把子级元素往哪放。
“that”，就是当前的这个数据，即”id”为”11”的数据。
“inx”是啥？”inx”是当前这个数据要插入的位置，为什么var inx = j+index+1; ，分成两部分考虑，首先，当前这个”id”为”11”的数据如果插入到数组”finalArr”中，它的下标该是多少？因为它就在”id”为”1”的数据后面，下标值当然是 inx = index + 1 了，此时对应的”j”的值为 0 ，那么紧接在”id”为”11”的数据后面的数据，它的下标值该是多少呢？这其实是一个容易忽略的地方，因为”id”为”11”的数据已经经过循环，插入到最终数组”finalArr”中了，所以，”inx”当然要相应地发生变化，稍加思考就可以知道，最终 ”inx“的值就应该是j+index+1 。
与此同时，”finalArr”也已经发生了变化，真正的新数组并不是子级数据组成的数组，而是最终数组”finalArr”。在我们假设的情况下，”id”为”11”的数据经过内层循环插入到”finalArr”之后，该数据就成了数组”finalArr”的第二个元素，那么接下来就是对它执行获取子级数据的数组、将子级数据插入”finalArr”的操作了，依次循环，直到将所有数据都按正确的顺序放入”finalArr”中，就大功告成了( •̀∀•́ )哈哈哈哈哈~（我不会说其实我是花了好几分钟才看明白自己写的为什么就对了的）
哦对了，在将数据插入到”finalArr”时用到了数组的”splice()”方法，开始的时候我写成了”slice”，结果老是怪怪的，看了半天原来是把方法名写错了⊙﹏⊙，看来下次遇到方法名之类的我还是复制粘贴吧。
总结
我搞定了用JavaScript实现无序多叉树先序遍历的效果的问题，很开心(^o^)/~嗯，就酱，我的演讲结束了，谢谢大家！(^o^)/