알고리즘 ] 트리순회 : 전위순회, 중위 순회, 후위 순회

알고리즘 ] 트리순회 : 전위순회, 중위 순회, 후위 순회

정의

트리 순회(Tree traversal)는 트리 구조에서 각각의 노드를 정확히 한 번만 체계적인 방법으로 방문하는 과정을 말한다.

특징 / 특이사항

트리 순회에는 전위 순회(pre-order), 중위 순회(in-order), 후위 순회(post-order) 등의 방법이 있다.

재귀로 구현한다.

알고리즘 별 특징

1) 전위 순회

트리를 복사하거나 전위 표기법을 구하는데 주로 사용된다.

트리를 복사할 때는 트리를 생성할 때 자식 노드보다 부모 노드가 먼저 생성되어야 하기 때문이다.

출처 : https://yoongrammer.tistory.com/70

순회 결과 : A→B→D→E→C→F→G

2) 중위 순회

출처 : https://yoongrammer.tistory.com/70

순회 결과 : D→B→E→A→F→C→G

2) 후위 순회

후위 순위는 트리를 삭제하는 데 사용된다.

부모 노드를 삭제하기 전에 자식 노드를 삭제하는 순으로 삭제해야 하기 때문이다.

출처 : https://yoongrammer.tistory.com/70

순회 결과 : D→E→B→F→G→C→A

전위 순회, 중위 순회, 후위순회 구현

위의 tree를 class로 구현하면 아래와 같다.

const tree = {}; class Node { constructor(data, left, right) { this.data = data; this.left = left; this.right = right; } } // 자식이 없을 때는 . 으로 표현 const nodes = ['A B C', 'B D E', 'C F G', 'D . .', 'E . .', 'F . .', 'G . .']; nodes.forEach((n) => { const [node, left, right] = n.split(' '); tree[node] = new Node(node, left, right); }); console.log(tree);

전위순회, 중위순회, 후위 순회는 위치만 조정하여 재귀로 간단히 구현할 수 있다.

// 전위순회 function pre_order(node) { console.log(node.data); if (node.left !== '.') { pre_order(tree[node.left]); } if (node.right !== '.') { pre_order(tree[node.right]); } } // 중위순회 function in_order(node) { if (node.left !== '.') { in_order(tree[node.left]); } console.log(node.data); if (node.right !== '.') { in_order(tree[node.right]); } } // 후위순회 function post_order(node) { if (node.left !== '.') { post_order(tree[node.left]); } if (node.right !== '.') { post_order(tree[node.right]); } console.log(node.data); }

위의 그래프를 각각의 순회로 실행하면

pre_order(tree['A']); console.log('_______________________________'); in_order(tree['A']); console.log('_______________________________'); post_order(tree['A']);

다음과 같은 결과를 얻을 수 있다.

A B D E C F G

_______________________________

D B E A F C G

_______________________________

D E B F G C A

from http://jibsun-i.tistory.com/22 by ccl(A) rewrite - 2021-11-01 22:26:47