JavaScript의 트리 스트리밍 기술

나무는 재미있는 데이터 구조의 하나다.그것은 각 분야에서 광범위하게 응용되고 있다.
예를 들면 다음과 같습니다.

DOM은 트리 데이터 구조

입니다.

운영체제의 디렉터리와 파일은 트리로 표시할 수 있다

족 차원 구조는 나무로 표시할 수 있다.

트리에는 많은 변체(예를 들어 쌓기, BST 등)가 있는데 스케줄링, 이미지 처리, 데이터베이스 등과 관련된 문제를 해결하는 데 사용된다. 많은 복잡한 문제는 트리와 무관해 보일 수 있지만 실제로는 하나로 나타낼 수 있다.우리도 이 문제들(본 시리즈의 뒷부분)을 토론해서 나무가 복잡해 보이는 문제를 어떻게 쉽게 이해하고 해결할 수 있는지 볼 것이다.

소개하다.

두 갈래 나무를 위한 실현Node은 매우 간단하다.

function Node(value){
  this.value = value
  this.left = null
  this.right = null
}
// usage
const root = new Node(2)
root.left = new Node(1)
root.right = new Node(3)

이 코드는 다음과 같이 두 갈래 트리를 생성합니다.

        2  
      /  \
     1    3
   /        \
null       null

쿨!그래서 쉬워요.지금 우리는 그것을 어떻게 사용합니까?

통과

연결된 나무 노드 (또는 나무) 를 훑어보는 것부터 시작합시다.우리가 수조를 두루 돌아다닐 수 있는 것처럼, 우리도 나무 노드를 두루 돌아다닐 수 있다면 정말 멋있을 것이다.그러나 나무는 수조와 같은 선형 데이터 구조가 아니기 때문에 이 나무들을 두루 훑어보는 방법은 한 가지가 아니다.우리는 대개 반복 방법을 다음과 같은 몇 가지로 나눌 수 있다.

너비 우선 스트리밍

깊이 우선 순위

BFS

이런 방법에서 우리는 한 단계 한 단계 나무를 두루 돌아다닌다.우리는 뿌리부터 시작해서 모든 아이를 덮을 것이다. 우리는 모든 2급 아이를 덮을 것이다.
예를 들어, 위의 트리에 대해 다음 결과가 반복됩니다.

2, 1, 3

다음은 좀 더 쉽게 이해할 수 있도록 복잡한 트리 그래프입니다.

이런 형식의 반복을 실현하기 위해서 우리는 대기열(선진 선출) 데이터 구조를 사용할 수 있다.다음은 전체 알고리즘의 모습이다.

루트가 있는 대기열을 시작합니다

.

대기열에서 첫 번째 항목 제거

팝업 항목의 좌우 하위 항목을 대기열에 밀어넣기

큐가 비어 있을 때까지 2단계와 3단계를 반복합니다

.
다음은 이 알고리즘이 실현된 후의 모습이다.

function walkBFS(root){
  if(root === null) return

  const queue = [root]
  while(queue.length){
      const item = queue.shift()
      // do something
      console.log(item)

      if(item.left) queue.push(item.left)
      if(item.right) queue.push(item.right)
   }
}

위의 알고리즘을 약간 수정하여 각 내부 배열은 다음 요소를 포함하는 레벨을 나타내는 배열 배열을 반환할 수 있습니다.

function walkBFS(root){
  if(root === null) return

  const queue = [root], ans = []

  while(queue.length){
      const len = queue.length, level = []
      for(let i = 0; i < len; i++){
          const item = queue.shift()
          level.push(item)
          if(item.left) queue.push(item.left)
          if(item.right) queue.push(item.right)
       }
       ans.push(level)
   }
  return ans
}

DFS

DFS에서 우리는 노드를 하나 취하여 깊이가 다 소모될 때까지 그것의 하위 노드를 계속 탐색했다.다음 방법 중 하나를 사용할 수 있습니다.

 root node -> left node -> right node // pre-order traversal
 left node -> root node -> right node // in-order traversal
 left node -> right node -> root node // post-order traversal

이 모든 역행 기술은 점차적으로 실현될 수도 있고, 교체적으로 실현될 수도 있다.세부 사항에 대한 논의를 시작하겠습니다.

사전 순차

다음은 트리의 사전 순서가 반복되는 모양입니다.

 root node -> left node -> right node 

팁:

우리는 이 간단한 기교를 사용하여 수동으로 모든 나무의 앞뒤를 찾아낼 수 있다. 뿌리 노드부터 전체 나무를 훑어보고 왼쪽을 유지할 수 있다.

구현:

우리들은 이런 두루 겪은 실제 실현을 깊이 연구합시다.
귀속 방법은 상당히 직관적이다.

function walkPreOrder(root){
  if(root === null) return

  // do something here
  console.log(root.val)

  // recurse through child nodes
  if(root.left) walkPreOrder(root.left)
  if(root.right) walkPreOrder(root.left)
}

미리 순차적으로 반복되는 교체 방법은 BFS와 매우 비슷합니다. 다른 점은 우리가 stack 대신 queue를 사용했기 때문입니다. 그리고 우리는 먼저 정확한 하위 항목을 대기열에 밀어 넣었습니다.

function walkPreOrder(root){
  if(root === null) return

  const stack = [root]
  while(stack.length){
      const item = stack.pop()

      // do something
      console.log(item)

      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}

순차적

다음은 나무의 순서대로 옮겨다니는 것이다.

left node -> root node -> right node 

팁:

우리는 이 간단한 기교를 사용하여 임의의 나무의 질서정연한 흐름을 수동으로 찾을 수 있다. 나무의 밑에 수평으로 평면 거울을 놓고 모든 노드의 투영을 얻을 수 있다.

구현:

반복:

function walkInOrder(root){
  if(root === null) return

  if(root.left) walkInOrder(root.left)

 // do something here
  console.log(root.val)

  if(root.right) walkInOrder(root.right)
}

반복:

function walkInOrder(root){
  if(root === null) return

  const stack = []
  let current = root

  while(stack.length || current){
      while(current){
         stack.push(current)
         current = current.left
      }
      const last = stack.pop()

      // do something
      console.log(last)

      current = last.right
   }
}

후순이 두루 다니다

다음은 나무의 뒷순서가 옮겨다니는 모습이다.

 left node -> right node -> root node 

팁:

모든 나무의 빠른 수동 후순 반복: 맨 왼쪽의 잎 노드를 하나씩 잡습니다.

구현:

우리들은 이런 두루 겪은 실제 실현을 깊이 연구합시다.
반복:

function walkPostOrder(root){
  if(root === null) return

  if(root.left) walkPostOrder(root.left)
  if(root.right) walkPostOrder(root.right)

  // do something here
  console.log(root.val)

}

반복:

function walkPostOrder(root){
  if(root === null) return []

  const tempStack = [root], mainStack = []

  while(tempStack.length){
      const last = tempStack.pop()

      mainStack.push(last)

      if(last.left) tempStack.push(last.left)
      if(last.right) tempStack.push(last.right)
    }

    return mainStack.reverse()
}

보상:JavaScript 프롬프트

만약 우리가 아래의 방식 중 하나를 통해 이 나무를 가로질러 갈 수 있다면 얼마나 좋을까.

 for(let node of walkPreOrder(tree) ){
   console.log(node)
 }

정말 예뻐 보이고 읽기도 간단하지 않나요?우리가 해야 할 일은 walk 함수를 사용하면 교체기를 되돌려 주는 것이다.
다음은 위에서 공유한 예제에 따라 위의 함수walkPreOrder를 수정하는 방법입니다.

function* walkPreOrder(root){
   if(root === null) return

  const stack = [root]
  while(stack.length){
      const item = stack.pop()
      yield item
      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}

본문은 최초로 발표되었다StackFull.dev.더 많은 글을 삭제할 때 알림을 받고 싶으면 구독을 고려하십시오. newsletter