一个将数据结构化的算法——以思维简图为例

问题设定

在思维简图中，软件可以将用户录入的文本直接转化为思维导图。其规则是：用户录入的文字必须以一个感叹号作为一个节点的起始标记，一个感叹号表示后面的文字处于第一级节点，两个感叹号表示后面的文字处于第二个节点，以此类推。

所以， 上面这段文字经过软件处理后应该生成的树状图应该如下：

常规思路

在将文字转化为图片的过程中，如何将录入文本转化为一个结构化的数据至关重要。按照最容易想到的思路，算法设计应该是这样：

1. 在全文的最末尾加一个感叹号，然后找出所有处于单个感叹号之间的文字，放入一个数组中；

2. 将数组中的第一个节点的文字提取出来，作为这个节点的title值保存下来，并且保存自己的父级的id（对于第一级的节点，父级节点id取-1），创建一个自己的id；

3. 上述处理完毕之后，用递归的方式处理第二级、第三级……节点，直到全部遍历完。

这就是我写第一版程序时的思路，这个算法写得很笨，也写得很痛苦。层层递归的方式，在程序调试时不那么符合地球人的思维习惯。那种感觉很像是我们诟病Nodejs里的层层回调嵌套出现的“死亡金字塔”式的程序结构。

重新思考

前些天阅读过promise编程模式，很好的破解掉了这个“死亡金字塔”，让代码的结构非常便于阅读和调试。受到这个启发，再次思考了这个算法的设计，应该有一个调试起来思路更清楚，代码结构更一目了然的方式：

1. 首先不考虑感叹号的多少，把感叹号之间的文字提取出来，放入一个数组；

2. 遍历数组，将数组中每个元素创建为一个节点实例，实例包含如下属性：id, title, level, parent, childrenids。id即自己在数组中的序号，title为自身文字，level即自身文字中包含感叹号的数量。parent的算法稍复杂：寻找id和自己最接近且level比自己小1的节点，它的id即parent的值。childrenids暂时设为一个空数组。

3. 上一步遍历完成后，再次遍历，根据parent值将各个节点的childrenids数组填写好。

4. 至此，所有节点的属性值已经都具备。如果我们需要用一个json来结构化的表达这一组数据，那么只需要再次遍历数组，创建一个json，将相应的值填充好就可以了。

下面是实现这个算法的代码：

var str="!内容 !!同盟会的政治纲领是“驱除鞑虏，恢复中华，创立民国，平均地权”。 !!孙中山将同盟会的纲领概括为三大主义，即民族主义、民权主义、民生主义，后被称为三民主义。 !!!民族主义，即民族革命，包括“驱除鞑虏，恢复中华”两项内容。 !!!民权主义即政治革命，内容是“创立民国”，即建立资产阶级民主共和国。 !!!民生主义即社会革命，指的是“平均地权”。 !评价: !!它初步描绘出中国还不曾有过的资产阶级共和国方案，是一个比较完整而明确的资产阶级民主革命纲领。!!对推动革命的发展产生了重大而积极的影响。 !!但它并不是一个彻底的资产阶级民主革命纲领。";       //提取文字创建数组     var pt=/!+[^!]+(?=!)/g;     var arr=str.match(pt);     console.log(arr)      //遍历数组，将数组中每个元素创建为一个节点实例     var nodes=[];     for(var i in arr){         var obj={};         obj.id=i;         var len=arr[i].length;         obj.title=arr[i].replace(/!/g,"");         obj.level=len-obj.title.length;         if(obj.level==1)obj.parent=-1;         else obj.parent=findparent(obj.level,obj.id).id;         obj.childrenids=[];         nodes.push(obj);     }      //遍历数组，为每个节点补上子节点集合     for(var i in nodes){         nodes[i].childrenids=findchildrenid(nodes[i].id);     }      //转化为json数组     var json={         title:"三民主义学说和资产阶级共和国方案",         id:-1,         parent:-1,         level:-1,         childrenids:findchildrenid(-1)     }      createjson(json,json.childrenids);      function createjson(node,idarr){         var c=[];         for(var i in idarr){             c.push(findbyid(idarr[i]));         }         node.children=c;          for(var i in c){             createjson(c[i],c[i].childrenids);         }     }      console.log(JSON.stringify(json,null,"/t"))      function findchildrenid(id){         var arr=[];         for(var i in nodes){             if(nodes[i].parent==id)arr.push(nodes[i].id);         }         return arr;     }      function findparent(level,id){         var parr=findbylevel(level-1);         var n={},sub;         for(var i in parr){             if(parr[i].id<id){                 if(i==0 || id-parr[i].id<sub){                     sub=id-parr[i].id;                     n=parr[i];                 }             }         }         return n;      }      function findbylevel(level){         var arr=[];         for(var i in nodes){             if(nodes[i].level==level)arr.push(nodes[i]);         }         return arr;     }      function findbyid(id){         for(var i in nodes)if(nodes[i].id==id)return nodes[i];         return {};     }

最后执行生成json的打印结果如下：

{     "title": "三民主义学说和资产阶级共和国方案",     "id": -1,     "parent": -1,     "level": -1,     "childrenids": [         "0",         "6"     ],     "children": [         {             "id": "0",             "title": "内容 ",             "level": 1,             "parent": -1,             "childrenids": [                 "1",                 "2"             ],             "children": [                 {                     "id": "1",                     "title": "同盟会的政治纲领是“驱除鞑虏，恢复中华，创立民国，平均地权”。 ",                     "level": 2,                     "parent": "0",                     "childrenids": [],                     "children": []                 },                 {                     "id": "2",                     "title": "孙中山将同盟会的纲领概括为三大主义，即民族主义、民权主义、民生主义，后被称为三民主义。 ",                     "level": 2,                     "parent": "0",                     "childrenids": [                         "3",                         "4",                         "5"                     ],                     "children": [                         {                             "id": "3",                             "title": "民族主义，即民族革命，包括“驱除鞑虏，恢复中华”两项内容。 ",                             "level": 3,                             "parent": "2",                             "childrenids": [],                             "children": []                         },                         {                             "id": "4",                             "title": "民权主义即政治革命，内容是“创立民国”，即建立资产阶级民主共和国。 ",                             "level": 3,                             "parent": "2",                             "childrenids": [],                             "children": []                         },                         {                             "id": "5",                             "title": "民生主义即社会革命，指的是“平均地权”。 ",                             "level": 3,                             "parent": "2",                             "childrenids": [],                             "children": []                         }                     ]                 }             ]         },         {             "id": "6",             "title": "评价: ",             "level": 1,             "parent": -1,             "childrenids": [                 "7",                 "8"             ],             "children": [                 {                     "id": "7",                     "title": "它初步描绘出中国还不曾有过的资产阶级共和国方案，是一个比较完整而明确的资产阶级民主革命纲领。",                     "level": 2,                     "parent": "6",                     "childrenids": [],                     "children": []                 },                 {                     "id": "8",                     "title": "对推动革命的发展产生了重大而积极的影响。 ",                     "level": 2,                     "parent": "6",                     "childrenids": [],                     "children": []                 }             ]         }     ] }