<commit_before>---
layout: default
title: JavaScript实现无序多叉树先序遍历的效果
---

JavaScript实现无序多叉树先序遍历的效果
===================




首先，感觉这个题目有点太高大上了，我还是用人话来解释一下吧。


![tree](https://raw.githubusercontent.com/wznonstop/wznonstop.github.io/master/images/2015-11-23-tree.jpg)


借用一张解决问题过程中看到的[图](http://www.iteye.com/topic/1122125)，我需要解决的问题和这张图中描述的有些不同，不同处在于——我只需实现无序多叉树，不需要实现图中第二步的“兄弟节点横向排序”，而是直接跳到第三步的先序遍历。看起来还是不太清楚对不对？那就请看官移步下文到的具体问题吧( •̀∀•́ )

----------


数据与实现效果
-------------

数据我做了简化，差不多就是下面这样子的：

    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”的是一级分类，他们没有父级数据了。

要实现什么效果呢？其实是一个排序的问题，就是像这样的：


![list](https://raw.githubusercontent.com/wznonstop/wznonstop.github.io/master/images/2015-11-23-list.png)


注意看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）数据源的方法）](http://www.iteye.com/topic/1122125)瞄了一眼，嗯！要实现的效果差不多！那张图也特别好，看得很明白！可是，数据格式不一样，而且，好像看不懂，怎么还有java，说好的JavaScript呢，我等渣渣不会java啊~好吧我说着玩的，刚才瞄第二眼的时候感觉大致的意思还是明白的，我是看到下面评论说文章说的方法不太好我就不想看了。然后我就接着搜，没有搜到满意的结果，时间也到了周五晚的9点多了，我只好收拾收拾，回到没网的宿舍，在大雪纷飞的京城一隅宅了两天，捧着kindle狂看了几部文学作品，码农的身份不能成为没有文学素养的借口。与此同时继续思考解决问题的方法，但都是些模糊的碎片，没有连贯的思路。

转眼就到了今天，星期一，因为在这个问题上耽误了挺长时间，我决定整理一下思路，直接问带我的导师了（公司给每个新员工都分配一个导师，真是极好极好的）。导师说啊，说了什么呢？看下面的解决思路吧( •̀∀•́ )

解决思路
-------------<commit_msg>test the github Contributions Calendar<commit_after>---
layout: default
title: JavaScript实现无序多叉树先序遍历的效果
---

JavaScript实现无序多叉树先序遍历的效果
===================




首先，感觉这个题目有点太高大上了，我还是用人话来解释一下吧。


![tree](https://raw.githubusercontent.com/wznonstop/wznonstop.github.io/master/images/2015-11-23-tree.jpg)


借用一张解决问题过程中看到的[图](http://www.iteye.com/topic/1122125)，我需要解决的问题和这张图中描述的有些不同，不同处在于——我只需实现无序多叉树，不需要实现图中第二步的“兄弟节点横向排序”，而是直接跳到第三步的先序遍历。看起来还是不太清楚对不对？那就请看官移步下文到的具体问题吧( •̀∀•́ )

----------


数据与实现效果
-------------

数据我做了简化，差不多就是下面这样子的：

    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”的是一级分类，他们没有父级数据了。

要实现什么效果呢？其实是一个排序的问题，就是像这样的：


![list](https://raw.githubusercontent.com/wznonstop/wznonstop.github.io/master/images/2015-11-23-list.png)


注意看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）数据源的方法）](http://www.iteye.com/topic/1122125)瞄了一眼，嗯！要实现的效果差不多！那张图也特别好，看得很明白！可是，数据格式不一样，而且，好像看不懂，怎么还有java，说好的JavaScript呢，我等渣渣不会java啊~好吧我说着玩的，刚才瞄第二眼的时候感觉大致的意思还是明白的，我是看到下面评论说文章说的方法不太好我就不想看了。然后我就接着搜，没有搜到满意的结果，时间也到了周五晚的9点多了，我只好收拾收拾，回到没网的宿舍，在大雪纷飞的京城一隅宅了两天，捧着kindle狂看了几部文学作品，码农的身份不能成为没有文学素养的借口。与此同时继续思考解决问题的方法，但都是些模糊的碎片，没有连贯的思路。

转眼就到了今天，星期一，因为在这个问题上耽误了挺长时间，我决定整理一下思路，直接问带我的导师了（公司给每个新员工都分配一个导师，真是极好极好的）。导师说啊，说了什么呢？看下面的解决思路吧( •̀∀•́ )

解决思路
-------------
{'fraction_non_alphanumeric': 0.18271383788625167, 'fraction_numerical': 0.07493655769517839, 'mean_word_length': 2.7746478873239435, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 15, 'https://': 4, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7152458', 'n_tokens_mistral': 4730, 'n_tokens_neox': 5050, 'n_words': 286}