트리 순회 알고리즘

트리 순회 알고리즘

트리의 모든 노드들을 방문하는 트리 순회 알고리즘에는 3가지 방법이 있다.

전위 순회 (Preorder)

중위 순회 (Inorder)

후위 순회 (Postorder)

위 3가지 방법 모두 재귀로 구현할 수 있다.

전위 순회 (Preorder)

전위 순회는 주로 트리를 복사할 때 사용되는 방법이다.

하나의 노드를 방문했을 때 다음과 같은 순서로 진행된다.

루트 노드 방문 왼쪽 자식 노드 방문 오른쪽 자식 노드 방문

const tree=[[1,2],[3,4],[5,6],[.,.],[.,.],[.,.],[.,.]]; /* node 0 ~ 6을 포함한 트리를 2D 배열로 표현 각 노드별로 왼쪽 오른쪽 자식 노드를 배열로 표현 .은 자식 노드가 없음을 표현 0 / \ 1 2 / \ / \ 3 4 5 6 */ function preorder(node){ if(node == '.'){ return; } console.log(node) preorder(tree[node][0]); //0번이 왼쪽 노드 preorder(tree[node][1]); //1번이 오른쪽 노드 } preorder(0);

결과값은 0 1 3 4 2 5 6 이 나온다.

중위 순회 (Inorder)

하나의 노드를 방문했을 때 다음과 같은 순서로 진행된다.

왼쪽 자식 노드 방문 루트 노드 방문 오른쪽 자식 노드 방문

const tree=[[1,2],[3,4],[5,6],[.,.],[.,.],[.,.],[.,.]]; /* node 0 ~ 6을 포함한 트리를 2D 배열로 표현 각 노드별로 왼쪽 오른쪽 자식 노드를 배열로 표현 .은 자식 노드가 없음을 표현 0 / \ 1 2 / \ / \ 3 4 5 6 */ function inorder(node){ if(node == '.'){ return; } inorder(tree[node][0]); //0번이 왼쪽 노드 console.log(node) inorder(tree[node][1]); //1번이 오른쪽 노드 } inorder(0);

결과값은 3 1 4 0 5 2 6 이 나온다.

후위 순회 (Postorder)

주로 트리를 삭제하는 데 사용된다.

하나의 노드를 방문했을 때 다음과 같은 순서로 진행된다.

왼쪽 자식 노드 방문 오른쪽 자식 노드 방문 루트 노드 방문

tree=[[1,2],[3,4],[5,6],[.,.],[.,.],[.,.],[.,.]]; /* node 0 ~ 6을 포함한 트리를 2D 배열로 표현 각 노드별로 왼쪽 오른쪽 자식 노드를 배열로 표현 .은 자식 노드가 없음을 표현 0 / \ 1 2 / \ / \ 3 4 5 6 */ function postorder(node){ if(node == '.'){ return; } postorder(tree[node][0]); //0번이 왼쪽 노드 postorder(tree[node][1]); //1번이 오른쪽 노드 console.log(node) } postorder(0);

결과값은 3 4 1 5 6 2 0 이 나온다.

from http://jjakddo-studio.tistory.com/10 by ccl(A) rewrite - 2021-11-28 23:00:25