常用数据结构处理

• 1、扁平数组转换为树结构
  • 1.1 没有id父子关系的扁平数组转化为树
  • 1.2 一维数组分类
• 2、树结构转换为扁平数组
• 3、过滤树结构
• 4、过滤固定层级的树结构，去除没有子节点的节点

1、扁平数组转换为树结构

这个可以处理具有唯一父节点的, 比如下面id为0的节点就是唯一的根节点。

function flatArrayToTree(data, rootParentId, parentKey, id = 'id') {
  let r = null;
  let tempObj = {};
  data.forEach(function (node) {
    tempObj[node[id]] = {
      ...node,
      children: tempObj[node[id]] && tempObj[node[id]].children
    };

    if (node[parentKey] === rootParentId) {
      r = tempObj[node[id]];
    } else {
      tempObj[node[parentKey]] = tempObj[node[parentKey]] || {};
      tempObj[node[parentKey]].children = tempObj[node[parentKey]].children || [];
      tempObj[node[parentKey]].children.push(tempObj[node[id]]);
    }
  }, Object.create(null));
  tempObj = null;
  return r;
}
const testData = [
  {
    id: 'A-2-1',
    name: 'A-2-1',
    _parentId: 'A-2'
  },
  {
    id: 'A',
    name: 'A',
    _parentId: '0'
  },
  {
    id: '0',
    name: 'root',
    _parentId: '-1'
  },

  {
    id: 'B',
    name: 'B',
    _parentId: '0'
  },
  {
    id: 'C',
    name: 'C',
    _parentId: '0'
  },
  {
    id: 'A-1',
    name: 'A-1',
    _parentId: 'A'
  },
  {
    id: 'A-2',
    name: 'A-2',
    _parentId: 'A'
  },

  {
    id: 'B-1',
    name: 'B-1',
    _parentId: 'B'
  },
  {
    id: 'C-1',
    name: 'C-1',
    _parentId: 'C'
  }
];

console.log(JSON.stringify(flatArrayToTree(testData, '-1', '_parentId'), null, 2));

不过很多时候后台返回的数据都是没有唯一根节点的， 可能是多个根节点， 那么我们稍微改造即可

function flatArrayToTree(data, root, parentKey, id = 'id') {
  let r = [];
  let tempObj = {};
  data.forEach(function (node) {
    tempObj[node[id]] = {
      ...node,
      children: tempObj[node[id]] && tempObj[node[id]].children
    };

    if (node[parentKey] === root) {
      r.push(tempObj[node[id]]);
    } else {
      tempObj[node[parentKey]] = tempObj[node[parentKey]] || {};
      tempObj[node[parentKey]].children = tempObj[node[parentKey]].children || [];
      tempObj[node[parentKey]].children.push(tempObj[node[id]]);
    }
  }, Object.create(null));
  tempObj = null;
  return r;
}
const testData = [
  {
    id: 'A-2-1',
    name: 'A-2-1',
    _parentId: 'A-2'
  },
  {
    id: 'A',
    name: 'A',
    _parentId: '0'
  },
  {
    id: '0',
    name: 'root',
    _parentId: '-1'
  },

  {
    id: 'B',
    name: 'B',
    _parentId: '0'
  },
  {
    id: 'C',
    name: 'C',
    _parentId: '0'
  },
  {
    id: 'A-1',
    name: 'A-1',
    _parentId: 'A'
  },
  {
    id: 'A-2',
    name: 'A-2',
    _parentId: 'A'
  },

  {
    id: 'B-1',
    name: 'B-1',
    _parentId: 'B'
  },
  {
    id: 'C-1',
    name: 'C-1',
    _parentId: 'C'
  },
  {
    id: 'root2id',
    name: 'root2',
    _parentId: '-1'
  },
  {
    id: 'D-1',
    name: 'D-1',
    _parentId: 'root2id'
  }
];

console.log(JSON.stringify(flatArrayToTree(testData, '-1', '_parentId'), null, 2));

再进阶一下的话， 给一个断言函数， 是不是root节点由使用者自己传入函数决定

function flatArrayToTree(data, rootNodePredicateFn, parentKey, id = 'id') {
  let r = [];
  data.forEach(function (node) {
    this[node[id]] = {
      ...node,
      children: this[node[id]] && this[node[id]].children
    };
    if (rootNodePredicateFn(node, parentKey)) {
      r.push(this[node[id]]);
    } else {
      this[node[parentKey]] = this[node[parentKey]] || {};
      this[node[parentKey]].children = this[node[parentKey]].children || [];
      this[node[parentKey]].children.push(this[node[id]]);
    }
  }, Object.create(null));
  return r;
}
      
      
flatArrayToTree(
  list,
  (node, parentKey) => {
    // 如果节点的parentKey键对应的值不存在 实为root根节点
    if (!node[parentKey]) {
      return true;
    }
    return false;
  },
  '_parentId',
  'id'
);

1.1 没有id父子关系的扁平数组转化为树

有时候会受到后台传递的扁平数组，按照层级排序过，没有利用id形成父子关系，而是利用层级顺序表示父子关系， 将这类数据转换为树结构。

下面的示例代码只兼容到深度为3的场景，具体有什么需求可以额外更改

function transSortedFlatArrayToTree(arr = [], levelKey = 'levelNo') {
  const tree = [];
  let level1Obj;
  let level2Obj;
  for (let i = 0, len = arr.length; i < len; i++) {
    const item = arr[i];
    const level = item[levelKey];
    if (level === 0) {
      level1Obj = { ...item };
      level1Obj.children = [];
      tree.push(level1Obj);
    }

    if (level === 1) {
      level2Obj = { ...item };
      level2Obj.children = [];
      level1Obj.children.push(level2Obj);
    }
    if (level === 2) {
      level2Obj.children.push({ ...item });
    }
  }
  return tree;
}

let arr = [
  {
    levelNo: 0,
    title: 'item0'
  },
  {
    levelNo: 1,
    title: 'item0_1'
  },
  {
    levelNo: 2,
    title: 'item0_1_1'
  },
  {
    levelNo: 2,
    title: 'item0_1_2'
  },
  {
    levelNo: 0,
    title: 'item1'
  },
  {
    levelNo: 1,
    title: 'item1_1'
  },
  {
    levelNo: 2,
    title: 'item1_1_1'
  },
  {
    levelNo: 2,
    title: 'item1_1_2'
  },
  {
    levelNo: 2,
    title: 'item1_1_3'
  }
];

console.log(JSON.stringify(transSortedFlatArrayToTree(arr), null, 2));

1.2 一维数组分类

一维数组根据父类名称分类。需要自己生成父节点，变成一个深度为2的树结构

如下的例子， 这种还是很多的，后端只会入库下面四条数据

const flatList = [
  { name: 'A-1', groupName: '分类A' },
  { name: 'A-2', groupName: '分类A' },
  { name: 'B-3', groupName: '分类B' },
  { name: 'B-4', groupName: '分类B' }
];

// 输出 
[
    {
        "groupName": "分类A",
	      "leaf": false,
        "title": "分类A",
        "children": [
            {
                "name": "A-1",
                "groupName": "分类A",
                "leaf": true,
                "title": "A-1"
            },
            {
                "name": "A-2",
                "groupName": "分类A",
                "leaf": true,
                "title": "A-2"
            }
        ]
    },
    {
        "groupName": "分类B",
      	"leaf": false,
        "title": "分类B",
        "children": [
            {
                "name": "B-3",
                "groupName": "分类B",
                "leaf": true,
                "title": "B-3"
            },
            {
                "name": "B-4",
                "groupName": "分类B",
                "leaf": true,
                "title": "B-3"
            }
        ]
    }
]

function groupFlatList(list = [], groupKey = 'groupName', cb = _ => _) {
  const result = [];
  const map = {};
  for (let i = 0, len = list.length; i < len; i++) {
    let item = list[i];
    const groupName = item[groupKey];
    if (!map[groupName]) {
      map[groupName] = [];
      let parentNode = {
        [groupKey]: groupName,
        children: map[groupName],
        leaf: false
      };
      parentNode = cb(parentNode);
      result.push(parentNode);
    }
    map[groupName].push(cb(item));
  }
  return result;
}

Usage

const groupTree = groupFlatList(flatList, 'groupName', item => {
  if (item.leaf === false) {
    // 定义一些父节点要用的属性
    item.title = item.groupName;
    return item;
  }
  item.leaf = true;
  item.title = item.name;
  return item;
});

2、树结构转换为扁平数组

这个就是树的遍历， 查看二叉树的各种遍历即可。稍加改造就可变成各种嵌套数据的遍历，无论是深度优先还是广度优先， 或是层序遍历。很容易即可得到一个扁平的数组。

举个例子吧还是

const data = {
  id: '0',
  name: 'root',
  children: [
    {
      id: 'A',
      name: 'A',
      _parentId: '0',
      children: [
        {
          id: 'A-1',
          name: 'A-1',
          _parentId: 'A'
        },
        {
          id: 'A-2',
          name: 'A-2',
          _parentId: 'A',
          children: [
            {
              id: 'A-2-1',
              name: 'A-2-1',
              _parentId: 'A-2'
            }
          ]
        }
      ]
    },
    {
      id: 'B',
      name: 'B',
      _parentId: '0',
      children: [
        {
          id: 'B-1',
          name: 'B-1',
          _parentId: 'B'
        }
      ]
    },
    {
      id: 'C',
      name: 'C',
      _parentId: '0',
      children: [
        {
          id: 'C-1',
          name: 'C-1',
          _parentId: 'C'
        }
      ]
    }
  ]
};

function deepFirstSearch(node) {
  const nodes = [];
  if (node != null) {
    var stack = [];
    stack.push(node);
    while (stack.length != 0) {
      let item = stack.pop();
      const children = item.children;
      nodes.push({
        ...item,
        children: null
      });
      if (children && children.length > 0) {
        for (let i = children.length - 1; i >= 0; i--) {
          stack.push(children[i]);
        }
      }
    }
  }
  return nodes;
}

console.log(deepFirstSearch(data));
/* 
[
  { id: '0', name: 'root', children: null },
  { id: 'A', name: 'A', _parentId: '0', children: null },
  { id: 'A-1', name: 'A-1', _parentId: 'A', children: null },
  { id: 'A-2', name: 'A-2', _parentId: 'A', children: null },
  { id: 'A-2-1', name: 'A-2-1', _parentId: 'A-2', children: null },
  { id: 'B', name: 'B', _parentId: '0', children: null },
  { id: 'B-1', name: 'B-1', _parentId: 'B', children: null },
  { id: 'C', name: 'C', _parentId: '0', children: null },
  { id: 'C-1', name: 'C-1', _parentId: 'C', children: null }
]
*/

以上是一个深度优先的遍历结果

3、过滤树结构

第二个参数为一个断言函数, 参数是当前节点

/**
 * 过滤树结构
 *
 * @param {*} tree 多节点的树结构
 * @param {boolean} [predicate=node => true] 断言函数
 * @param {*} [arr=[]]
 * @return {*} []
 */
function filterTree(tree, predicate = node => true, arr = []) {
  if (!tree || tree.length === 0) {
    return [];
  }
  for (let i = 0, len = tree.length; i < len; i++) {
    const node = tree[i];

    if (predicate(node)) {
      const newNode = { ...node, children: [] };
      arr.push(newNode);
      if (node.children && node.children.length > 0) {
        filterTree(node.children, predicate, newNode.children);
      }
    }
  }
  return arr;
}

如果只想过滤叶子节点，可以这样子写断言函数

const ret = filterTree(tree, node => {
  if (node.children && node.children.length > 0) {
    return true;
  }
  return node.prop > 0;
});

4、过滤固定层级的树结构，去除没有子节点的节点

有时候一些树结构，固定层级只有三级，但是如果一个一级或者二级节点没有三级子节点， 那么这个一级和二级的也都不要了。 实现比较傻瓜， 就是三个循环

function deleteTree(tree, predicate = node => false, childKey = 'children') {
  for (let i = tree.length - 1; i >= 0; i--) {
    const level1Item = tree[i];
    const level1Children = level1Item[childKey];
    if (level1Children && level1Children.length > 0) {
      for (let j = level1Children.length - 1; j >= 0; j--) {
        const level2Children = level1Children[j][childKey];
        if (level2Children && level2Children.length > 0) {
          for (let k = level2Children.length - 1; k >= 0; k--) {
            const level3Item = level2Children[k];
            if (predicate(level3Item)) {
              level2Children.splice(k, 1);
            }
          }
        }
        if (!level2Children || level2Children.length === 0) {
          level1Children.splice(j, 1);
        }
      }
    }
    if (!level1Children || level1Children.length === 0) {
      tree.splice(i, 1);
    }
  }
  return tree;
}
console.log(deleteTree(tree, node => !node.name));