자료구조
[JAVA] Tree 이진트리 구현
jay Joon
2020. 12. 15. 01:26
이진트리란
자식 노드가 최대 2개인 노드로 구성된 트리이다.
-> 이 말을 해석 해보자면 부모 노드로 부터 자식노드가 0 ~2개 사이로 존재 할 수 있다.
더 자세히 그림으로 살펴보자.
| left(10) root(5) right(null) | left(10) root(5) right(20) | left(null) root(5) right(20) | left(null) root(5) right(null) |
|---|---|---|---|
 |
 |
 |
 |
이런 구조를 가질 수 있다.
그럼 위 그림을 통해 Node 구조를 만들어 보자.
1. 한개의 노드를 봤을때 Value 값이 필요함
2. 노드에서 는 left 노드 , right 노드 포함할 수도 있고 없을 수도 있다.
private class Node {
private Node left;
private Node right;
private int value;
public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value){
this.value = value
}
}Node class를 정의 했다. 이제 이 Node를 이용해 이진 트리를 만들어보자.
이진트리를 만들기전에 3가지의 전제조건 부터 알아보자.
1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값 보다 작아야 한다.
2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
3. 같은 키의 값을 갖는 노드는 존재하지 않는다.
위의 전제조건을 이용하여 Insert 코드를 만들어보자
private boolean find(int value){
Node currentNode =root;
while (currentNode!=null){
if(currentNode.getValue()==value){
return true;
}else if(currentNode.getValue() >value) {
currentNode = currentNode.getLeft();
}else {
currentNode = currentNode.getRight();
}
}
return false;
} public boolean insert(int value){
Node newNode = new Node(value); //값을 받아서 새로운 newNode 생성
if(find(value)){ //find method를 호출하여 value 가 있는지 체크 3번 전제조건 확인
return false;
}
if(root == null){ // root 가 null 이면 newNode 를 root로 변경후 return
root =newNode;
return true;
}
Node currentNode = root;
Node parent;
while (true){
parent = currentNode;
if(value<currentNode.getValue()){ //value 보다 cur.value 가 더 크면
currentNode = currentNode.getLeft(); //왼쪽 노드로이동 1번 전제조건 확인
if(currentNode==null){
parent.setLeft(newNode);
return true;
}
}else {
currentNode = currentNode.getRight(); // cur.value 보다 value 가 더 크면
if(currentNode==null){
parent.setRight(newNode); //오른쪽 노드로이동 2 번전제조건 확인
return true;
}
}
}
}
다음은 이진트리의 탐색 방법 4가지를 알아보자
1. 전위 탐색(PreOrderTraversal) : root -> left ->right
전위 탐색이 곧 - >깊이우선탐색(DFS) 가 됨 (stack 활용)
private List<Integer> inOrderTraverse(Node focusNode, List<Integer> integers) {
if (focusNode != null) {
integers.add(focusNode.getValue());
inOrderTraverse(focusNode.getLeft(),integers);
inOrderTraverse(focusNode.getRight(),integers);
}
return integers;
}
2. 중위 탐색(InOrderTraversal) : left -> root > right
중위탐색 -> 오름차순 정렬
private List<Integer> inOrderTraverse(Node focusNode, List<Integer> integers) {
if (focusNode != null) {
inOrderTraverse(focusNode.getLeft(),integers);
integers.add(focusNode.getValue());
inOrderTraverse(focusNode.getRight(),integers);
}
return integers;
}
3. 후위 탐색(PostOrderTraversal) : left ->right ->root
private List<Integer> postOrderTraverse(Node focusNode,List<Integer> integers) {
if (focusNode != null) {
postOrderTraverse(focusNode.getLeft(),integers);
postOrderTraverse(focusNode.getRight(),integers);
integers.add(focusNode.getValue());
}
return integers;
}
4. 너비우선탐색(BFS)
-> Queue 를 이용
public List<Integer> BFS(Node focusNode){
if(focusNode == null){
return null;
}
List<Integer> result = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(focusNode);
while (!queue.isEmpty()){
int size = queue.size();
for (int i = 0; i < size; i++) {
Node poll = queue.poll();
if(poll.getLeft() !=null){
queue.add(poll.getLeft());
}
if(poll.getRight() !=null){
queue.add(poll.getRight());
}
result.add(poll.getValue());
}
}
return result;
}
Test 코드
class BinaryTreeTest {
BinaryTree binaryTree;
@BeforeEach
void beforeEach(){
binaryTree = new BinaryTree();
binaryTree.insert(5);
binaryTree.insert(1);
binaryTree.insert(2);
binaryTree.insert(6);
binaryTree.insert(7);
binaryTree.insert(10);
binaryTree.insert(9);
}
@Test
@DisplayName("객체 추가")
void insert(){
//when
boolean insert_20 = binaryTree.insert(20);
boolean insert_dup_10 = binaryTree.insert(10);
//then
assertThat(insert_20).isTrue();
assertThat(insert_dup_10).isFalse();
}
@Test
@DisplayName("전위 순회 ,깊이우선탐색(DFS)")
void preOrderTravers(){
//when
List<Integer> preOrderTraverse = binaryTree.Traverse(binaryTree.root, BinaryTree.PRE_ORDER_TRAVERSE);
//then
assertThat(preOrderTraverse).isEqualTo(List.of(5, 1, 2, 6, 7, 10, 9));
}
@Test
@DisplayName("너비우선탐색(BFS)")
void BFS(){
//when
List<Integer> preOrderTraverse = binaryTree.BFS(binaryTree.root);
//then
assertThat(preOrderTraverse).isEqualTo(List.of(5, 1, 6, 2, 7, 10, 9));
}
@Test
@DisplayName("중위 순회")
void inOrderTravers(){
//when
List<Integer> preOrderTraverse = binaryTree.Traverse(binaryTree.root, BinaryTree.IN_ORDER_TRAVERSE);
//then
assertThat(preOrderTraverse).isEqualTo(List.of(1, 2, 5, 6, 7, 9, 10));
}
@Test
@DisplayName("후위 순회")
void postOrderTravers(){
//when
List<Integer> preOrderTraverse = binaryTree.Traverse(binaryTree.root, BinaryTree.POST_ORDER_TRAVERSE);
//then
assertThat(preOrderTraverse).isEqualTo(List.of(2, 1, 9, 10, 7, 6, 5));
}
}전체소스코드 : 바로가기