생각을 개발하자, 박진형

[자료구조 알고리즘] 트리, 이진트리, 이진트리 순회 본문

Data structure & Algorithm/data structure_algorithm

[자료구조 알고리즘] 트리, 이진트리, 이진트리 순회

imjinbro imjinbro 2017.10.13 15:31

[트리란]

1) 비선형자로구조 : 데이터의 관계를 나타내는 것에 비중이

2) 뿌리에서 가지를 뻗어나가는 형태의 자료구조 : 계층을 나타냄



[트리 관련 개념]

1) 노드 : 트리 구성요소

2) 엣지 : 노드와 노드를 연결하는

3) 루트노드 : 트리구조에서의 최상위노드(서브트리도 포함, 어떤 트리가 문제해결의 중심이냐에 따라)

4) 단말노드 : 아래로 다른 노드와의 연결없는 노드

5) 내부노드 : 단말노드를 제외한 노드, 관계가 있는 노드

6) 레벨 : 같은 높이에 있는 노드들

7) 높이 : 루트노드(0) 기준으로 가지가 몇단계에 걸쳐 뻗어져있는가?, 최대 레벨은 높이와 같음

8) 서브트리 : 루트노드에서 뻗어져나온 노트들이 뻗었을 그때 트리 형태

9) 형제관계 : 같은 레벨의 노드

10) 부모관계

11) 포화이진트리 : 모든 레벨에 꽉찬 이진트리

12) 완전이진트리 : 차곡차곡 쌓여진 이진트리(포화이진트리X), 아래에서 , 왼쪽에서 오른쪽



[이진트리란]

1) 루트노드가 2개의 노드를 가짐 : 상하위 관계

2) 서브노드의 서브노드는 이진트리 구조 : 2 노드

- 0~1 가질 떄에도 이진트리 : 3 이상을 가지는 순간 이진트리X, 공노드라고



[이진트리 만들기 - 정확히는 이진트리를 구성할 있는 도구]

1) 배열 : 접근이 용이하다는 장점

2) 연결리스트

- 트리 관계 표현을 쉽게할 있다는 장점

- 루트 노드 1개로 전체 트리를 가져올 있다는 장점

- 주로 연결리스트를 사용하지만 배열을 사용할 때가 있음



[연결리스트 기반 이진트리]

1) BTree(BTreeNode) 객체타입 1개를 가지고 이진트리 표현

- 스택, 큐와 같이 노드 / 자료구조 기능 따로 2개의 타입을 만들었다면 이진트리는 BTreeNode 두가지 역할 모두함

- 노드와 노드 간의 관계를 가짐 : 상하위


2) 선형자료구조와 달리 비선형자료구조는 데이터 관계 표현이 주목적

- 선형자료구조가 저장, 변경, 삭제 기능이 우선시 되었다면

- 비선형자료구조는 데이터 간의 관계 표현을 우선시


3) 루트노드 주소값만 가지고 있으면 나머지 노드는 연결되어있으므로 딸려다님

- 노드를 단순로드로 보지않고 이진트리의 루트노드로



[이진트리 순회]

1) 순회 종류 : 전위, 후위, 중위가 있는데 루트노드를 언제 순회하느냐에 따라 차이, 횡은 왼쪽 -> 오른쪽

2) 루트노드 관점에서 순회코드 짜기

3) 재귀 : 패턴 + 언제 (탈출조건 == 루트노드)


[이진트리 관계 맺기 + 순회 코드]
- 깃헙 레포 :  https://github.com/imjinbro/datastructure/tree/master/src/main/java/com/jinbro/source/tree/binarytree

import java.util.NoSuchElementException;

public class BTreeTest {
public static void main(String[] args) {

try{
BTreeNode bt1 = new BTreeNode(1);
BTreeNode bt2 = new BTreeNode(2);
BTreeNode bt3 = new BTreeNode(3);
BTreeNode bt4 = new BTreeNode(4);

/* 노드 간 이진트리 관계 맺어주기 : 루트노드 -> 서브노드 -> 서브노드 */
bt1.setLeftSubTree(bt2);
bt1.setRightSubTree(bt3);
bt2.setLeftSubTree(bt4);

/* 중위순회 : 재귀 */
BTreeNode.Traverse(bt1);

} catch(NoSuchElementException e){
System.out.println(e.getMessage());
}

}
}
import java.util.NoSuchElementException;

public class BTreeNode { //노드이자 이진트리의 루트노드 즉, 이진트리

//왼쪽 노드는 곧 왼쪽 서브트리의 루트노드
private BTreeNode leftSubTree;
private BTreeNode rightSubTree;

private Object data;

public BTreeNode(Object data) {
this.data = data;

leftSubTree = null;
rightSubTree = null;
}

public BTreeNode getLeftSubTree() {
if(leftSubTree == null){
//호출하는 쪽에서 처리를 해야함
throw new NoSuchElementException();
}

return leftSubTree;
}

/*
[서브트리 세팅메서드 쓰임새 : 나눠주는게 좋지않을까] : 추가 / 변경 / 삭제
1) 아무것도 설정되어있지않을 때 관계를 설정함
- 추가되는 노드가 곧 서브트리의 루트노드

2) 기존에 설정되어있는 서브트리에서 루트 노드만 변경할 떄?
- 노드일 경우와 트리일 경우 모두 생각해야함
(1) 서브트리라고 칭해진 루트노드의 왼쪽 오른쪽 null 체크하고 null일 경우는 그대로 붙이고
(2) null이 아니라면 2가지 경우 : 서브트리 자체를 변경하느냐 루트노드 데이터만


3) 서브트리 삭제 : set 메서드는 서브트리를 null 만들 때도 사용
- 순회하면서 null 처리 : 메모리 낭비를 하지않기위해 참조를 끊어줌
- 순회의 방법은? 루트노드를 타고 들어가?
*/
public void setLeftSubTree(BTreeNode leftSubTree) {
this.leftSubTree = leftSubTree;
}

public BTreeNode getRightSubTree() {
if(rightSubTree == null){
throw new NoSuchElementException();
}

return rightSubTree;
}

public void setRightSubTree(BTreeNode rightSubTree) {
this.rightSubTree = rightSubTree;
}



public Object getData() {
return data;
}

public void setData(Object data) {
//데이터 변경
this.data = data;
}



/*
[순회] : 순회하는 것을 보여주려고 출력만 설정함
1) 노드로만 보지않고 서브 트리의 루트노드로 봐야함 : 노드 + 트리 관점 접근
2) 같은 패턴, 깊이는 몰라(반복하되 탈출조건은 있는) : 재귀 호출
3) 재귀 : 같은 메서드지만 다른 스택프레임 생성 - 종료되어야 호출한 쪽 코드 흐름 실행
*/
static void Traverse(BTreeNode root){
/* [이진트리 관점] */
if(root == null){
return;
}

Traverse(root.leftSubTree);
System.out.println(root.getData());
Traverse(root.rightSubTree);

/*
[단순 노드 관점]
if(root.leftSubTree != null){
Traverse(root.leftSubTree);
}
System.out.println(root.getData());
if(root.rightSubTree != null){
Traverse(root.rightSubTree);
}
*/
}
}