트리의 순회

inorder(node)
  if node.left  ≠ null then inorder(node.left)
  print node.value
  if node.right ≠ null then inorder(node.right)

대표적으로 3가지 순회 방법이 있다

 

전위 순회(preorder)

 

전위 순회의 방법

1. 노드를 방문한다.

2. 왼쪽 서브 트리를 전위 순회한다.

3.오른쪽 서블 트리를 전위 순회한다.

 

전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.

 

public void preorder(Node node){

    System.out.println(node.value);
    
    if(node.left != null){
    	preorder(node.left);
    }

    if(node.right != null){
    	preorder(node.right)
    }

}

 

 

중위 순회 → BST요소들을 정렬해 출력하는 기능(중요)

중위 순회(Inorder)는 다음 순서로 진행

 

1. 왼쪽 서브 트리를 중외 순회한다.

2. 노드를 방문한다.

3. 오른쪽 서브 트리를 중위 순회한다.

 

중위 순회는 대칭 순회(symmetric)이라고도한다.

public void preorder(Node node){

    if(node.left != null){
    	preorder(node.left);
    }
    
	System.out.println(node.value);
    
    if(node.right != null){
    	preorder(node.right);
    }

}

 

 

 

후위 순회

후위 순회(postorder)는 다음과 같은 방법으로 진행한다.

 

1.왼쪽 서브 트리를 후위 순회한다.

2.오른쪽 서브 트리를 후위 순회한다.

3.노드를 방문한다.

 

public void preorder(Node node){

    if(node.left != null){
    	preorder(node.left);
    }
    
    if(node.right != null){
    	preorder(node.right);
    }
    
    System.out.println(node.value);

}

 

순회 종류별 방문순서