js 树形结构查找节点|极客笔记

js 树形结构查找节点

在开发中，我们经常会遇到需要对树形结构数据进行操作的情况。树形结构是一种常见的数据结构，它由节点组成，每个节点有可能包含子节点。在 JavaScript 中，我们经常需要对树形结构进行查找、添加、删除或更新等操作。本文将详细介绍如何使用 JavaScript 来查找树形结构中的特定节点。

什么是树形结构

树形结构是一种非线性数据结构，它包含若干个节点，每个节点最多有一个父节点和多个子节点。树形结构由根节点、内部节点和叶子节点组成。根节点是树的顶层节点，内部节点是位于树中间的节点，叶子节点是位于树底部的节点。树形结构常用来表示层级关系，比如组织结构、文件系统等。

树形结构示例

下面是一个简单的树形结构示例：

{
  name: 'root',
  children: [
    {
      name: 'node1',
      children: [
        {
          name: 'node11',
          children: []
        },
        {
          name: 'node12',
          children: []
        }
      ]
    },
    {
      name: 'node2',
      children: []
    }
  ]
}

在这个示例中，根节点的名称是root，根节点下有两个子节点node1和node2，node1下又有两个子节点node11和node12。

如何查找树形结构中的节点

在实际应用中，我们经常需要查找树形结构中的特定节点。下面我们将介绍如何使用 JavaScript 来查找树形结构中的节点。

递归方法

一种常见的方法是使用递归来遍历树形结构，找出目标节点。下面是一个示例代码：

function findNode(tree, targetName) {
  if(tree.name === targetName) {
    return tree;
  }

  for(let child of tree.children) {
    let found = findNode(child, targetName);
    if(found) {
      return found;
    }
  }

  return null;
}

在这个示例中，findNode函数接受两个参数tree和targetName，其中tree是树形结构数据，targetName是要查找的节点名称。函数首先比较当前节点的名称是否等于targetName，如果相等则返回当前节点。如果当前节点的名称不是目标节点，则递归地查找当前节点的子节点，直到找到目标节点或遍历完整个树。

示例

我们可以使用以下树形结构数据来测试上面的findNode函数：

const treeData = {
  name: 'root',
  children: [
    {
      name: 'node1',
      children: [
        {
          name: 'node11',
          children: []
        },
        {
          name: 'node12',
          children: []
        }
      ]
    },
    {
      name: 'node2',
      children: []
    }
  ]
};

const targetNode = findNode(treeData, 'node11');
console.log(targetNode);

以上代码将会输出如下结果：