(1) 트리(Tree)
- 노드(Node)와 링크(Link)로 구성된 자료구조(Cycle X)
- 계층적 구조를 나타낼 때 사용
- ex) 폴더 구조(디렉토리, 서브 디렉토리), 조직도, 가계도 ...
(2) 트리 구조
- 노드(Node): 트리 구조의 자료값을 담고 있는 단위
- 루트 노드(Root): 부모 없는 노드, 가장 위의 노드
- 잎새 노드(Leaf): 자식이 없는 노드(=단말)
- 내부 노드(Internal): 잎새 노드를 제외한 모든 노드
- 에지(Edge): 노드 간의 연결선(=Link, Branch)
- 부모(Parent): 연결된 두 노드 중, 상위 노드
- 자식(Child): 연결된 두 노드 중, 하위 노드
- 형제(Sibling): 같은 부모를 가지는 노드
- 깊이(Depth): 루트에서 어떤 노드까지의 간선의 수
- 레벨(Level): 트리의 특정 깊이를 가지는 노드 집합
- 높이(Height): 트리에서 가장 큰 레벨 값
- 크기(Size): 자신을 포함한 자식 노드 개수
- 차수(Degree): 각 노드가 가진 가지의 수
- 트리의 차수: 트리의 최대 차수
(3) 트리 특징
- 하나의 노드에서 다른 노드로 이동하는 경로 유일
- 노드가 N개인 트리의 Edge 수: N-1개
- Acyclic (Cycle X)
- 모든 노드가 서로 연결
- 하나의 Edge를 끊으면 2개 Sub-Tree로 분리
(4) 이진 트리
- 각 노드는 최대 2개의 자식을 가질 수 있음
- 자식 노드는 좌우를 구분
- 왼쪽 자식: 부모(기준)의 왼쪽
- 오른쪽 자식: 부모(기준)의 오른쪽
(5) 이진 트리 종류
- 포화 이진 트리(Perfect Binary Tree): 모든 레벨에서 노드들이 꽉 차있는 트리
- 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외하고 노드들이 꽉 채워져 있는 트리
- 정 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
- 편향 트리(Skeqed Binary Tree): 한 쪽으로 기울어진 트리
- 균형 이진 트리(Balanced Binary Tree): 모든 노드의 좌우 서브 트리 높이가 1이상 차이나지 않는 트리(탐색속도 빠름)
(6) 이진 트리 특징
- 포화 이진 트리의 높이가 h일 때, 노드의 수: 2^(h+1) - 1
- 포화(or 완전) 이진 트리의 노드가 N개일 때, 높이: log N
- 이진 트리의 노드가 N개일 때, 최대 가능 높이: N-1
(7) 이진 트리 순회(Traversal)
- 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
- 순회 종류 4가지: (1) 전위 순회, (2) 중위 순회, (3) 후위 순회, (4) 레벨 순회
(1) DFS - 전위 순회(Preorder Traversal)
- 방문 순서: 현재 노드 → 왼쪽 노드 → 오른쪽 노드
(2) DFS - 중위 순회(Inorder Traversal)
- 방문 순서: 왼쪽 노드 → 현재 노드 → 오른쪽 노드
(3) DFS - 후위 순회(Postorder Traversal)
- 방문 순서: 왼쪽 노드 → 오른쪽 노드 → 현재 노드
(4) BFS - 레벨 순회(Levelorder Traversal)
- 방문 순서: 위쪽 레벨부터 왼쪽 노드 → 오른쪽 노드
(8) 이진 트리 구현
- 배열로 구현하는 방법: 레벨 순회 순서로 배열에 구현
- 왼쪽 노드의 인덱스 번호: (부모 인덱스)*2 + 1
- 오른쪽 노드의 인덱스 번호: (부모 인덱스)*2 + 2
- Root 노드의 인덱스 번호==0 이므로
- 루트 노드의 왼쪽 자식 노드의 인덱스 번호: 0*2 + 1 = 1 인덱스 자리
- 루트 노드의 오른쪽 자식 노드의 인덱스 번호: 0*2 + 2 = 2 인덱스 자리
- 그림과 다른 이유: 배열은 0부터 시작하기 때문에 구현할 때는 (왼:+0, 오:+1)이 아니라 (왼:+1, 오:+2)이 되야 함
- 연결리스트: 값과 간선을 관리하기 위한 노드로 연결 리스트 구현
(9) JAVA로 구현해보기
(1) Array를 이용한 이진 트리 구현, 순회 4가지
//Array를 이용한 이진 트리 구현, 순회
class BinaryTree{
char[] arr; //저장할 배열 생성
BinaryTree(char[] data){
this.arr = data.clone(); //입력받은 배열을 복사
}
//DFS-전위 순위: 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
public void preOrder(int idx){
//먼저 현재 노드 실행
System.out.print(this.arr[idx]+ " ");
int left = 2*idx+1; //현재 노드의 왼쪽 노드
int right = 2*idx+2; //현재 노드의 오른쪽 노드
//왼쪽 노드부터 실행
if(left < this.arr.length){ //왼쪽 자식 노드 확인
this.preOrder(left); //재귀함수
}
//왼쪽 노드가 없으면 오른쪽 노드 실행
if(right < this.arr.length){ //오른쪽 자식 노드 확인
this.preOrder(right);
}
}
//DFS-중위 순회: 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
public void inOrder(int idx){
int left = 2*idx+1; //현재 노드의 왼쪽 노드
int right = 2*idx+2; //현재 노드의 오른쪽 노드
//왼쪽 노드부터 실행
if(left < this.arr.length){ //왼쪽 자식 노드 확인
this.inOrder(left);
}
//왼쪽 노드가 없으면 현재 노드 실행
System.out.print(this.arr[idx] + " ");
//현재 노드 다음에 오른쪽 노드 실행
if(right < this.arr.length){ //오른쪽 자식 노드 확인
this.inOrder(right);
}
}
//DFS-후위 순회: 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
public void postOrder(int idx){
int left = 2*idx+1; //현재 노드의 왼쪽 노드
int right = 2*idx+2; //현재 노드의 오른쪽 노드
// 왼쪽 노드부터 실행
if(left < this.arr.length){
this.postOrder(left);
}
//오른쪽 노드 실행
if(right < this.arr.length){
this.postOrder(right);
}
//현재 노드 실행
System.out.print(this.arr[idx] + " ");
}
//BFS-레벨 순회: (위쪽 레벨부터) 왼쪽 노드 -> 오른쪽 노드
public void levelOrder(int idx){
// 배열 입력 그대로 출력하면 됨(이미 위쪽 레벨부터 왼,오 순서로 정렬되어 있음)
for (int i = 0; i < this.arr.length; i++) {
System.out.print(this.arr[i]+" ");
}
System.out.println();
}
}- 재귀 함수를 이용해 찾고자 하는 노드를 입력 받는 것을 반복하면서 출력을 진행함
(2) 연결리스트를 이용한 이진 트리 구성, 순회
//연결 리스트를 이용한 이진 트리 구성, 순회
class Node{
char data; //저장할 데이터 변수 생성
Node left; //현재 노드의 왼쪽 노드 정보 변수 생성
Node right; //현재 노드의 오른쪽 노드 정보 변수 생성
//TIP: alt+insert: 생성자 바로만들기
public Node(char data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}
class BinaryTree2{
Node head; //트리의 root 노드 정보 저장하는 변수 생성
BinaryTree2(){}
BinaryTree2(char[] arr){ //배열로 트리를 입력받음
//노드 형태의 배열로 만듬
Node[] nodes = new Node[arr.length];
for (int i = 0; i < arr.length; i++) { //입력 받은 배열을 노드 객체들로 만듦
nodes[i] = new Node(arr[i], null, null);
}
//자식 연결
for (int i = 0; i < arr.length; i++) {
int left = 2*i+1; //현재의 왼쪽 노드
int right = 2*i+2; //현재의 오른족 노드
if(left < arr.length){
nodes[i].left = nodes[left]; //현재 기준 노드의 왼쪽 노드 정보 입력에 노드 정보 추가
}
if(right < arr.length){
nodes[i].right = nodes[right]; //현재 기준 노드의 오른쪽 노드 정보 입력에 노드 정보 추가
}
}
//root 연결
this.head = nodes[0]; //배열의 첫 번째 인덱는 root
}
//DFS-전위 순위: 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
public void preOrder(Node node){
if(node == null){ //왼쪽 노드나 오른쪽 노드가 없는 경우 반환을 통해 다음 라인으로 진행함
return;
}
//현재 노드부터 시작
System.out.print(node.data+" ");
//현재 노드의 왼쪽으로 이동: 왼쪽 노드가 없는 경우 return을 통해 다음 라인(오른쪽)으로 이동함
this.preOrder(node.left);
//현재 노드의 오른쪽으로 이동
this.preOrder(node.right);
}
//DFS-중위 순회: 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
public void inOrder(Node node){
if(node == null){ //왼쪽 노드나 오흔쪽 노드가 없는 경우 반환을 통해 다음 라인을 진행함
return;
}
//왼쪽 노드부터 시작
this.inOrder(node.left);
//더이상 왼쪽 노드가 없는 경우 현재 노드를 출력
System.out.print(node.data + " ");
//오른쪽 노드로 이동
this.inOrder(node.right);
}
//DFS-후위 순회: 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
public void postOrder(Node node){
if(node == null){
return;
}
//왼쪽 부터 시작
this.postOrder(node.left);
//오른쪽으로 이동
this.postOrder(node.right);
//현재 노드 출력
System.out.print(node.data+" ");
}
//BFS-레벨 순회: (위쪽 레벨부터) 왼쪽 노드 -> 오른쪽 노드
public void levelOrder(Node node){
Queue<Node> queue = new LinkedList<>(); //큐는 선입선출
queue.add(node);
while(!queue.isEmpty()){ //큐가 비어있지 않을때 동안 반복
Node cur = queue.poll(); //큐에서 현재 노드를 뽑음
//현재 노드 출력
System.out.print(cur.data+" ");
if(cur.left != null){ //현재 노드의 왼쪽이 있다면
queue.offer(cur.left); //왼쪽 출력, 큐에 추가
}
if(cur.right != null){ //현재 노드의 오른쪽이 있다면
queue.offer(cur.right); //오른쪽 출력, 큐에 추가
}
}
}
}(3) 트리 구조 복습 / 구현
//트리 구조 복습/구현
class Node2{
char data; //노드에 저장할 데이터 변수 생성
Node2 left; //노드의 왼쪽 노드 정보를 저장할 변수 생성
Node2 right; //노드의 오른쪽 노드 정보를 저장할 변수 생성
Node2 parent; //노드의 부모 노드 정보를 저장할 변수 생성
public Node2(char data, Node2 left, Node2 right, Node2 parent) {
this.data = data;
this.left = left;
this.right = right;
this.parent = parent;
}
}
class BinaryTree3{
Node2 head; //트리의 Root 노드 정보를 저장할 변수 생성
BinaryTree3(char[] arr){
Node2[] nodes = new Node2[arr.length]; //입력의 길이만큼 노드 배열 생성
for (int i = 0; i < arr.length; i++) { //입력받은 배열 정보를 노드 객체들로 생성
nodes[i] = new Node2(arr[i], null, null, null);
}
//초기 설정 - 노드들을 연결해주기
for (int i = 0; i < arr.length; i++) {
int left = 2 * i + 1; //왼쪽 노드 인덱스
int right = 2 * i + 2; //오른쪽 노드 인덱스
if (left < arr.length) {
nodes[i].left = nodes[left];
nodes[left].parent = nodes[i];
}
if (right < arr.length) {
nodes[i].right = nodes[right];
nodes[right].parent = nodes[i];
}
}
this.head = nodes[0]; //root 노드 저장
}
//찾고자하는 data가 트리에 존재하는지, 존재하면 노드를 반환
public Node2 searchNode(char data){
Queue<Node2> queue = new LinkedList<>();
queue.add(this.head); //헤드부터 찾음
while(!queue.isEmpty()){ //비어있지 않을 경우에만 반복
Node2 cur = queue.poll(); //현재 큐의 노드를 하나 뽑음
if(cur.data == data){ //뽑은 데이터가 찾는 데이터라면
return cur;
}
if(cur.left != null){ //뽑은 데이터의 왼쪽이 비어져 있지 않으면
queue.offer(cur.left); //왼쪽 추가
}
if (cur.right != null) { //뽑은 데이터의 오른쪽이 비어져있지 않으면
queue.offer(cur.right); //오른쪽 추가
}
}
return null; //데이터가 존재하지 않으면 null반환
}
//크기 구하기: 트리의 사이즈를 data를 기준으로 자신을 포함한 자식 노드의 개수를 알아보는 함수
public Integer checkSize(char data){
Node2 node = this.searchNode(data);
if(node == null){
return null;
}
Queue<Node2> queue = new LinkedList<>();
queue.add(node);
int size = 0;
while(!queue.isEmpty()){
Node2 cur = queue.poll();
if(cur.left != null){
queue.offer(cur.left);
size++; //존재할 경우 사이즈 증가
}
if(cur.right != null){
queue.offer(cur.right);
size++; //존재할 경우 사이즈 증가
}
}
return size+1; //자기 자신 포함
}
}'자료구조 with JAVA' 카테고리의 다른 글
| [자료구조 with JAVA] 균형 이진 트리 (Balanced Binary Search Tree) - AVL 트리 (0) | 2025.02.26 |
|---|---|
| [JAVA] 자료구조 - 이진 탐색 트리 (Binary Search Tree) (0) | 2025.01.07 |
| [JAVA] 자료구조 - 해시 테이블 (Hash Table) (0) | 2024.12.30 |
| [JAVA] 자료구조 - 데크 (Deque) (0) | 2024.12.30 |
| [JAVA] 자료구조 - 큐(Queue) (1) | 2024.12.30 |