Copyright (c) 2015-, All Rights Reserved by Kwanghoon Choi
(아래 자바 프로그래밍 강의 교재의 내용을 자유롭게 이용하되 다른 웹 사이트 등을 통한 배포를 금합니다.)

4. 이진 트리 (Binary Tree)

이진 트리란 원소를 포함하지 않는 널 트리이거나 원소를 포함하면 그 원소는 두 개의 작은 이진 트리를 갖는 형태의 자료구조이다.

널 트리는 ()로 표현하고, 원소를 갖는 이진 트리는 (T1 : n : T2)와 같이 표현한다. 예를 들어,

- (() : 1 : ())
- ( (() : 2 : ()) : 1 : () )
- ( (() : 2 : ()) : 1 : (() : 3 : ()) )
- ( ((() : 4 : ()) : 2 : ()) : 1 : (() : 3 : ()) )

4-1. 이진 트리 클래스

리스트 클래스를 응용해서 이진 클리 클래스 Tree, NullTree, BinTree를 정의하시오. 리스트의 원소는 정수로 가정한다.

Tree 클래스는 다음의 메소드를 갖는다.

- boolean isNull()
- boolean isBinTree()
- int value()
- Tree left()
- Tree right()
- String toString()

NullTree 클래스는 Tree 클래스를 상속받아 정의하되 아래 메소드를 재정의(overriding)한다.

- boolean isNull()
- String toString()

BinTree 클래스 역시 Tree 클래스를 상속받아 정의한다. 이 클래스는 정수, 왼쪽 이진 트리, 오른쪽 이진 트리를 저장하는 필드를 포함한다. 그리고 Tree 클래스의 아래 메소드를 재정의(overriding)한다.

- int value
- Tree leftTree
- Tree rightTree

- boolean isBinTree()
- int value()
- Tree left()
- Tree right()
- String toString()

BinTree의 경우 정수와 두 개의 이진 트리 객체를 받는 생성자를 갖는다.
- BinTree(Tree left, int value, Tree right)

4-2. 이진 트리에 대한 연산

리스트에 흔히 적용할 수 있는 연산들로 리스트에 포함된 원소의 수를 구하는 count, 이진 트리의 높이를 구하는 height, 모든 원소의 합을 구하는 sum이 있다.

- int count(Tree tree)
- int height(Tree tree)
- int sum(Tree tree)

이 외에도 이진 트리의 각 원소를 순서대로 방문하는 preorder, inorder, postorder가 있다. 방문 순서는 앞에서 정의한 List 객체로 만들어 리턴한다.

- List preorder(Tree tree)
- List inorder(Tree tree)
- List postorder(Tree tree)

이진 트리 (T1 : n : T2)가 있다고 가정하자. preorder는 n을 방문하고, T1을 모두 방문하고, T1를 을 방문한다. inorder는 T1을 모두 방문하고, n을 방문하고 T2를 방문한다. postorder는 T1과 T2를 차례대로 방문한 다음 n을 방문한다.

- (() : 1 : ())

preorder
===> [1]

inorder
===> [1]

postorder
===> [1]

- ( (() : 2 : ()) : 1 : () )

preorder
===> [1,2]

inorder
===> [2,1]

postorder
===> [2,1]

- ( (() : 2 : ()) : 1 : (() : 3 : ()) )

preorder
===> [1,2,3]

inorder
===> [2,1,3]

postorder
===> [2,3,1]

- Tree 클래스의 preorder 메소드

abstract class Tree {
        ...
        public List preorder() {
           if (this.isNull()) {
               return new NullList();
           }
           else {
               return new Pair(this.value(), new NullList())  // 현재 노드를 방문
                        .concat(this.left().preorder())       // 왼쪽 트리를 preorder 순서로 방문
                        .concat(this.right().preorder());     // 오른쪽 트리를 preorder 순서로 방문
           }
        }
        ...
}