JS의 이진 트리에 대한 너비 우선 순회

이진 트리의 호흡 우선 순회는 기본적인 작업입니다.
그럼 내가 이 글을 쓰는 이유는?
구글에서 구현을 빨리 찾으려고 하면 공백이 생기기 때문이다.

대부분의 기사는 이진 머릿단이 아닌 일반 트리를 다룹니다. 따라서 "왼쪽"및 "오른쪽"노드에 대한 개념이 없고 정렬되지 않은 자식만 있습니다.
https://medium.com/@kenny.hom27/breadth-first-vs-depth-first-tree-traversal-in-javascript-48df2ebfc6d1
https://medium.com/@stephaniewo/understanding-breadth-first-tree-traversal-with-javascript-9b8fe670176d
https://gist.github.com/thinkphp/1440007

그리고 이것은 초보자를 혼란스럽게 할 수 있습니다.
this great article at hackernoon과 같은 다른 사람들은 개념을 완벽하게 설명하지만 코드를 제시하지는 않습니다.


Stephanie Wong의 gif

따라서 대기열을 사용하여 this great article at hackernoon에서 너비 우선 순회를 수행하는 방법에 대한 개념을 읽었다고 가정하면 leftright 노드가 있는 이진 트리에 특정한 최신 구현이 있습니다.
(그리고 위의 gif에서와 같이 항상 왼쪽에서 오른쪽으로 이동합니다)

class Tree {
  constructor(value, left, right) {
    this.value = value
    this.left = left
    this.right = right
  }
}

const breadthFirstTraversal = (tree, callback) => {
  if (tree == null) {
    return;
  }

  let queue = [tree]

  while (queue.length > 0) {
    let item = queue.shift()
    let value = item.value
    callback(value)

    if (item.left == null && item.right == null) {
      continue
    }
    if (item.left != null) {
      queue.push(item.left)
    }
    if (item.right != null) {
      queue.push(item.right)
    }
  }
}

t = new Tree(1,
      new Tree(2, null, null), new Tree(3,
        new Tree(4, null, null), null))

breadthFirstTraversal(t, console.log)
// Will print "1,2,3,4"

좋은 웹페이지 즐겨찾기