[자료구조] 트리

트리란?

트리는 1개 이상의 노드를 갖는 노드의 집합으로 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할 때 사용하는 비선형 자료구조입니다.

트리는 디렉터리 구조등 계층적인 구조를 갖는 데이터일때 사용됩니다.

트리는 다음과 같은 조건을 만족합니다.

1. 트리에 최상위에 루트노트라는 노드가 존재합니다.
2. 한 노드는 하나의 노드만 가르키고 있습니다. (1 : n 관계)
3. 트리는 사이클을 그리지 않으며, 계층적인 구조를 가집니다.

다음과 같은 구조는 트리가 아닙니다.

위의 경우는 C 노드를 A와 F가 가르키고 있기 때문에 트리가 아닙니다.

위의 경우에는 노드들이 사이클을 그리고 있기 때문에 트리가 아닙니다.

 

트리 용어

트리는 다음과 같은 용어를 사용합니다.

• 루트 노드(root node) : 부모가 없는 노드를 의미합니다. 트리는 하나의 루트노드만을 가집니다. 위에서는 A노드가 루트노드입니다.
• 내부 노드(internal node) : 노드의 차수가 1 이상인 모든 노드를 의미합니다. 위에서는 A, B, C, H 노드가 내부 노드입니다.
• 리프 노드(leaf node) : 노드의 차수가 0인 노드를 의미합니다. (맨 끝에 있는 노드를 의미) 위에서는 D, E, F, G 노드가 리프 노드입니다. 
• 부모 노드 (parent node) : 부속 트리를 가진 노드를 의미합니다. 위에서는 D, E 노드의 부모 노드는 B입니다.
• 자식 노드 (child node) : 부모에 속하는 노드를 의미합니다. 위에서는 C의 자식 노드는 F, G입니다.
• 형제 노드(sibling node) : 같은 부모를 가지는 노드를 의미합니다. 위에서는 D의 형제 노드는 E입니다.
• 조상 노드(ancestor node) : 특정 노드의 모든 부모 노드들을 의미합니다. 위에서 F의 조상 노드는 C, A 입니다.
• 자손 노드(descendant node) : 특정 노드의 모든 자식노드들을 의미합니다. 위에서 C의 자손 노드는 F, G입니다.
• 링크(link) : 각 노드간에 연결하는 선을 의미합니다. (edge, branch 라고도 부릅니다.)
• 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 루트노드 부터 레벨 1로 시작하며, 아래로 내려가면서 1씩 증가합니다. 위에서 D의 레벨은 3입니다.
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수를 의미합니다. C 노드의 크기는 3입니다. (C, F, G)
• 노드의 차수(degree) : 노드의 부속 트리 개수를 의미합니다.(쉽게 말해서 연결되어 있는 노드의 수라고 생각하면 됩니다.) 위에서 C 노드는 2의 차수를 가지고 있습니다.
• 트리의 차수(degree of tree) : 트리에서 가장 큰 차수를 가진 노드를 의미합니다. 위에서는 A 노드가 가장 많은 3의 차수를 가지고 있으므로 트리의 차수는 3입니다.
• 트리의 높이(height of tree) : 루트 노드에서 가장 깊숙히 있는 노드(리프 노드)의 레벨을 의미합니다. 위의 트리에서 트리의 높이는 3입니다.
• 서브트리(subtree) : 전체 트리의 부분 집합
• 포레스트(forest) : 트리들의 집합

이진 트리(Binary Tree)

이진 트리는 자식 노드의 수가 2개 이하인 트리를 의미합니다.

위와 같은 노드들이 이진 트리이며 왼쪽과 오른쪽으로 자식 노드를 가질 수 있으며 자식 노드가 없더라도 이진 트리라고 할 수 있습니다.

 

이진 트리는 다음과 같은 특징을 가지고 있습니다.

• 이진 트리의 최대 레벨이 n인 경우 트리의 최대 노드의 개수는 2^n - 1개입니다.
• 이진 트리의 최대 레벨이 n인 경우 트리의 최소 노드의 개수는 n개 입니다.

포화 이진 트리(Perfect Binary Tree)

모든 레벨에 노드가 가득 차 있는 이진 트리를 의미합니다. 포화 이진 트리는 이진 트리가 가질 수 있는 최대 노드의 개수인 2^n-1 개를 가집니다.

완전 이진 트리(Complete Binary Tree)

마지막 레벨를 제외하고 모든 노드가 채워져 있는 이진 트리를 의미합니다. 마지막 레벨의 노드들은 왼쪽부터 차례대로 채워지게 되며 마지막 레벨이 가득 채워져 있더라도 완전 이진트리입니다. (포화 이진 트리이기도 하며 완전 이진 트리가 됩니다.)

편향 이진 트리(Skewed Binary Tree)

n의 레벨을 가진 이진 트리중에서 노드의 개수가 n개이며 왼쪽이나 오른쪽으로만 노드가 생성되어 있는 트리를 의미합니다.

이진 트리의 순회

트리 순회는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말합니다.

노드를 방문하는 순서에 따라 다음과 같이 분류됩니다.

• 전위 순회 : 노드방문 -> 왼쪽 서브 트리 -> 오른쪽 서브트리
• 중위 순회 : 왼쪽 서브 트리 -> 노드 방문 -> 오른쪽 서브트리
• 후위 순회 : 왼쪽 서브 트리 -> 오른쪽 서브트리 -> 노드 방문
• 레벨 순회 : 레벨 순서대로 왼쪽 노드부터 차례대로 순회

위과 같은 트리 구조가 있을 경우 각 순회방식에 따른 결과는 다음과 같습니다.

• 전위 순회 : F, B, A, D, C, E, G, I, H
• 중위 순회 : A, B, C, D, E, F, G, H, I
• 후위 순회 : A, C, E, D, B, H, I, G, F
• 레벨 순회 : F, B, G, A, D, I, C, E, H

링크드리스트를 통한 이진 트리 구현

https://github.com/zxcv9203/dataStructure/tree/master/chap05

GitHub - zxcv9203/dataStructure