一文吃透JS树状结构的数据处理(增删改查)

什么是树状结构

树状结构是一种经典的数据结构，在计算机领域中被广泛应用。树状结构由连通的节点组成，节点之间形成父子关系。一根树状结构的“根节点”没有父节点，每个子节点可以有多个“子节点”，但一个“子节点”只能有一个“父节点”。常见的应用包括文件系统、HTML DOM 和 JSON 数据格式等。

数据结构设计

我们以一个图书分类的树状结构为例进行说明，结构如下所示：

const data = [{
    id: 1,
    label: "文学",
    children: [{
        id: 2,
        label: "小说",
        children: [{
            id: 3,
            label: "现代小说"
          },
          {
            id: 4,
            label: "言情小说"
          }
        ]
      },
      {
        id: 5,
        label: "散文",
        children: [{
          id: 6,
          label: "古代散文"
        }]
      }
    ]
  },
  {
    id: 7,
    label: "科学",
    children: [{
      id: 8,
      label: "数学"
    }]
  }
];

我们可以看到每个节点都包含了一个 ID、标签和一个子节点数组。而子节点数组中的每个元素都是一个字典，包含了对应子节点的 ID、标签和子节点数组。

在开发过程中，我们经常需要对这样的树状结构做一些基本操作，如：增加、删除、修改、查找等。接下来，我们将分别讨论这些操作的实现方法。

增加节点

在上面的数据结构中，每个节点包含了一个固定格式的字典，我们可以通过以下方式来向树状结构中添加节点：

const addChild = (parentId, child) => {
  const parent = data.find(item => item.id === parentId);
  if (parent.children) {
    parent.children.push(child);
  } else {
    parent.children = [child];
  }
};

这个函数接收两个参数：parentId 代表要添加子节点的父节点 ID，child 代表要添加的子节点。首先我们通过 find 方法来查找 parent，然后判断是否已经有了子节点，如果有，就直接将新的子节点添加进去；如果没有，就新建一个空数组，再将子节点加入进去。

删除节点

删除节点是一个比较麻烦的操作，因为我们需要做到 “删除一个节点的同时，也要删除它的所有子节点”。下面是一个关于如何删除节点的示例：

const removeNode = (id) => {
  const recursive = (data, id) => {
    for (let i = 0; i < data.length; i++) {
      if (data[i].id === id) {
        data.splice(i, 1)
        break
      } else if (Array.isArray(data[i].children)) {
        recursive(data[i].children, id)
      }
    }
  }
  recursive(data, id)
}

这个函数接收一个 id 参数，表示要删除的节点 ID。它首先定义了一个内部递归函数 recursive，该函数接收两个参数，并进行递归删除节点操作。递归函数中，首先判断数组中元素的 id 是否等于传入的 id，如果等于就从数组中删除该元素；否则，递归遍历该元素的子节点，进行相同的操作。

修改节点

修改节点比增加和删除操作简单些。首先，我们需要找到要修改的节点，然后将其属性改为所需要的值即可。下面是一个示例代码：

const updateNode = (id, label) => {
  const update = (id, label, data) => {
    for (let i = 0; i < data.length; i++) {
      if (data[i].id === id) {
        data[i].label = label;
        break;
      } else if (Array.isArray(data[i].children)) {
        update(id, label, data[i].children)
      }
    }
  }
  update(id, label, data)
}

这个函数接收两个参数：id 表示要修改的节点 ID，label 表示要修改的标签。该函数通过递归遍历所有子节点，找到要修改的节点，然后进行修改。

查找节点

查找节点也是一项常见操作，我们可以通过递归来实现。下面是一个示例代码：

const findNode = (data, id) => {
  for (let i = 0; i < data.length; i++) {
    if (data[i].id === id) {
      return data[i];
    } else if (Array.isArray(data[i].children)) {
      const result = findNode(data[i].children, id);
      if (result !== null) {
        return result;
      }
    }
  }
  return null;
};

这个函数接收两个参数：data 表示要查找的数据，id 表示要查找的节点 ID。首先遍历每个节点，找到要查找的节点，返回该节点；否则，递归遍历该元素的所有子节点，查找相同的节点 ID。

总结

树状结构是一种非常常用的数据结构，因此在开发过程中，我们经常需要对树状数据进行增删改查的操作。上述这些操作可以通过递归遍历进行实现。同时，我们也可以通过不同方式修改这些操作的逻辑，例如使用深度优先遍历代替示例中的广度优先搜索。