[Java자료구조] 7 - 트리

트리(Tree)는 대표적인 비선형 자료구조 이다.

노드들을 간선으로 연결한 계층형 자료구조

제일위의 하나의 노드를 루트노드로 하여 나머지 노드들이 간선으로 연결 됨

하나의 노드는 그자체로 트리이며 루트가 된다

1. 이진트리 개념

1. 노드의 차수 -한노드가 가진 서브트리의 수 ex) A의 차수 : 3, B의 차수 : 2, C의 차수 : 0, D의 차수 : 3
2. 리프노드(단말,터미널) - 차수가 0인 노드 ex) 리프노드 : E, J, K, L, H, I
3. 자식 노드 -노드에 연결된 서브트리의 루트노드들 ex) A의 자식노드 : B, C, D
4. 부모 노드 -노드에 연결된 한단계 상위 레벨 노드 ex) I의 부모노드 : D
5. 형제 노드 - 부모가 같은 노드 ex) G, H, I 는 형제노드
6. 트리의 차수 - 노드가 가지고 있는 자식 노드의 개수 ex) B, C, D → 3개
7. 노드의 레벨 -노드가 속한 트리의 깊이 ex) A노드의 레벨 : 0
8. 트리의 깊이(높이) -트리의 최대 레벨 ex) 트리의 깊이 : 3

 

 

트리(Tree)

트리는 계층적인 구조를 나타내는 자료구조로 부모-자식 관계의 노드들로 이루어진다. 계층적인 조직 표현이나 컴퓨터 디스크의 디렉토리 구조 등에 트리 구조가 사용된다.

 

루트는 서브트리를 만들어 낼 수 있다.

 

 

노드(node)란 트리의 구성요소를 의미한다. 자식 노드, 부모 노드, 형제 노드, 조상 노드, 자손 노드는 인간관계와 동일한 개념이다.

 

루트(root) 노드는 부모가 없는 노드이다. ex) A 이다.

 

단말노드(terminal node)는 자식이 없는 노드이다. ex) F, G, H, J, K, L 이다.

 

레벨(level)이란 트리의 각 계층의 번호이며, 높이(height)는 트리의 최대 레벨이다.

위 그림에서 트리의 높이는 4 이다. ( A(1) → B(2) → E(3) → J(4) = 4

차수(degree)는 노드가 가지고 있는 자식 노드의 개수이다. A 노드의 차수는 3이고, B 노드의 차수는 2이다.

 

 

A는 루트 노드이다.

B는 D와 E의 부모노드이다.

C는 B의 형제 노드이고, F와 G의 부모노드이다.

D와 E는 B의 자식노드이다.

B의 차수는 2이다.

위의 트리의 높이는 4이다.

 

 

이진 트리(Binary Tree)

이진트리는 모든 노드가 최대 두 개의 서브트리를 가지는 트리 구조를 말한다.

 

 

 

이진트리 성질

이진트리는 노드의 개수가 n개 이면, 간선의 개수는 n-1 이다.

높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 $2^h - 1$ 개의 노드를 가진다.

 

 

루트를 제외하고 모두 부모가 있다.

 

n개의 노드를 가지는 이진트리의 높이는 최대 n 이고, 최소 [ $log_2(n+1)$ ] 이다.

 

 

높이가 log n개

만약 노드가 1조 개 있을 때 최소 높이가 40개 될수 있음 = log n개

 

 

이진트리의 분류

 

 

 

이진트리의 표현

이진트리를 메모리에 표현하는 방법에는 배열을 이용하는 표현법과 연결리스트(포인터)를 이용하는 표현법이 있다.

 

배열 표현법

배열 표현법은 모든 이진트리를 포화 이진트리로 가정하고, 각 노드에 번호를 부여하여 해당 번호를 배열의 인덱스로 사용하여 노드(데이터)를 배열에 저장하는 방법이다.

 

인덱스 0은 비워둠

 

완전 이진트리 위에서부터 왼쪽에서 오른쪽으로 밑으로 내려옴 - 공간 낭비가 없음

경사 이진트리를 배열 표현법으로 쓰면 무조건 공간 낭비가 발생함

 

표현법으로 이진트리를 표현하면 각 노드의 위치를 쉽게 계산할 수 있다.

노드 i의 부모 노드 인덱스 = i / 2 (분자 분모)

노드 i의 왼쪽 자식 노드 인덱스 = 2*i

노드 i의 오른쪽 자식 노드 인덱스 = 2 * i + 1

 

 

 

링크 표현법

LinkedList를 사용함

경사진 이진트리를 링크 표현법으로 표현하면 다음과 같다.

최소 3개의 칸이 있음.

왼쪽의 칸은 왼쪽 자식을 가리키는 주소, 오른쪽 칸은 오른쪽 자식을 가리키는 주소

 

 

이진트리 사용 시 완전 이진트리를 다루는 응용에서는 배열 표현법을 사용하고, 그렇지 않는 경우에는 링크 표현법을 사용하는 것이 바람직하다.

 

 

표현법 사용

완전 이진트리 : 배열 표현법

경사진 이진트리 : 링크 표현법(배열 표현법 사용 시 공간낭비)

 

 

2. 이진트리 순회

순회(traversal)란 트리의 노드들을 체계적으로 방문하는 것을 말한다.

전위순희(Preorder Traversal)

이진트리를 전위순회하는 방법은 루트노드를 먼저 방문하고, 왼쪽 서브트리 방문, 다음으로 오른쪽 서브트리를 방문한다. 각 서브트리에서도 동일한 방법으로 전위순회 한다.

 

 

루트 방문 왼쪽 먼저 방문을 끝까지 끝이 나면 그 자리에서 오른쪽으로 방문 없으면 위의 오른쪽으로 점점 올라감

왼쪽이 만약 있으면 무조건 방문 후 오른쪽으로 내려옴

 

 

입력 : 루트 노드를 x로 가지는 이진트리

결과 : 이진트리의 각 노드를 전위순회 결과 출력

preorder(x)
if x≠NULL
	then print DATA(x);
	  	 preorder(LEFT(x));
	 		 preorder (RIGHT(x));

 

 

중위순회(Inorder Traversal)

이진트리를 중위순회하는 방법은 왼쪽 서브트리를 먼저 방문하고, 루트노드를 방문하고, 다음으로 오른쪽 서브트리를 방문한다. 각 서브트리에서도 동일한 방법으로 중위순회 한다.

재귀호출로 표현한 중위순회 알고리즘이다.

입력 : 루트 노드를 x로 가지는 이진트리

결과 : 이진트리의 각 노드를 중위순회 결과 출력

inorder(x)
if x≠NULL
	then inorder(LEFT(x));
			print DATA(x);
			inorder(RIGHT(x));

 

후위순회(Postorder Traversal)

후위순회는 이진트리를 방문하는 방법 중 하나로, 왼쪽 서브트리를 먼저 방문하고, 오른쪽 서브트리를 방문한 후에 마지막으로 루트노드를 방문한다.

재귀호출로 표현한 후위순회 알고리즘이다.

입력 : 루트 노드를 x로 가지는 이진트리 결과 : 이진트리의 각 노드를 후위순회 결과 출력

postorder(x)
if x≠NULL
then postorder (LEFT(x)); 
		postorder(RIGHT(x)); 
		print DATA(x);

 

 

수식트리(Expression Tree)

수식	a + b	a + b * c	a < b or c > d
전위순회	+ a b	x + a b c	or < a b > c d
중위순회	a + b	a + b x c	a < b or c > d
후위순회	a b +	a b + c x	a b < c d > or

수식 계산에는 후위식이 용이하므로, 수식트리를 후위순회하면서 수식을 계산한다.

다음은 수식트리에 저장된 수식을 계산하는 알고리즘이다.

 

입력 : 루트 노드를 exp로 가지는 수식트리

결과 : 수식트리의 수식 계산 결과 반환

evaluate(exp)

if exp = NULL
	then return 0;
	else x <- evaluate(exp.left);
	y <- evaluate(exp.right);
	op <- exp.data;
	return (x op y);

후위에서 조금만 바꿔주면 계산 가능

 

 

레벨순회(level order)

 

레벨순회는 트리의 각 레벨을 순서대로 검사하는 순회 방법이다. 다른 일반적인 트리 순회 방법들인 전위순회, 중위순회, 후위순회는 재귀호출을 통해 구현되어 내부적으로 스택을 사용한다. 그에 비해 레벨순회는 큐를 활용하여 구현된다.

 

레벨 순회는 1 레벨부터 끝 레벨까지 각 레벨 별 왼쪽에서 오른쪽으로 순회하는 방법

 

다음은 큐를 활용하여 이진트리를 레벨순회하는 알고리즘이다.

입력 : 수식트리(root 노드)

결과 : 수식트리의 수식 계산 결과 반환

level_order(root)
initialize queue;
enqueue(queue, root);
	while is_empty(queue)TRUE do
	x← dequeuer(queue);
	if (x=NULL) then
		print DATA(x); 
		enqueuer(queue, LEFT(x)); 
		enqueuer(queue, RIGHT(x));

 

 

3. 이진트리 구현

링크 표현법을 사용한 이진트리를 구현하였다. Node라는 클래스를 정의하여 이진트리를 구성하는 각 노드 객체생성 하였다.

이 예제에서 사용하는 이진트리는 아래와 같다.

 

아래는 이진트리를 만들고, 각 노드를 순회하는 예제이다.

package s240430;

import java.util.LinkedList;
import java.util.Queue;

class Node { // 노드 클래스 정의
    private String value; // 영문자를 저장하기위해 String 타입으로 선언
    private Node left; // 왼쪽 자식 노드를 참조하는 포인터(참조형 변수)
    private Node right; // 오른쪽 자식 노드를 참조하는 포인터(참조형 변수)

    public Node(Node l, String v, Node r) { // 인자 3개인 생성자
        left = l;
        value = v;
        right = r;
    }

    public void setLeft(Node l) {
        left = l;
    }

    public void setRight(Node r) {
        right = r;
    }

    public String getValue() { // 접근자
        return value;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }
}

class BinaryTree { // 이진트리 클래스
    private Node root; // 루트 노드 참조 변수

    public BinaryTree(Node r) { // 생성자
        root = r;
    }

    public void preOrder(Node root) { // 전위순회 메소드
        if (root == null)
            return;
        System.out.print(root.getValue() + " ");
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }

    public void inOrder(Node root) { // 중위순회 메소드
        if (root == null)
            return;
        inOrder(root.getLeft());
        System.out.print(root.getValue() + " ");
        inOrder(root.getRight());
    }

    public void postOrder(Node root) { // 후위순회 메소드
        if (root == null)
            return;
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue() + " ");
    }

    // level order(레벨 오더) 구현
    public void levelOrder(Node root) {
        Queue<String> table = new LinkedList<>();

    }
}

public class BinaryTreeTest {
    public static void main(String[] args) {
        // 노드 객체 생성(Bottom-Up 방식으로 단말노드부터 생성)
        Node h = new Node(null, "H", null);
        Node i = new Node(null, "I", null);
        Node j = new Node(null, "J", null);
        Node k = new Node(null, "K", null);
        Node d = new Node(h, "D", i);
        Node e = new Node(null, "E", null);
        Node f = new Node(null, "F", null);
        Node g = new Node(j, "G", k);
        Node b = new Node(d, "B", e);
        Node c = new Node(f, "C", g);
        Node a = new Node(b, "A", c); // 마지막에 루트노드 생성
        BinaryTree tree = new BinaryTree(a); // 이진트리 객체 생성
        System.out.print("PreOrder : ");
        tree.preOrder(a);
        System.out.println();
        System.out.print("InOrder : ");
        tree.inOrder(a);
        System.out.println();
        System.out.print("PostOrder : ");
        tree.postOrder(a);
    }
}

 

 

추가실습

레벨 오더 함수 구현 

    // level order(레벨 오더) 구현
    public void levelOrder(Node3 root) {
        Queue<Node3> q = new LinkedList<>();
        q.add(root); // 루트 노드 큐에 삽입
        while(!q.isEmpty()) { // q가 비어있으면 끝남
            Node3 tempNode = q.poll(); // q의 노드를 꺼냄
            System.out.print(tempNode.getValue() + " "); // 해당 노드의 값 출력

            // 왼쪽 자식 추가
            if (tempNode.getLeft() != null) { // 왼쪽 자식이 있으면 큐에 추가
                q.add(tempNode.getLeft());
            }
            // 오른쪽 자식 추가
            if (tempNode.getRight() != null) { // 오른쪽 자식이 있으면 큐에 추가
                q.add(tempNode.getRight());
            }
            // 만약 더이상 자식이 없으면
        }
    }