이진 트리의 순회

기본적으로 이진 트리도 데이터를 저장하기 위한 자료구조이다. 데이터는 노드의 데이터 필드를 이용하여 저장된다. 이진 트리를 순회(traversal)한다는 것은 이진트레이 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다.  트리가 가지고 있는 자료를 순차적으로 순회하는 것은 이진 트리에서 중요한 연산이다. 스택, 큐들은 대게 데이터를 선형으로 저장하고 순회하는 방법도 하나뿐이었지만, 트리는 3가지가 있다.

 

 

이진 트리 순회방법

• 전위순회(preorder traversal) : VLR
• 중위순회(inorder traversal) : LVR
• 후위순회(postorder traversal) : LRV

 

1. 전위순회

전위순회는 먼저 루트, 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문한다

 

1. 루트노드를 먼저 방문한다
2. 왼쪽 서브트리를 방문한다
3. 오른쪽 서브트리를 방문한다.

 

이런 트리의 구조일 때 전위순회 라면 -  *  A  B  /  C  D 순으로 방문을 하게 된다. 

   public void preorder(TreeNode root){
        if(root!=null){
            System.out.print(root.data + " ");
            preorder(root.left);
            preorder(root.right);
        }
    }

 

자바로 구현하게 되면 이렇게 구현을 할 수 있다. 재귀함수와 if 문을 이용해서 구현을 하게 된다.

 

 

2. 중위순회 

중위순회는 먼저 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문한다.

 

1. 왼쪽 서브트리를 방문한다.
2. 루트노드를 방문한다.
3. 오른쪽 서브트리를 방문한다.

 

아까와 같이 이런 트리일 때 중위순회를 하면 A * B - C  /  D 순으로 방문을 하게 된다. 

public void inorder(TreeNode root){
        if(root!=null){
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

 자바로 구현을 했고, 전위순회와 순서만 바꿔주면 구현이 가능하다.

 

 

3. 후위순회

후위순회는 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문한다. 

 

1. 왼쪽 서브트리의 모든 노드를 방문한다
2. 오른쪽 서브트리의 모든 노드를 방문한다.
3. 루트노드를 방문한다.

 

후위순회도 똑같이 위와 같은 이진트리에서 순회를 해보면  A B  *  C  D  /  - 순으로 순회를 하게된다.

 

  public void postorder(TreeNode root){
        if(root!=null){
            postorder(root.left);
            postorder(root.right);
            System.out.print(root.data + " ");
        }
    }