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

 

아래의 유툽영상을 바탕으로 작성되었습니다. 좋은영상 감사합니다.

Tree의 종류 :  https://youtu.be/LnxEBW29DOw

0. 트리(tree)란?

출처 : 위키백과 - 트리 구조

즉 Array, LinkedList, Stack, Queue같이 선형구조가 아닌, 부모자식의 관계를 가지는 계층형 그래프.

 

1. 이진 트리(Binary tree)

Binary tree : 부모 노드가 자식 노드를 최대 2개씩만 갖고있는 트리.

Ternary tree : 자식 노드를 2개 이상 갖고 있는 트리

 

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

Binary tree : 노드들간의 대소관계는 고려하지 않는다.

Binary search tree : left child와 그 이하 노드들의 데이터가 현재 노드(부모 노드)의 데이터 보다 작아야 하고, right child와 그 이하 노드들의 데이터가 현재 노드(부모 노드)의 데이터 보다 커야한다.

 

3. 밸런스(Balance)

Balanced : left, right 노드의 갯수가 정확하게 일치해야 할 필요는 없음. unbalanced처럼 지나치게 한쪽으로 치우치지 않았다면 balanced tree. (예: red-black tree, AVL tree)

Unbalanced : 한쪽으로 지나치게 치우친 tree.

 

4. 완전 이진 트리(Complete binary tree)

Complete binary tree : 마지막 레벨을 제외한 모든 서브트리의 레벨이 같아야 하고, 마지막 레벨은 왼쪽부터 채워져 있어야 함.

 

5. 정이진트리(Full binary tree)

Full binary tree : 자식 노드가 아예 없거나, 최대 둘뿐인 tree. 자식을 하나만 가진 노드가 없어야 한다.

 

6. 포화 이진 트리(Perfect binary tree)

Perfect binary tree : 자식이 아예 없거나 2개씩만 갖는 Full binary tree와 달리, Perfect binary tree는 완벽한 피라미드 형태로, 빈공간 없이 모든 노드가 2개의 자식을 갖고있는 tree.

*Q. Perfect binary search의 레벨의 갯수가 n이라면, 해당 트리의 노드의 갯수는?

A. $2^n-1$. root제외 모든 노드는 자식을 2개씩 갖고 있으므로.

Binary Tree의 3가지 순회방법 구현하기 : https://youtu.be/QN1rZYX6QaA

7. 이진 트리의 순회(Binary tree traversal)

 

 

이진 트리의 순회들(Binary tree traversals) : Root를 제일 먼저 순회 하냐, 중간에 하냐, 제일 나중에 하냐에 따라 달라짐.
중위 순회(Inorder) : Root를 중간에 순회	Left, Root, Right (LRootR)
전위 순회(Preorder) : Root를 제일 먼저 순회	Root, Left, Right (RootLR)
후위 순회(Postorder) : Root를 제일 나중에 순회	Left, Right, Root (LRRoot)

 

 

7-1. 중위순회(Inorder : LRootR)

 

Inorder : Root를 중간에 순회 한다. Left - Root - Right 순서로 노드를 순회.

1. left leaf로 이동

2. 현재 노드 출력

3. parent node 출력

4. (parent node에 right child가 있다면) right child 출력

6. 한 레벨씩 위로 올라가며 반복

7. 맨 위 올라갔다면 root출력

8. root에 right child가 있다면 right child를 기준으로 다시 1~7번 반복

 

*Q. 위 트리의 Inorder 순회 결과는?

A. 4-2-5-1-3

*Q. 아래 트리의 Inorder 순회 결과는?

A. 4-2-5-1-8-6-3-7

 

7-2. 전위순회(Preorder : RootLR)

1. root 출력

2. left child 출력

3. left leaf로 갈때까지 반복

4. 한 레벨 위로 올라감

5. (현재 노드가 right child를 갖고있다면) right child출력

6. right child가 자식을 갖고있다면 다시 2~4번 반복

7. root까지 올라가며 반복

8. root의 right child가 있다면 다시 2~6번 반복

 

*Q. 위 트리의 preorder 순회 결과는?

A. 1-2-4-5-3

 

*Q. 아래 트리의 Preorder 순회 결과는?

A. 1-2-4-5-6-3-7-8

 

7-3. 후위순회(Postorder : LRRoot)

1. left leaf로 이동 및 출력

2. (parent node에 right child가 있다면) right child 출력

3. parent 출력

4. 한 레벨씩 위로 올라가며 반복

5. root에 right child가 있다면 right child를 기준으로 다시 1~4번 반복

6. root출력

 

*Q. 위 트리의 preorder 순회 결과는?

A. 4-5-2-3-1

*Q. 아래 트리의 Postorder 순회 결과는?

A. 4-6-5-2-7-8-3-1

 

 

8. 기본 이진트리 구현 및 연습(c++)

(1) 이진트리(Binary tree)의 3가지 순회방법을 코드로 구현해보기

 

(2) 아래의 트리를 보고, 헤더의 빈 함수를 구현해보기