[자료구조] 트리, Tree

트리는 노드(자료 저장)와 간선(노드 연결)을 갖는 계층구조이다. 

즉, 부모-자식(Parent-Child 관계)

1:n 관계 (여기서 1은 Root Node, n은 Root를 제외한 나머지 자식 노드 즉, n은 레벨이 1이상인 노드이다.)

트리는 응용프로그램, 알고리즘에서 자주 쓰인다.

 

이진트리

 

트리의 종류

자식의 개수에 따라

binary tree : 최대 2개 자식

ternary tree : 최대 3개

 

부모를 기준으로 

binary tree : 부모를 기준으로 노드의 숫자가 기준 없이 자유롭다.

binary search tree : 부모를 기준으로 왼쪽은 부모보다 작아야하고 오른쪽은 큰 더 커야한다.

 

complete binary tree : 레벨이 다 맞고 왼쪽부터 채워져 있는 트리

full binary tree : 노드들이 자식을 가지려면 2개 있어야하고 그게 아니면 없어야한다.

perfect binary tree : 모든 노드의 자식이 2개있음. (노드의 개수 = 2^(트리 높이, 레벨 최댓값) - 1)

 

이진트리

모든 노드의 자식이 최대 2개인 트리. 즉, 자식이 없거나 1개 있거나 2개 있는 것.

 

이진트리의 표현

이진트리는 배열로 표현할 수 있는데, 1차원배열로 표현하는 방법, 2차원 배열로 표현하는 방법이 있다.

 

1. 1차원 배열로 표현한 이진트리

parent배열은 인덱스i의 부모 노드이다.

int[] parent = new int[node의 개수+1]; //node의 개수에 +1을 해준 이유는 배열의 인덱스 0 때문.

 

 2. 2차원 배열로 표현한 이진트리 

 

 

이진트리의 순회

 

 

 

 

 

 

https://www.youtube.com/watch?v=LnxEBW29DOw

 

https://www.youtube.com/watch?v=QN1rZYX6QaA