한 기사로 JavaScript 트리 구조 깊이 우선 알고리즘을 마스터하세요

이 기사에서는 javascript에 대한 관련 지식을 제공합니다. 주로 JavaScript 트리 구조 깊이 우선 알고리즘을 소개합니다. 트리 구조는 DOM 트리와 같이 프런트 엔드에서 가장 일반적인 데이터 구조 중 하나라고 할 수 있습니다. 캐스케이드 선택, 트리 구성요소에 대해 살펴보겠습니다. 모두에게 도움이 되기를 바랍니다.

【관련 추천: javascript 비디오 튜토리얼, web front-end】

나무란 무엇인가

실생활에서는 버드나무, 포플러, 복숭아 등 모든 사람이 나무에 대해 잘 알고 있다고 믿습니다. 나무, 나무는 우리 삶의 모든 곳에서 볼 수 있다고 할 수 있습니다. 컴퓨터 세계에서 나무는 아래 그림과 같이 계층 구조의 추상 모델,

입니다. 트리 구조에는 다양한 응용이 있습니다. 예를 들어 회사의 조직 구조는 아래와 같이 트리로 나타낼 수 있습니다.

조직 구조 외에 계보, 지방, 도시 등도 가능합니다. 트리 구조로 표현되기도 합니다. Tree terminology

Tree에는 아래와 같이 많은 용어가 있습니다.

Tree

: n=0, 이를 빈 트리라고 합니다. <p style="text-align:center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/a03cc2e194bec344e78d0f8742176d17-2.png"></p>노드의 차수<ul>: 노드의 <li>하위 트리<strong> 수, 예를 들어 노드 B의 차수는 2이고 노드 A의 차수는 3입니다. </strong><code>n=0时，称为空树；

节点的度：节点的子树个数，例如B节点的度就是2，A节点的度就是3；

树的度：树的所有节点中最大的度数，例如上图中，树的度是3；

叶子节点：度为0的节点，也叫叶节点；

子节点：如上图；

兄弟节点：如上图；

根节点：如上图；

树的深度：树中所有结点中的最大层次，例如上图中树的深度就是3；

节点的层次：例如E节点的层次就是3，节点的层次就是父节点层次+1，根节点的层次为1；

路径：一个节点到另一个节点的通道，例如A→H的路径就是A D H；

路径长度：一个节点到另一个节点的距离，例如A→H的路径就是3。

JavaScript中的树

树结构可以说是前端中最常见的数据结构之一，比如说DOM树、级联选择、树形组件等等；

JavaScript中并没有提供树这个数据结构，但是我们可以通过对象和数组来模拟一个树，

例如下面这段代码：

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        { value: 'E', children: null },
        { value: 'F', children: null },
      ],
    },
    {
      value: 'C',
      children: [{ value: 'G', children: null }],
    },
    {
      value: 'D',
      children: [
        { value: 'H', children: null },
        { value: 'I', children: null },
      ],
    },
  ],
}

广度优先和深度优点遍历算法

深度优先

所谓的深度优先遍历算法，就是尽可能深的去搜索树的分支，它的遍历顺序如下图：

实现思路如下：

• 访问根节点；
• 对根节点的children持续进行深度优先遍历（递归）；

实现代码如下：

function dfs(root) {
  console.log(root.value)
  root.children && root.children.forEach(dfs) // 与下面一致
  // if (root.children) {
  //   root.children.forEach(child => {
  //     dfs(child)
  //   })
  // }
}
dfs(tree) // 这个tree就是前面定义的那个树
/* 结果
A
B
E
F
C
G
D
H
I
*/

可以看到，和图中的顺序是一致的，也就是说我们的算法没有问题。

广度优先

所谓的广度优先就是依次访问离根节点近的节点，它的遍历顺序如下图：

实现思路如下：

• 创建要给队列，把根节点入队；
• 把队头出队并访问；
• 把队头的children트리의 차수
: 트리의 모든 노드 중 최대 차수입니다. 예를 들어 위 그림에서 트리의 차수는 3입니다.

leaf node

: 차수가 0인 노드입니다. 리프 노드라고도 합니다

자식 노드

: 위 그림에 표시됨

형제 노드: 위에 표시됨.

🎜루트 노드🎜: 위에 표시됨; 🎜: 트리🎜에 있는 모든 노드의 최대 레벨은 예를 들어 위 그림에서 트리의 깊이는 3입니다. 🎜🎜🎜노드의 레벨🎜: 예를 들어 E 노드의 레벨은 3입니다. 노드 수준은 🎜상위 노드 수준 + 1이고 루트 노드 수준은 1입니다. 🎜🎜🎜🎜Path🎜: 🎜한 노드에서 다른 노드로의 채널 🎜, 예를 들어 A→H의 경로는 A D H; 🎜🎜🎜경로 길이🎜: 🎜한 노드에서 다른 노드까지의 거리🎜, 예를 들어 A→H의 경로는 3입니다. 🎜🎜🎜JavaScript의 트리🎜🎜트리 구조는 DOM 트리, 계단식 선택, 트리 구성 요소 등과 같이 프런트 엔드에서 가장 일반적인 데이터 구조 중 하나라고 할 수 있습니다. 🎜🎜트리 데이터 구조는 다음과 같습니다. JavaScript에서는 제공되지 않지만 객체와 배열을 통해 트리를 시뮬레이션할 수 있습니다. 🎜🎜🎜예를 들어 다음 코드는 🎜🎜

function bfs(root) {
  // 1. 新建队列 跟节点入队
  const q = [root]
  // 4 重复执行
  while (q.length > 0) {
    const node = q.shift() // 2 队头出队
    console.log(node.value)
    // 3 队头 children 依次入队
    node.children &&
      node.children.forEach(child => {
        q.push(child)
      })
  }
}
bfs(tree)
/* 结果
A
B
C
D
E
F
G
H
I
*/

🎜폭 우선 및 깊이 이점 순회 알고리즘🎜🎜깊이 우선🎜🎜🎜그래서- 깊이 우선 순회 알고리즘이라고 불리는 것은 트리의 가지를 최대한 깊이 검색하는 것입니다. 순회 순서는 다음과 같습니다: 🎜🎜🎜🎜🎜🎜구현 아이디어는 다음과 같습니다. 🎜🎜🎜🎜루트 노드를 방문합니다. 🎜🎜계속 깊이 우선 탐색(재귀) 뿌리의 node의 children; 🎜🎜🎜🎜구현 코드는 다음과 같습니다.🎜🎜rrreee🎜 순서가 그림과 일치하는 것을 볼 수 있으며 이는 우리 알고리즘에는 문제가 없음을 의미합니다. 🎜🎜폭 우선순위🎜🎜🎜폭 우선순위는 루트 노드에 가장 가까운 노드를 순서대로 방문하는 것입니다. 순회 순서는 다음과 같습니다. 🎜🎜🎜🎜🎜🎜구현 아이디어는 다음과 같습니다. 🎜🎜🎜🎜큐를 생성하고 루트 노드를 큐에 추가합니다. 🎜 🎜대기열의 선두를 제거하고 액세스합니다. 🎜🎜대기열의 선두에 있는 하위 항목을 차례로 대기열에 추가합니다. 🎜🎜대기열이 빌 때까지 2단계와 3단계를 반복합니다. 🎜🎜🎜🎜구현 코드는 다음과 같습니다. 🎜🎜rrreee🎜보시다시피 그림의 순서와 일치하므로 저희 알고리즘에는 문제가 없습니다. 🎜🎜【관련 추천: 🎜javascript 비디오 튜토리얼🎜, 🎜web front-end🎜】🎜

위 내용은 한 기사로 JavaScript 트리 구조 깊이 우선 알고리즘을 마스터하세요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!