홈페이지>웹 디자인 튜토리얼>자바스크립트 튜토리얼

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

저자：Eve Cole 업데이트 시간：2022-07-26 11:50:14
이 기사에서는 JavaScript에 대한 관련 지식을 제공하며 주로 JavaScript 트리 구조 깊이 우선 알고리즘을 소개합니다. 트리 구조는 DOM 트리, 계단식 선택, 트리 모양 구성 요소와 같은 프런트 엔드에서 가장 일반적인 데이터 구조 중 하나라고 할 수 있습니다. , 함께 살펴 보겠습니다. 모두에게 도움이 되길 바랍니다.

실생활 에서

나무란 무엇입니까?

버드나무든, 포플러나무든, 복숭아나무든, 나무는 우리 삶의 모든 곳에서 볼 수 있지만 나무는 추상화입니다.

아래와 같이

계층적 구조를 갖습니다

.

예를 들어, 회사의 조직 구조는 아래와 같이 트리로 표현될 수 있습니다.

조직 구조 외에도 가계도, 지방, 도시 등을 트리 구조를 사용하여 표현할 수 있습니다.

트리 용어

아래와 같이 트리에 대한 많은 용어가 있습니다.

  • 트리 : n(n≥0) 노드의 유한 집합입니다. n=0 이면 빈 트리라고 합니다
  • . 노드 차수 : 노드 B의 차수 는 2입니다. 노드 A의 차수는 3입니다.
  • 트리의 차수 는 트리의 모든 노드 중 최대 차수입니다. 예를 들어 위 그림에서 트리의 차수는 3
  • 입니다 . , 리프 노드라고도 함 ;
  • 하위 노드 : 위 그림에 표시됨;
  • 루트 노드
  • : 위 그림에 표시됨.
  • 트리 깊이 : 트리의 모든 노드 중 최대 레벨 예를 들어 위 그림에서 트리의 깊이는 3입니다.
  • 노드 수준 : 예를 들어 E 노드의 수준은 3이고 노드 수준은 상위 노드 수준 + 1이며 루트 노드의 수준은 1입니다. ;
  • 경로 : 한 노드에서 다른 노드로의 채널 , 예를 들어 A→H의 경로는 ADH 입니다.
  • 경로 길이 : A→H의 경로와 같이 한 노드에서 다른 노드까지의 거리 입니다.

JavaScript의 트리 구조는

DOM 트리, 계단식 선택, 트리 구성 요소 등과 같이 프런트 엔드에서 가장 일반적인 데이터 구조 중 하나라고 할 수 있습니다.

JavaScript는 트리 데이터 구조를 제공하지 않지만 사용할 수 있습니다.

다음 코드와 같이

트리를 시뮬레이션하기 위한 객체 및 배열

: 
const tree = {
  값: 'A',
  어린이들: [
    {
      값: 'B',
      어린이들: [
        { 값: 'E', 하위 항목: null },
        { 값: 'F', 하위 항목: null },
      ],
    },
    {
      값: 'C',
      어린이: [{ 값: 'G', 어린이: null }],
    },
    {
      값: 'D',
      어린이들: [
        { 값: 'H', 하위 항목: null },
        { 값: '나', 하위: null },
      ],
    },
  ],
}

너비 우선 및 깊이 순회 알고리즘의 장점

깊이 우선

소위 깊이 우선 순회 알고리즘은 트리의 가지를 최대한 깊이 검색하는 것입니다. 순회 순서는 다음과 같습니다.

구현 아이디어는 다음과 같습니다.

  • 루트 노드를 방문하고
  • 루트 노드의 children 에 대한 깊이 우선 탐색(재귀)을 계속합니다.

구현 코드는 다음과 같습니다.

function dfs(root) {
  console.log(루트.값)
  root.children && root.children.forEach(dfs) // 다음과 일치 // if (root.children) {
  // root.children.forEach(child => {
  //dfs(자식)
  // })
  // }
}
dfs(tree) //이 트리는 이전에 정의된 트리입니다./* 결과 A
비
이자형
에프
기음
G
디
시간
나
*/

보시다시피 순서가 그림과 일치하므로 우리 알고리즘에는 문제가 없습니다.

폭 우선

순위(Breadth Priority)

소위 폭 우선순위(Breadth Priority)는 루트 노드에 가장 가까운 노드를 순서대로 방문하는 것입니다.

구현 아이디어는 다음과 같습니다.

  • 대기열을 만들고, 대기열에 루트 노드를 추가하고,
  • 대기열
    • 의 헤드를 제거
  • children 해당 대기열에
  • 액세스합니다.
  • 대기열이 비어 있습니다.

구현 코드는 다음과 같습니다:

function bfs(root) {
  // 1. 새 대기열을 만들고 대기열에 노드를 추가합니다. const q = [root]
  // 4 반복하는 동안 (q.length > 0) {
    const node = q.shift() // 2개의 큐 헤드가 큐에서 제거됨 console.log(node.value)
    // 팀장인 3명의 어린이가 팀에 추가됩니다. node.children &&
      node.children.forEach(자식 => {
        q.push(자식)
      })
  }
}
BFS(트리)
/* 결과 A
비
기음
디
이자형
에프
G
시간
나
*/

보시다시피 순서가 그림과 일치하므로 우리 알고리즘에는 문제가 없습니다.
관련 기사