5,267 판독값

JavaScript의 트리 순회 탐색: 예제를 통한 중순, 선순, 후순

~에 의해 Anton Nikiforov7m2023/05/29

너무 오래; 읽다

트리 순회는 트리 데이터 구조의 각 노드를 체계적으로 방문하는 컴퓨터 과학의 기본 개념입니다. 트리 순회를 통해 미리 결정된 순서로 노드를 처리할 수 있어 검색, 정렬, 표현식 평가와 같은 작업이 용이해집니다. 이 글에서는 가장 널리 사용되는 세 가지 트리를 살펴보겠습니다. 순회 방법: 중순, 선순, 후순.

featured image - JavaScript의 트리 순회 탐색: 예제를 통한 중순, 선순, 후순

트리 순회는 트리 데이터 구조의 각 노드를 체계적으로 방문하는 컴퓨터 과학의 기본 개념입니다. 트리 순회를 통해 미리 결정된 순서로 노드를 처리할 수 있어 검색, 정렬, 표현식 평가와 같은 작업이 용이해집니다.

이 글에서는 가장 널리 사용되는 세 가지 트리 순회 방법인 중위순서(Inorder), 사전 순서(Preorder), 사후 순서(Postorder)를 살펴보겠습니다.

JavaScript로 구현된 명확하고 간결한 예제를 통해 이러한 순회 기술에 대한 확실한 이해를 얻을 수 있습니다.

트리 구조 정의

트리 순회 알고리즘을 살펴보기 전에 이진 트리에 사용할 구조를 정의해 보겠습니다. 트리는 노드로 구성되며, 각 노드에는 왼쪽 및 오른쪽 하위 노드에 대한 값과 참조가 포함됩니다.

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

이제 트리 구조를 정의했으므로 세 가지 트리 탐색 방법을 탐색할 수 있습니다.

중위순회

중위 순회는 이진 트리의 노드를 방문하는 다음 패턴을 따릅니다. 알고리즘은 먼저 왼쪽 하위 트리를 순회한 다음 현재 노드를 방문하고 마지막으로 오른쪽 하위 트리를 순회합니다. 이렇게 하면 트리가 정렬된 데이터 구조를 나타내는 경우 노드가 오름차순으로 방문됩니다.

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

재귀적 중순 순회

현재 노드가 null인지 확인하십시오. 그렇다면 돌아가십시오.
왼쪽 하위 트리에서 함수를 재귀적으로 호출합니다.
현재 노드를 방문합니다.
오른쪽 하위 트리에서 함수를 재귀적으로 호출합니다.

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

비재귀적 중위순회

빈 스택을 초기화하고 현재 노드를 트리의 루트로 설정합니다.
스택이 비어 있지 않거나 현재 노드가 null이 아닌 동안 반복합니다.
- null 왼쪽 자식에 도달할 때까지 모든 왼쪽 노드를 스택에 푸시합니다.
- 스택에서 노드를 팝하고 방문하여 현재 노드를 오른쪽 자식으로 설정합니다.
스택이 비어 있고 현재 노드가 null이 될 때까지 2단계를 반복합니다.

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

선주문 순회

선주문 순회에서 알고리즘은 먼저 현재 노드를 방문한 다음 왼쪽 하위 트리를 순회하고 마지막으로 오른쪽 하위 트리를 순회합니다. 이 순서를 사용하면 루트에서 시작하여 리프를 향해 이동하는 "하향식" 방식으로 노드를 방문할 수 있습니다.

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

재귀적 선주문 순회

현재 노드가 null인지 확인하십시오. 그렇다면 돌아가십시오.
현재 노드를 방문합니다.
왼쪽 하위 트리에서 함수를 재귀적으로 호출합니다.
오른쪽 하위 트리에서 함수를 재귀적으로 호출합니다.

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

비재귀적 선주문 순회

빈 스택으로 시작하고 루트 노드를 스택에 푸시합니다.
선주문 순회 결과를 저장하기 위해 빈 배열을 초기화합니다.
스택이 빌 때까지 실행되는 while 루프를 입력합니다.
스택에서 노드를 팝하고 결과 배열에 해당 값을 추가하여 방문합니다.
노드에 오른쪽 자식이 있으면 오른쪽 자식을 스택에 푸시합니다.
노드에 왼쪽 자식이 있는 경우 왼쪽 자식을 스택에 푸시합니다.
스택이 빌 때까지 3~6단계를 반복합니다.

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

후순위 순회

이 순회에서 알고리즘은 먼저 왼쪽 하위 트리를 순회한 다음 오른쪽 하위 트리를 순회하고 마지막으로 현재 노드를 방문합니다. 이 순서를 사용하면 리프에서 시작하여 루트를 향해 이동하는 "상향식" 방식으로 노드를 방문할 수 있습니다.

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

재귀적 후순 순회

현재 노드가 null인지 확인하십시오. 그렇다면 돌아가십시오.
왼쪽 하위 트리에서 함수를 재귀적으로 호출합니다.
오른쪽 하위 트리에서 함수를 재귀적으로 호출합니다.
현재 노드를 방문합니다.

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

비재귀적 후순 순회

빈 스택으로 시작하고 루트 노드를 스택에 푸시합니다.
후위 순회 결과를 저장하기 위해 빈 배열을 초기화합니다.
스택이 빌 때까지 실행되는 while 루프를 입력합니다.
(제거하지 않고) 스택에서 최상위 노드를 가져옵니다.
노드에 왼쪽 자식이 있는 경우 왼쪽 자식을 스택에 푸시하고 현재 노드의 왼쪽 자식을 null로 설정합니다.
노드에 오른쪽 자식이 있는 경우 오른쪽 자식을 스택에 푸시하고 현재 노드의 오른쪽 자식을 null로 설정합니다.
노드에 왼쪽 자식과 오른쪽 자식이 모두 없으면 리프 노드입니다. 스택에서 노드를 팝하고 해당 값을 결과 배열에 추가합니다.
스택이 빌 때까지 4~7단계를 반복합니다.

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }