在前端开发中我经常遇到处理树形结构的过程，比如多级嵌套的菜单，多级评论等，而后端返回给我们的数据有可能是处理好了的树形结构，也有可能是一个平级的对象数组，比如：

const arr = [
  { id: 1, address: 'china', parentId: null },
  { id: 2, address: 'sichaun', parentId: 1 },
  { id: 4, address: '广州', parentId: 1 },
  { id: 3, address: 'neijiang', parentId: 2 }
];

我们希望对这个数据进行处理，按照id和parentId进行拼接成如下的数据：

[
    {
        "id": 1,
        "address": "china",
        "parentId": null,
        "children": [
            {
                "id": 2,
                "address": "sichaun",
                "parentId": 1,
                "children": [
                    {
                        "id": 3,
                        "address": "neijiang",
                        "parentId": 2,
                        "children": []
                    }
                ]
            },
            {
                "id": 4,
                "address": "广州",
                "parentId": 1,
                "children": []
            }
        ]
    }
]

当然我们得到了这个树形的数据后可能还需要做其他的处理，比如遍历这个树形数据，根据某一结点的属性获取节点对象，根据某一结点的属性来获取其所有的父节点等。

以下我就总结了一些常用的操作：

拼接树形数据

根据后端传过来的平级对象数组进行树形数据的拼接，如文章开头的实例，这里主要讲解如何拼接。

递归拼接

递归拼接代码结构简单，当然理解起来不太容易，而且如果数据量大可能会出现性能问题。
展示数据如下：

const arr = [
  { id: 1, address: 'china', parentId: null },
  { id: 2, address: 'sichaun', parentId: 1 },
  { id: 4, address: '广州', parentId: 1 },
  { id: 3, address: 'neijiang', parentId: 2 }
];

基本思路：每次递归都遍历整个数组，根据第一项的id来匹配parentId查找其子元素，当然最外层的元素parentId为null。

代码如下：

function mapTree(arrs: any[], id: number) {
  const arr = [];
  for (const item of arrs) {
    if (item.parentId === id) {
      arr.push(item);
      item.children = mapTree(arrs, item.id);
    }
  }
  return arr;
}
//这里初始参数要传null保证最外层元素能匹配，进而被push进数组
//console.log(mapTree(arr, null))

非递归方法

利用map来保存映射关系

 function mapTree(arrs) {
   const list = [];
   const map = new Map();
   arrs.forEach(element => {
     // 做一层浅拷贝,避免对原数组造成影响
     const newElement = {...element};
     if(!newElement.children) {
      newElement.children = [];
     }
     map.set(newElement.id, newElement)
   });

   arrs.forEach(element => {
     const parent = map.get(element.parentId);
     const node = map.get(element.id);
     if(parent) {
       parent.children.push(node);
     } else {
       list.push(node)
     }
   });
   return list
 }


 const mapArr = mapTree(arr);

遍历树形结构

根据某一节点属性来遍历获取结点对象

示例数据：

[
    {
        "id": 1,
        "address": "china",
        "parentId": null,
        "children": [
            {
                "id": 2,
                "address": "sichaun",
                "parentId": 1,
                "children": [
                    {
                        "id": 3,
                        "address": "neijiang",
                        "parentId": 2,
                        "children": []
                    }
                ]
            },
            {
                "id": 4,
                "address": "广州",
                "parentId": 1,
                "children": []
            }
        ]
    }
]

比如我要获取id为4的结点的数据(目前是匹配到第一个符合条件的就返回)。

这里为了灵活的修改判断条件我设置另一个回调函数，这样就可以灵活的配置判断条件了。

const traverseArrays = (
  arrays: any[],
  fn: (data: any) => boolean,
  arrayObj: any = null
): any => {
  for (const item of arrays) {
    //满足就返回
    if (fn(item)) {
      return item;
    //不满足就在子元素中查找
    } else if (item.children) {
      const childrenArrayObj = traverseArrays(item.children, fn);
      //满足就返回
      if (childrenArrayObj) {
        return childrenArrayObj;
      }
    }
  }
  return arrayObj;
};

根据某一结点id获取其所有父节点id

这一个经常用在菜单展开上，我点击菜单id可能需要获取所有父节点菜单id用于记录是否展开。

思路基本和上面的一样。这个是借鉴思否上的一个打来的忘了网址了。

const getParentMenusId = (
  menuList: any[],
  func: (menu: any) => boolean,
  parentId: any[] = []
): any[] => {
  if (!menuList) return [];
  for (const menu of menuList) {
    // 这里按照你的需求来存放最后返回的内容吧
     //包括自身
    parentId.push(menu.id);
   //这里的判断条件我写的是当前路由等于某一结点的url
    if (func(menu)) return parentId;
    if (menu.children) {
      const findChildren = getParentMenusId(menu.children, func, parentId);
      if (findChildren.length) {
        return findChildren;
      }
    }
    parentId.pop();
  }
  return [];
};

将多级的树形结构数据降为二级

在文章开始的时候我们将数据拼接后得到的树形结构是多级的，有时候我们并不需要嵌套这么多层的结构，只需要两个层级的结构，二级以上的都放到二级中，如下：

[
    {
        "id": 1,
        "address": "china",
        "parentId": null,
        "children": [
            {
                "id": 2,
                "address": "sichaun",
                "parentId": 1,
                "children": [
                    {
                        "id": 3,
                        "address": "neijiang",
                        "parentId": 2,
                        "children": []
                    }
                ]
            },
            {
                "id": 4,
                "address": "广州",
                "parentId": 1,
                "children": []
            }
        ]
    }
]

// 处理为嵌套层次最大为二级后
[
    {
        "id": 1,
        "address": "china",
        "parentId": null,
        "children": [
            {
                "id": 2,
                "address": "sichaun",
                "parentId": 1,
            },
            {
                "id": 3,
                "address": "neijiang",
                "parentId": 2,
                "children": []
            }
            {
                "id": 4,
                "address": "广州",
                "parentId": 1,
                "children": []
            }
        ]
    }
]

这种处理方式类似于平铺的处理方式所以我们可以利用广度优先搜索来进行处理
代码如下：

function treeToList(tree) {
   // 队列保存需要处理的
  const queen = [...tree];
  const list = [];
  while (queen.length > 0) {
    const first = queen.shift();
    if (first.children) {
      // 放到队列里去记录
      queen.push(...first.children);
      delete first.children;
    }
    list.push(first);
  }
  return list;
}