[JavaScript] 트리 순회

트리 순회

Tree traversal
트리 구조에서 각각의 노드를 한 번씩 방문하는 과정

대표적인 트리 순회로는 4가지가 존재한다

• postorder traversal
• preorder traversal
• inorder traversal
• levelorder traversal

Postorder Traversal

후위순회

post -> ~이후 라는 뜻처럼 child가 먼저 순회되고, 자신이 순회되는 방식이다.

Postorder Traversal Psudocode

postOrder(node) {
	if (node not visited)
    	postOrder(node -> left child)
		postOrder(node -> right child)
		visited[node] = true
}
	

Preorder Traversal

전위순회

pre -> ~이전 라는 뜻처럼 자신 (부모)가 먼저 순회되고, 자식이 순회되는 방식이다.

Preorder Traversal Psudocode

preOrder(node) {
	if (node not visited)
    	visited[node] = true
        preOrder(node -> left child)
        preOrder(node -> right child)
}

Inorder Traversal

중위 순회

in -> ~안 라는 뜻처럼 자신이 가운데에서 순회되는 방식

Inorder Traversal Psudocode

inOrder(node) {
	if (node not visited) {
		inOrder(node -> left child)
        visited[node] = true
        inOrder(node -> right child)
	}
}

Levelorder Traversal

레벨 순회

BFS 알고리즘과 동일하다

visited[next] = visited[prev] + 1

다음과 같이 트리의 level을 얻을 수 있다

구현

const adj = [
  [],
  [2, 3],
  [4, 5],
  [],
  [],
  []
]

const postOrder = (node, visited, result) => {
  if (!visited[node]) {
    const children = adj[node]
    children.forEach(child => postOrder(child, visited, result))
    result.push(node)
    visited[node] = true

    return result
  }
}

const preOrder = (node, visited, result) => {
  if (!visited[node]) {
    const children = adj[node]
    result.push(node)
    visited[node] = true
    children.forEach(child => preOrder(child, visited, result))

    return result
  }
}

const inOrder = (node, visited, result) => {
  if (!visited[node]) {
    const children = adj[node];
    if (children.length > 0) inOrder(children[0], visited, result)
    result.push(node)
    visited[node] = true;
    if (children.length > 1) inOrder(children[1], visited, result)

    return result
  }
}

const levelOrder = (node, visited, result) => {
  const queue = [node]
  visited[node] = true
  result.push(node)
  
  while(queue.length > 0) {
    const p = queue.shift()
    adj[p].forEach(child => {
      if (!visited[child]) {
        visited[child] = true
        result.push(child)
        queue.push(child)
      }
    })
  }

  return result
}

const orders = [postOrder, preOrder, inOrder, levelOrder]
orders.forEach(orderFn => {
  const visited = Array(5 + 1).fill(false)
  // node, visited, result
  console.log(`${orderFn.name}: [${orderFn(1, visited, [])}]`)
})

결과

postOrder: [4,5,2,3,1]
preOrder: [1,2,4,5,3]
inOrder: [4,2,5,1,3]
levelOrder: [1,2,3,4,5]

개선 사항

Level Order (BFS)에 대한 자세한 내용은 BFS 블로그 글을 참고하길 바란다.

https://velog.io/@gomteng03/JavaScript-BFS