트리 순회 알고리즘

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

 

• 전위 순회 (Preorder)
• 중위 순회 (Inorder)
• 후위 순회 (Postorder)

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

전위 순회 (Preorder)

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

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

 

1. 루트 노드 방문
2. 왼쪽 자식 노드 방문
3. 오른쪽 자식 노드 방문

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)

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

 

1. 왼쪽 자식 노드 방문
2. 루트 노드 방문
3. 오른쪽 자식 노드 방문

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)

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

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

 

1. 왼쪽 자식 노드 방문
2. 오른쪽 자식 노드 방문
3. 루트 노드 방문

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 이 나온다.