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에서 너비 우선 순회를 수행하는 방법에 대한 개념을 읽었다고 가정하면
left
및 right
노드가 있는 이진 트리에 특정한 최신 구현이 있습니다.(그리고 위의 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"
Reference
이 문제에 관하여(JS의 이진 트리에 대한 너비 우선 순회), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/snird/breadth-first-traversal-for-binary-trees-in-js-h9m텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)