이진트리를 어떻게 정의할지 알아보기로 합시다.
일단 이진트리라는 데이터 구조 자체도 약간씩 다른 버전으로 정의할 수 있습니다.
이 중에서 우리는 트리의 노드 부분에만 원소가 나타나고 아무 원소도 없는 빈 이진트리도 포함하는 정의를 따릅시다.
그러니까 이진트리를 구성하는 다음의 두 가지란 말이죠.
이렇게 정의를 하나로 고정시켜 놓더라도 Java로 이것을 작성하는 방법이 또 여러가지가 있을 수 있다.
사실 Java에서만 그런 게 아니라 공통점이 많은 C++이나 C# 등에서도 이건 마찬가지.
// null 을 빈 이진트리라고 생각하자
// 노드를 나타내는 class 딱 하나만 정의하면 끝!!
class Tree {
int value;
Tree left;
Tree right;
// 생성자
Tree(int v, Tree l, Tree r) { value=v; left=l; right=r; }
@Override
public String toString() {
return value+"@{ "+left+"; "+right+" }";
}
boolean has(int v) { // 매번 has를 호출하기 전에 null인지 아닌지 검사를 해줘야 함
return v == value
|| (left !=null) && left.has(v)
|| (right!=null) && right.has(v);
}
}
/*
2
/ \
1 3
\
4
*/
Tree t0 = null; // 빈 트리는 이렇게 정의하겠죠
Tree t1 = new Tree(2,
new Tree(1, null, null),
new Tree(3,
null,
new Tree(4, null, null) ) );
t1
2@{ 1@{ null; null }; 3@{ null; 4@{ null; null } } }
// t1의 정의를 직접 코드에서 하지 않고 입력받거나 프로그램에서 계산했다면 항상 null인지 아닌지 검사하면서
(t1!=null) && t1.has(3)
true
null == null
true
// t0의 정의를 직접 코드에서 하지 않고 입력받거나 프로그램에서 계산했다면 항상 null인지 아닌지 검사하면서
(t0!=null) && t0.has(3)
false
abstract class ATree {
abstract boolean has(int v);
}
class Null extends ATree {
@Override
public String toString() { return "Null"; }
@Override
boolean has(int v) { return false; }
}
class Node extends ATree {
int value;
ATree left;
ATree right;
// 생성자
Node(int v, ATree l, ATree r) { value=v; left=l; right=r; }
@Override
public String toString() {
return value+"@{ "+left+"; "+right+" }";
}
@Override // ATree를 구성하기 위해서 null을 활용하지 않으므로 널포인터 검사 불필요
boolean has(int v) { return v == value || left.has(v) || right.has(v); }
}
ATree nil = new Null(); // 나도 빈 트리인데
ATree nil2 = new Null(); // 너도 빈 트리구나
ATree t2 = new Node(2,
new Node(1, nil, nil),
new Node(3,
nil,
new Node(4, nil, nil) ) );
t2
2@{ 1@{ Null; Null }; 3@{ Null; 4@{ Null; Null } } }
t2.has(6)
false
nil == nil
true
nil2 == nil
false
nil.has(3)
false