트리

이번 포스팅에서는 트리에 대해서 알아보려고 합니다.

 

트리는 비선형 자료구조로 자료간의 포함관계, 상하위 관계와 같은 계층 구조를 표현할 수 있는 자료구조 입니다.

 

아래 그림은 각 자료간 포함관계를 표현합니다.

 

트리 관련 용어

트리는 노드와 간선들로 구성되어 있고, 각 노드는 간선을 사이에 두고 상위, 하위 관계를 가지게 됩니다.

여기서 상위 노드는 부모, 하위 노드는 자식이라고 부릅니다.

여기서 특징은 무조건 부모는 하나여야 합니다. 그렇기 때문에 트리는 가장 최상위 부모를 루트(root) 라는 용어로 부릅니다. 그리고 트리의 최하위 노드는 리프(leaf)라고 부릅니다.

 

트리는 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 해당 노드의 깊이라고 합니다.

리프 노드의 깊이를 트리의 높이(height) 라고 합니다.

 

• 부모 : 상위 노드
• 자식 : 하위 노드
• 루트 : 최상위 노드
• 리프 : 최하위 노드
• 높이 : 루트에서 리프 노드 사이의 간선의 수

 

트리의 재귀적 속성

트리가 가장 많이 사용되는 이유는 트리의 재귀적 속성 때문입니다.

노드를 하나 선택하면 그 노드와 해당 노드의 하위 트리로도 하나의 트리를 만들 수 있습니다.

 

빨간색 영역의 트리도 트리라고 볼 수 있고, 파란색 영역의 트리도 마찬가지 입니다.

이런 트리들을 가리켜 서브트리(subtree) 라고합니다.

모든 트리는 위와 같이 루트 노드와 하위의 서브 트리들의 집합입니다.

이런 특성 때문에 트리 자료구조를 이용하는 알고리즘들은 보통 재귀함수를 통해 구현됩니다.

 

트리 구현

 

노드 구현

public class TreeNode {
    TreeNode left;
    TreeNode right;
    int data;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }


}

 

 

순회

트리는 자료구조로, 자료구조의 목적은 데이터의 효율적인 저장 및 탐색/조작 입니다. 트리를 조직적이고 체계적으로 방문하는 것을 트리의 순회라고 합니다.

 

구현 코드

package Tree;

public class TreeTraversal {
    TreeNode root;

    public TreeTraversal() {
        root = null;
    }
	
    
    //전위 순회
    public void preorderTraversal(TreeNode treeNode) {
        if (treeNode == null) return;

        System.out.print(treeNode.data + " ");
        preorderTraversal(treeNode.left);
        preorderTraversal(treeNode.right);
    }
	
    //중위 순회
    public void inOrderTraversal(TreeNode treeNode) {
        if (treeNode == null) return;

        inOrderTraversal(treeNode.left);
        System.out.print(treeNode.data + " ");
        inOrderTraversal(treeNode.right);
    }
	
    //후위 순회
    public void postOrderTraversal(TreeNode treeNode) {
        if(treeNode == null) return;

        postOrderTraversal(treeNode.left);
        postOrderTraversal(treeNode.right);
        System.out.print(treeNode.data + " ");

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        TreeTraversal traversal = new TreeTraversal();
        traversal.preorderTraversal(root);
        System.out.println();
        traversal.inOrderTraversal(root);
        System.out.println();
        traversal.postOrderTraversal(root);
    }
}

 

트리의 순회에는 다양한 방식이 있는데 그중에서 가장 유명한 순회 방식이 3가지 있습니다.

나뉘는 기준은 방문 순서입니다.

 

방문순서

• 전위 순회 : 현재 노드, 왼쪽, 오른쪽
• 중위 순회 : 왼쪽 노드, 현재 노드, 오른쪽 노드
• 후위 순회 : 왼쪽 노드, 오른쪽 노드, 현재 노드

 

트리의 재귀적 속성을 이용하여 재귀함수를 통해 트리의 순회를 구현했습니다.

 

 

정리

트리에 대한 중요한 키워드를 뽑아봅시다.

표현 대상

• 계층
• 포함
• 상위, 하위 관계

속성

• 재귀

구성 요소

• 노드와 간선

표현 대상은 트리의 목적이고, 트리가 가지는 가장 중요한 특성, 트리의 구성 요소를 키워드로 뽑아낼 수 있겠습니다.

이 키워드들을 중점으로 트리를 이해하시면 좋을 것 같습니다.