Sobird

例如：将下面数据

[
 ['a', 'aa', 'aaa', 'aaaa'],
 ['b', 'bb', 'bbb'],
 ['a', 'ab', 'aba'],
 ['a', 'aa', 'aab']
]

转换为

[
    {
        "name" : "a",
        "child" : [
            {
                "name" : "aa",
                "child" : [
                    {
                        "name" : "aaa",
                        "child" : [
                            {
                                "name" : "aaaa",
                                "child" : []
                            }
                        ]
                    },
                    {
                        "name" : "aab",
                        "child" : []
                    }
                ]

            },
            {
                "name" : "ab",
                "child" : [
                    {
                        "name": "aba",
                        "child" : []
                    }
                ]

            }
        ]
    },
    {
        "name": "b",
        "child" : [
            {
                "name" : "bb",
                "child" : [
                    {
                        "name" : "bbb",
                        "child" : []
                    }
                ]
            }
        ]
    }

]

分析

从上面转换的前后数据结构可以看出，二维数组的元素是一维数组，一维数组需要转换为单链表的形式来满足结果的树结构，同时需要将节点名称一样的进行合并。

大体思考如下：

• 将形如['a', 'aa', 'aaa', 'aaaa']数组转为单链表
• 合并单链表中的重复项
• 将结果保存输出

实现

// 数组转链表
function array2list(arr) {
  if(!arr.length) {
    return null;
  }

  var node;
  var head = {
    name: arr[0],
    child: []
  }
  var pnode = head;
  for(var i = 1; i < arr.length; i++) {
    node = {
      name: arr[i],
      child: []
    };
    pnode.child = [node];
    pnode = node;
  }
  return head;
}

// 链表项去重
function mergeTree(tree, list) {
  if(!tree) {
    return;
  }
  var head = list.name;
  tree.some(function(item) {
    if(item.name == head) {
      mergeTree(item.child, list.child[0]);
      return true;
    } else {
      tree.push(list);
   }
  });
  if(tree.length == 0) {
    tree.push(list);
  }
}

// 二维数组转树结构
function array2tree(data) {
  var tree = [];
  data.forEach(function(item, index) {
    var tmp = array2list(item);
    mergeTree(tree, tmp);
  });
  return tree;
}

var data = [
 ['a', 'aa', 'aaa', 'aaaa'],
 ['b', 'bb', 'bbb'],
 ['a', 'ab', 'aba'],
 ['a', 'aa', 'aab']
];

array2tree(data);