[자료구조] 트리의 종류, 3가지 순회방법

✨트리(Tree) 의 종류 

 

 

1. Binary Tree ( 이진 트리 ) 

트리 종류	설명
Ternary tree	부모 노드가 자식 노드를 최대 3개씩 가지고 있는 트리
Binary tree	부모 노드가 자식 노드를 최대 2개씩 가지고 있는 트리 (이진 트리) 즉, 자식이 없거나 1개 or 2개

2. Balance ( 밸런스 ) 

종류	설명
Balanced	지나치게 한쪽으로 치우치지 않았다면 Balanced Tree (Left, Right 노드 갯수가 일치해야 할 필요없음)
Unbalanced	한쪽으로 지나치게 치우쳐진 Tree를 Unbalanced Tree 라고 한다. (비 순환적 경로로 연결되어있으므로 트리구조이다 O )

3. Binary Search Tree ( 이진 검색 트리 ) 

트리 종류	설명
Binary tree	부모를 기준으로 노드의 숫자가 기준 없이 자유롭다. (노드들간의 대소관계는 고려하지 않음)
Binary Search tree	Left child와 그 이하 노드들의 데이터가 Parent 노드 의 데이터 보다 작아야 하고, Right child 와 그 이하 노드들의 데이터가 Parent 노드의 데이터 보다 커야한다. (즉, 현재 노드를 기준으로 L 작은수, R 큰수)
Complete Binary tree	마지막 레벨을 제외한 모든 서브트리의 레벨이 같아야 하고, 마지막 레벨은 왼쪽부터 채워져 있어야한다. (레벨이 다 맞고 왼쪽부터 채워져 있는 트리)
Full Binary tree	자식 노드가 아예 없거나, 최대 둘뿐인 tree (자식을 하나만 가진 노드가 없어야 함)

( 노드의 개수 = 2^(트리높이, 레벨 최댓값)-1 )

트리 종류	설명
Perfect Binary tree	완벽한 피라미드 형태로, 모든 노드의 자식이 2개씩 있다. (해당 트리 노드의 갯수는 2^3-1 = 7 ) Root 제외 모든 노드는 자식을 2개씩 가지고 있으므로 -1 을 해준다.

---

✨이진 트리의 3가지 순회방법 

Binary tree traversals (이진 트리의 순회종류)	설명
Inorder(중위 순회)	Root를 중간에 순회 (L Root R)  1. Left leaf 이동 및 출력 3. Parent node 출력 4. Right child 출력 5. 한 레벨씩 위로 올라가며 반복 6. Root 출력후 Right child 기준으로 반복
Preorder(전위 순회)	Root를 제일 먼저 순회 (Root L R) 1. Root 출력 2. Left child 출력 3. Left leaf로 갈때까지 반복 4. Root 출력후 Right child 기준으로 반복 (Right leaf로 갈때까지)
Postorder(후위 순회)	Root를 제일 마지막에 순회 (L R Root) 1. Left leaf 이동 및 출력 2. Right child 출력 3. Parent node 출력 4. 위로 올라가며 반복 5. Root 출력후 Right child 기준으로 반복