트리(Tree)

1. 트리

■ 리스트, 스택, 큐, 덱은 자료들이 일렬로 나열된 형태인 선형 자료구조에 적합했다.

■ 자료들이 선형이 아닌 계층적인(hierarchical) 구조일 때, 자료들이 계층적인 관계를 가질 때, 이 구조를 표현하기에 적합한 자료구조는 비선형 자료구조인 트리이다.

1.1 트리 구조

트리

■ 트리는 노드(node or vertex)와 노드와 노드를 연결하는 선인 간선(= 엣지, edge)로 표현된다.

■ 계층 구조에서 가장 높은 곳, 레벨(level) 1에 위치한 노드를 루트(root) 노드라고 한다. 따라서 트리에서 모든 노드는 자신의 서브트리의 루트 노드로 볼 수 있다.

■ 하나의 노드도 트리가 될 수 있다. 예를 들어 노드 E는 E를 포함하고 있는 서브 트리의 루트 노드로 볼 수 있다.

■ 루트 노드를 부모(parent) 노드라 한다면, 이 부모 노드에서 파생된 왼쪽 서브트리의 노드와 오른쪽 서브트리의 노드를 루트 노드의 자식(child) 노드라고 한다.

- 즉 엣지로 직접 연결된 노드 중, 상위 노드와 하위 노드를 부모 노드, 자식 노드라고 한다.

■ 그리고 동일한 부모 노드를 가진 노드, 즉 같은 레벨에 있는 노드들을 형제(sibling) 노드라고 한다.

■ 예를 들어 첫 번째 그림에서 루트 노드는 A이며 B, C, D 노드는 부모 노드 A의 자식 노드이자 자신의 서브 트리의 루트 노드가 된다. 그리고 B, C, D는 동일한 부모 노드 A를 갖기 때문에 B, C, D는 형제 노드이다.

■ 또한, 조상(ancestor) 노드와 자손(descendent) 노드 관계가 있는데, 어떤 노드에서 루트 노드까지 경로상에 있는 모든 노드들을 조상 노드, 어떤 노드에서 연결된 모든 하위 노드들을 자손 노드라고 한다.

■ 예를 들어, k의 조상 노드는 루트 노드까지 경로상에 있는 I, D, A 노드가 k의 조상 노드가 된다. 반대로, D의 자손 노드는 D와 연결된, D의 모든 하위 노드인 H, I, J, K 노드가 D의 자손 노드가 된다.

■ 자식 노드가 아예 없는 노드를 단말(terminal) 또는 리프(leaf) 노드라고 한다.

■ 예를 들어, 노드 k는 자식 노드가 없으므로 리프 노드이다.

■ 차수(degree)에는 노드의 차수와 트리의 차수가 있다.

- 노드의 차수는 어떤 노드가 가지고 있는 자식 노드의 수로, 모든 노드에는 노드의 차수가 있다.

- 트리의 차수는 트리에 있는 노드들의 차수 중에서 가장 큰 차수이다.

■ 예를 들어, 자식 노드가 없는 노드 E, F, K 등은 노드의 차수가 0이고, 노드 A와 D는 노드의 차수가 3으로 전체 노드들 중에서 노드의 차수가 가장 높다. 따라서 트리의 차수는 3이 된다.

■ 레벨(level)은 트리의 각 층에 대한 번호로 루트의 레벨은 1이 되고, 루트에서 한 층씩 내려갈수록 레벨은 1씩 증가한다.

(* 루트 레벨을 0에서 시작해도 된다.)

■ 트리의 높이(height)는 트리의 최대 레벨이다.

■ 이 예에서는 트리의 레벨이 4까지 있으므로 트리의 높이는 4이다.

 

1.2 일반 트리

■ 일반적으로 트리를 표현하는 방법은 연결된 구조에서의 링크 필드와 데이터 필드를 갖는 노드 형태로 표현하는 것이다.

■ 노드는 항목 값을 저장하는 데이터 필드와 자식 노드를 가리키는 링크를 갖기 때문에, 자식 노드가 많아질수록 링크의 수도 이에 비례하여 증가하게 된다. 즉, 노드의 차수만큼 링크가 필요하여 구조가 복잡해진다.

■ 노드 하나가 두 개의 링크를 갖게 해서 일반 트리를 더 단순화하여 나타낼 수 있다.

■ 링크 하나는 첫 번째 자식 노드를 가리키고, 다른 하나는 다음 형제 노드를 가리키게 만들면 된다.

다만 이렇게 표현할 경우 루트 노드 A에서 노드 K를 찾기 위해 필요 없는 많은 노드를 방문해야 한다는 문제가 있다.

■ 이보다 다 딘슨힌 형태로, 왼쪽 자식 노드와 오른쪽 자식 노드를 정확히 구별하고 왼쪽, 오른쪽 자식 노드에 바로 접근할 수 있는 트리 형태가 있는데, 이를 이진 트리라고 한다.

 

2. 이진트리(Binary Tree)

■ 이진트리는 모든 노드가 최대 2개의 서브트리를 갖는 트리이다. 즉 \( 0 \leq \) 모든 노드의 차수 \( \leq 2 \)인 트리로, 자식 노드를 최대 2개까지 가질 수 있다.

■ 이때 자식 노드들 사이에도 순서가 존재하기 때문에 왼쪽 자식 노드와 오른쪽 자식 노드를 반드시 구분해야 한다.

■ 이진 트리는 다음과 같이 정의할 수 있다.

■ 즉, 이진트리는 공집합(아무것도 없는 트리)도, 노드와 그 노드의 자식이 하나 있는 트리도 이진트리가 된다.

■ 중요한 것은 전체 트리가 이진트리가 되려면 루트 노드의 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진트리여야 하는데, 이 말은 즉 왼쪽 서브트리의 루트 노드의 왼쪽 서브트리와 오른쪽 서브트리도 이진트리여야 하며, 오른쪽 서브트리의 루트 노드의 왼쪽 서브트리와 오른쪽 서브트리도 이진트리 구조가 되야 한다는 의미이다. 따라서 이진트리는 재귀적 구조를 갖는다고 볼 수 있다.

■ 이진트리에는 포화이진트리(full binary tree)와 완전이진트리(complete binary tree)가 있다.

■ 포화이진트리는 트리의 각 레벨에 노드가 꽉 차있는 이진트리이다. 따라서 트리의 높이에 따라 노드의 개수가 일정하게 정해진다. 각 노드가 모두 자식 노드 2개를 갖기 때문이다.

■ 트리의 높이가 \( h \)라면, level 1에 \( 2^0 \)개, level 2에 \( 2^1 \)개, level 3에 \( 2^3 \)개, ... , level \( h\)에 \( 2^h - 1 \)개를 갖는다. 따라서 높이가 \( h \)이면 포화이진트리의 전체 노드 개수는 \( 2^h - 1 \)개이다.

■ 포화이진트리의 각 노드에 순서대로 번호를 붙일 수 있으며, 이 번호는 항상 일정하다. 번호는 레벨 단위로 왼쪽에서 오른쪽 순서대로 붙인다.

■ 즉, 루트 노드의 번호는 항상 1이고, 루트 노드의 왼쪽 자식 노드의 번호는 항상 2, 오른쪽 자식 노드의 번호는 항상 3이다.

■ 완전이진트리는 트리의 높이가 \( h \)일 때, 레벨 1부터 레벨 \( h - 1 \)까지는 노드가 모두 채워지고, 마지막 레벨 \( h \)에서는 노드가 왼쪽부터 오른쪽 순서대로 채워진 이진트리이다.

■ 따라서 레벨 1부터 레벨 \( h - 1 \) 중에 자식 노드 2개를 가지지 않고 노드가 하나라도 없으면 완전이진트리가 아니며,

■ 마지막 레벨에서 노드가 모두 채워져 있지 않아도 되지만 중간에 빈 곳이 있으면 안 된다.

■ 예를 들어 다음 그림의 왼쪽 트리는 마지막 레벨에서 노드가 왼쪽부터 오른쪽으로 빈 곳 없이 채워져 있으므로 완전이진트리가 맞다. 그러나 두 번째 트리는 마지막 레벨에서 노드가 왼쪽부터 오른쪽으로 채워져 있지 않고 빈 곳이 있으므로 완전이진트리가 아니다.

■ 포화이진트리는 모든 노드가 자식 노드를 2개씩 갖고 있으므로, 항상 완전히 채워져 있는 구조이므로 포화이진트리는 완전이진트리이다.

■ 그러나 역은 항상 성립하지 않는다. 완전이진트리가 레벨 1부터 레벨 \( h - 1 \)까지 포화이진트리의 형태를 갖는다고 해도 높이 \( h \)에서 노드 1개만 갖고 있다면 완전이진트리가 되지만 포화이진트리는 성립하지 않기 때문이다.

2.1 이진트리의 성질

■ 루트 노드를 제외한 모든 노드는 부모 노드를 가지며, 부모 노드와 자식 노드에는 하나의 edge가 존재한다. 따라서 노드의 개수가 \( n \)이면 간선(edge)의 개수는 \( n - 1 \)이다.

■ 이진트리의 높이가 \( h \)라면 이진트리는 \( h \)개 이상 \( 2^h - 1 \)개 이하의 노드를 가진다.

- 왜냐하면 트리의 높이는 트리의 최대 레벨이며, 트리의 한 레벨에는 적어도 하나의 노드가 존재해야 하므로 최소한 \( h \)개의 노드를 가진다.

- 그리고 노드 개수가 가장 많은 경우는 포화이진트리이며, 포화이진트리의 전체 노드 개수는 \( 2^h - 1 \)이므로, 높이가 \( h \)이면 \( h \leq \) 노드 개수 \( \leq 2^h - 1 \)이 성립한다.

- 다음 그림과 같이 레벨마다 노드가 1개씩 있는 트리가 노드의 개수가 \( h \)인 경우이다.

■ 반대로 이진트리가 \( n \)개의 노드를 가진다면, 이진트리의 높이는 \( \log_2 (n + 1) \)이상 \( n \)이하이다.

- 위의 그림처럼 레벨 하나에는 최소한 노드 1개가 있어야 하므로 노드 개수가 \( n \)이라면, 높이가 \( n \)을 초과할 수 없다.

■ 이진트리의 노드 개수는 \( h \leq \) 노드 개수 \( \leq 2^h - 1 \)이므로 노드 개수가 \( n \)개라면 \( h \leq n \leq 2^h - 1 \)이 성립한다. 

- 여기서 부등식을 \( h \leq n \)과 \( n \leq 2^h -1 \)로 나눌 수 있으며, \( h \leq n \)은 ' 노드 개수가 \( n \)이라면, 높이가 \( n \)을 초과할 수 없다.'에 해당된다.

- \( n \leq 2^h -1 \)은 \( n + 1 \leq 2^h \Leftrightarrow \log_2 (n + 1) \leq h \)가 된다.

- 따라서 \( n \)개의 노드를 가지는 이진트리의 높이는 \( \log_2 (n + 1) \leq h \leq n \)이 성립한다.

 

2.2 이진트리의 표현 및 구현

■ 이진트리는 배열 구조와 연결 구조로 표현할 수 있다.

2.2.1 배열 표현법

■ 배열 표현법은 왼쪽부터 오른쪽 순서대로 이진트리의 노드에 번호를 부여하고, 이를 배열의 인덱스로 사용하는 방법이다. 즉, 각 노드에 배열의 인덱스를 부여하는 방법이다.

■ 트리의 높이를 계산해 배열을 할당하고, 각 노드의 번호를 인덱스로 사용해서 노드를 배열에 저장하면 된다.

■ 예를 들어 높이가 \( h \)이면 결과가 \( 2^h - 1 \)인 배열이 필요하다. 즉, 포화이진트리의 전체 노드 개수 \(2^h - 1 \)만큼 배열을 할당한다.

■ 인덱스를 사용하는 특성상 데이터의 접근이 쉽다. 즉, 데이터 접근에 대한 시간 복잡도는 \( O(1) \)이다.

■ 따라서 배열 표현법의 장점은 다음과 같이 어떤 노드의 인덱스를 알면 그 노드의 인덱스로 부모 노드나 자식 노드의 인덱스를 쉽게 구할 수 있다는 점이다.

■ 예를 들어 어떤 노드의 인덱스가 \( i \)라면

- 노드 \( i \)의 부모 노드의 인덱스는 \( (i - 1) // 2 \)

- 노드 \( i \)의 왼쪽 자식 노드의 인덱스는 \( 2i + 1 \)

- 노드 \( i \)의 오른쪽 자식 노드의 인덱스는 \( 2i + 2 \)

- 예를 들어 \( i = 2 \)인 노드의 부모 인덱스는 \( 1 // 2 = 0 \)이므로, 루트 노드가 부모 노드이다.

- \( i = 6 \)이라면 이 노드의 부모 노드의 인덱스는 \( 5 // 2 = 2 \)이므로 인덱스 번호가 2인 노드가 부모 노드이다.

- \( i = 2 \)이라면 왼쪽 자식 노드의 인덱스는 5, 오른쪽 자식 노드의 인덱스는 6이 된다.

■ 만약, 루트 노드의 번호를 1로 시작하게 만든다면, 인덱스 0은 사용하지 않으므로, 높이가 \( h \)이면 길이가 \( 2^h \)인 배열을 할당해야 하며

- 노드 \( i \)의 부모 노드의 인덱스는 \( i // 2 \)

- 노드 \( i \)의 왼쪽 자식 노드의 인덱스는 \( 2i \)

- 노드 \( i \)의 오른쪽 자식 노드의 인덱스는 \( 2i + 1 \)

- 만약 위와 같은 트리라면, 배열의 길이는 8이 되고

- 트리의 루트 노드가 A라면 인덱스 0을 사용하지 않으므로 A의 인덱스는 1이 되고 A의 왼쪽, 오른쪽 자식 노드인 B와 C는 인덱스 2, 3을 부여 받는다.

- 그리고 B의 자식 노드들은 인덱스 4와 5를 부여 받고, C의 자식 노드들은 인덱스 6과 7을 부여 받는다.

■ 위와 같은 예시에서 중간에 노드가 비어 있는 경우 배열의 빈 공간이 생긴다.

■ 즉, 배열 표현법의 단점은 메모리 낭비와 배열의 크기가 트리의 높이에 따라 제한된다는 점이다.

 

2.2.2 링크 표현법

■ 연결된 구조로 이진트리를 표현하기 위해선 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키기 위해 2개의 링크가 필요하다.

■ 예를 들어 다음과 같은 트리들을 연결된 구조로 표현하면

링크의 좌, 우를 구분해서 왼쪽 자식 노드와 오른쪽 자식 노드를 연결하고, 자식 노드가 없는 경우 링크가 아무것도 가리키지 않게, 즉 None으로 설정하면 된다.

■ 이런 노드 구조를 클래스로 나타내면 다음과 같다.

# 링크드 리스트로 구현한 트리 노드의 클래스
class TreeNode:
    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right

node_F = TreeNode('F', None, None)
node_E = TreeNode('E', None, None)
node_D = TreeNode('D', None, None)
node_C = TreeNode('C', node_F, None)
node_B = TreeNode('B', node_D, node_E)
root_node = TreeNode('A', node_B, node_C)

root_node.left, root_node.right
```#결과#```
(<__main__.TreeNode at 0x19432b4da50>, <__main__.TreeNode at 0x19432b4d190>)
````````````

root_node.left.data, root_node.right.data
```#결과#```
('B', 'C')
````````````

root_node.left.left, root_node.right.left
```#결과#```
(<__main__.TreeNode at 0x19432b4e1d0>, <__main__.TreeNode at 0x19431dc6d50>)
````````````

root_node.left.left.data, root_node.right.left.data
```#결과#```
('D', 'F')
````````````

cf) root_node.left.data가 'B'를 출력하는 이유는 위와 같이 클래스 객체인 root_node의 left(= root_node.left)와 right( = root_node.right)가 각각 TreeNode 클래스의 객체 node_B와 node_C를 가리키는 참조이므로 이 node_B, node_C 객체의 data 속성에 접근할 수 있기 때문이다.

- 만약, root_node.left.left를 하면 node_D이고, node_D는 TreeNode(data = 'D', left = None, right = None)을 가리키므로 root_node.left.left.data의 결과는 D가 나온다. 즉, root_node.left.left.data = Node_D.data

- 그럼 root_node.left.left.left.data는?

root_node.left.left.left.data
```#결과#```
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[65], line 1
----> 1 root_node.left.left.left.data

AttributeError: 'NoneType' object has no attribute 'data'
`````````````

- None.data가 되므로 위와 같은 'NoneType' object has no attribute 'data'가 발생한 것이다.

print(root_node.left.left.left)
```#결과#```
None
````````````

 

2.3 이진트리의 연산

■ 이진트리는 재귀 구조를 갖기 때문에 연산을 재귀 알고리즘으로 처리하는 것이 좋다.

■ 트리의 기본적인 연산으로 순회가 있다.

2.3.1 순회(Traversal)

■ 트리에 있는 모든 노드를 한 번씩 방문하는 것을 순회라고 한다.

■ 선형 자료구조는 항목들이 일렬로 나열되어 있어 순회 방법이 단순하지만, 트리 구조의 순회에는 많은 방법이 존재하며, 동일한 트리에 대해서도 다양한 순서로 노드를 방문할 수 있다.

■ 이진 트리의 순회에는 전위(Preorder), 중위(Inorder), 후위(Postorder) 순회 방법이 있으며, 루트, 루트의 왼쪽 서브트리, 루트의 오른쪽 서브트리를 어떤 순서로 방문하느냐에 따라 순회 방법이 구분된다.

■ 루트로 방문하는 작업을 V, 왼쪽, 오른쪽 서브트리를 방문하는 작업을 L, R이라 했을 때

- 전위 순회의 방문 순서는 VLR

- 중위 순회의 방문 순서는 LVR

- 후위 순회의 방문 순서는 LRV

■ 그리고 이진트리는 재귀 구조이므로 각 서브트리도 이진트리이다. 즉, 전체 트리와 동일한 방식으로 서브트리의 노드들을 방문한다. 이는 전체 트리 순회에 사용할 알고리즘을 서브트리에도 적용할 수 있음을 의미한다.
■ 전위 순회의 방문 순서는 루트 노드 \( \rightarrow \) 왼쪽 서브트리 \( \rightarrow \) 오른쪽 서브트리이다.

■ 왼쪽 서브트리, 오른쪽 서브트리도 이진트리이므로 방문 순서가 동일하다.

- 처음에 루트 노드 방문 후 왼쪽 서브트리를 방문할 때 왼쪽 서브트리의 루트 노드를 먼저 방문하고,

- 왼쪽 서브트리의 왼쪽 서브트리가 있다면 해당 서브트리의 루트 노드를 방문한다.

- 더 이상 방문할 왼쪽 서브트리가 없다면 오른쪽 서브트리를 방문한다.

■ 예를 들어 다음과 같은 이진트리가 있다고 할 때

- B'를 왼쪽 서브트리, C'를 오른쪽 서브트리라고 하자.

- 그러면 A \( \rightarrow \) B' \( \rightarrow \) C'이고, B'은 B \( \rightarrow \) D \( \rightarrow \) E, C'은 C \( \rightarrow \) F \( \rightarrow \) G이므로 

- 방문 순서는 A \( \rightarrow \) B \( \rightarrow \) D \( \rightarrow \) E \( \rightarrow \) C \( \rightarrow \) F \( \rightarrow \) G이다.

■ 전위 순회를 재귀 구조로 구현하면 다음과 같다.

def preorder(node):
    if node is not None:
        print(node.data, end = ' ')
        preorder(node.left) # preorder(node.left) 호출이 종료되면
        preorder(node.right) # preorder(node.right)을 호출, 이 호출도 종료되면 재귀 함수 종료

node_G = TreeNode('G', None, None)
node_F = TreeNode('F', None, None)
node_E = TreeNode('E', None, None)
node_D = TreeNode('D', None, None)
node_C = TreeNode('C', node_F, node_G)
node_B = TreeNode('B', node_D, node_E)
root_node = TreeNode('A', node_B, node_C)

preorder(root_node)
```#결과#```
A B D E C F G 
````````````

- preorder 함수에 root_node를 넣으면

1) node is not None은 True이므로 if문의 수행문이 실행되서 root_node.data인 'A'를 출력한다.

2) 그리고 preorder(rood_node.left) = preorder(node_B) 호출

3) node is not None이므로 node_B.data인 'B'를 출력한다.

4) 그리고 preorder(node_B.left) = preorder(node_D) 호출

4) node is not None이므로 node_D.data인 'D'를 출력한다.

5) 그리고 preoder(node_D.left) = preorder(None) 호출

6) node is None이므로 재귀 호출 종료 조건인 if 문이 종료되고 다시 preorder(node_D)로 돌아가서 preorder(node_D.left) 다음 수행문인 preorder(node_D.right)를 호출

7) node is None이므로 if 문이 종료되고 preorder(node_D)가 종료되어 preorder(node_B)로 돌아가서 preorder(node_B.left) 다음 수행문인 preorder(node_B.right) = preorder(node_E)를 호출

8) node is not None이므로 node_E.data인 'E'를 출력한다.

9) 그리고 preorder(node_E.left) = preorder(None)을 호출 -> node is None -> preorder(node_E.right) = preorder(None) 호출 -> node is None -> preorder(node_B)로 돌아가고 preorder(node_B)가 종료되면서 preorder(root_node.left) 다음 수행문인 preorder(root_node.right) = preorder(node_C)를 호출

10) node is not None이므로 node_C.data인 'C'를 출력한다.

이후의 과정은 왼쪽 서브트리와 동일하게 수행되어 preorder(root_node)의 결과가 전위 순회 방문 순서인 'A B D E C F G'가 출력된 것이다.

■ 중위 순회의 방문 순서는 왼쪽 서브트리 \( \rightarrow \) 루트 \( \rightarrow \) 오른쪽 서브트리이다.

■ 예를 들어 다음과 같은 이진트리가 있다고 할 때

- B' \( \rightarrow \) A \( \rightarrow \) C'이고, B'은 D \( \rightarrow \) B \( \rightarrow \) E, C'은 F \( \rightarrow \) C \( \rightarrow \) G이므로

- 방문 순서는 D \( \rightarrow \) B \( \rightarrow \) E \( \rightarrow \) A \( \rightarrow \) F \( \rightarrow \) C \( \rightarrow \) G이다.

■ 중위 순회를 재귀 구조로 구현하면 다음과 같다.

def inorder(node):
    if node is not None:
        inorder(node.left)
        print(node.data, end = ' ')
        inorder(node.right)

inorder(root_node)
```#결과#```
D B E A F C G 
````````````

■ 후위 순회의 방문 순서는 왼쪽 서브트리 \( \rightarrow \) 오른쪽 서브트리  \( \rightarrow \) 루트 노드이다.

■ 예를 들어 다음과 같은 이진트리가 있다고 할 때

- B' \( \rightarrow \) C' \( \rightarrow \) A이고, B'은 D \( \rightarrow \) E \( \rightarrow \) B, C'은 F \( \rightarrow \) G \( \rightarrow \) C이므로

- 방문 순서는 D \( \rightarrow \) E \( \rightarrow \) B \( \rightarrow \) F \( \rightarrow \) G \( \rightarrow \) C \( \rightarrow \) A이다.

■ 후위 순회를 재귀 구조로 구현하면 다음과 같다.

def postorder(node):
    if node is not None:
        postorder(node.left)
        postorder(node.right)
        print(node.data, end = ' ')
        
```#결과#```
postorder(root_node)
````````````

■ 노드를 전부 방문하는 것이 중요하면, 위의 세 가지 순회 방법 중 어떤 방법이든 상관없다.

■ 만약, 어떤 상위의 값이 하위 값들의 합으로 표현되는 문제라면, 자식 노드를 방문한 다음, 부모 노드를 방문하는 후위 순회를 ex) 폴더 용량 계산

■ 반대로, 상위에서 하위로 진행되는 문제는, 부모 노드를 방문한 다음 자식 노드를 방문하는 전위 순회를 사용하면 된다. ex) 구조화된 문서 출력, 노드 레벨 계산

■ 이 세 가지 순회와 반대로, 재귀 알고리즘을 이용하지 않는 순회 방법에는 레벨 순회, 깊이 우선 탐색, 너비 우선 탐색이 있다.

 

2.3.2 트리의 노드 반환과 노드 개수 반환

■ 트리(전체 트리, 왼쪽 서브트리, 오른쪽 서브트리)의 노드를 반환하는 것과 트리의 노드 개수를 반환하는 것 역시 순환을 사용하면 된다.

■ 트리의 노드를 반환하는 방법은 먼저 입력한 노드를 저장하고, 재귀 호출을 이용해 입력한 노드의 왼쪽 자식과 오른쪽 자식을 추가로 저장하면 된다.

■ 트리의 노드 개수를 세는 방법은, 먼저 공백 트리이면 노드가 없으므로 0을 반환해야 한다.

■ 공백 트리가 아니라면 최소한 루트 노드 1개는 반드시 있는 것이고 루트 노드의 왼쪽 서브트리나 오른쪽 서브트리가 존재하면, 재귀 호출을 통해 왼쪽 서브트리의 노드 수와 오른쪽 서브트리의 노드 수를 구하고, 여기에 트리(전체 트리 또는 서브트리)의 루트 노드 1개를 더하면 된다.

def get_node(node):
    result = [node.data]  # 현재 노드의 값을 먼저 저장
    if node.left:  # 왼쪽 자식이 있으면 재귀 호출
        result.extend(get_node(node.left))
    if node.right:  # 오른쪽 자식이 있으면 재귀 호출
        result.extend(get_node(node.right))
    return result

 

def count_node(node):
    if node is None: # node is None이면 공백 트리이므로
        return 0 # 노드 개수는 0
    else:
        return 1 + count_node(node.left) + count_node(node.right)

print(get_node(root_node), count_node(root_node))
print(get_node(node_B), count_node(node_B))
print(get_node(node_F), count_node(node_F))

```#결과#```
['A', 'B', 'D', 'E', 'C', 'F', 'G'] 7
['B', 'D', 'E'] 3
['F'] 1
`````````````

 

2.3.3 리프 노드 반환과 리프 노드 개수 반환

■ 리프 노드를 확인하는 방법은

- 공백 트리인 경우 0,

- 루트 노드는 있지만 루트의 왼쪽, 오른쪽 서브트리가 없는 경우 루트 노드가 리프 노드가 되며,

- 루트의 왼쪽 서브트리와 오른쪽 서브트리가 있는 경우 각각의 서브트리의 리프 노드를 확인하면 된다.

■ 먼저 리프 노드의 개수를 세는 방법은 위와 같이, 입력한 트리가 공백 트리면 0, 자식이 없으면 1, 왼쪽과 오른쪽 자식이 있으면 재귀 호출을 이용해 왼쪽 서브트리의 리프 노드 개수와 오른쪽 서브트리의 리프 노드 개수를 더하면 된다.

■ 리프 노드를 반환하는 방법도 자식이 없으면 현재 노드를 반환하고, 왼쪽과 오른쪽 자식이 있으면 왼쪽 서브트리의 리프 노드와 오른쪽 서브트리의 리프 노드를 반환하면 된다.

def count_leaf_node(node):
    if node is None: # 공백 트리
        return 0
    elif node.left is None and node.right is None: # 루트의 왼쪽과 오른쪽이 없으면
        return 1 # 루트가 리프 노드
    else: # 루트의 왼쪽과 오른쪽이 있다면
        return count_leaf_node(node.left) + count_leaf_node(node.right) # 왼쪽과 오른쪽의 리프 노드 개수를 더해주면 된다.

def get_leaf_node(node):
    if node is None: 
        return []
    elif node.left is None and node.right is None: 
        return [node.data]  
    else: 
        return get_leaf_node(node.left) + get_leaf_node(node.right)

- count_leaf_node의 else 문의 '+'는 숫자를 더하는 역할이며

- get_leaf_node(node.left)와 get_leaf_node(node.right) 사이의 '+'는 elif 문의 return [node.data], 즉 리스트를 합치는 역할을 한다. [node.data] + [node.data] + ... + [node.data]

print(get_leaf_node(root_node), count_leaf_node(root_node))
print(get_leaf_node(node_B), count_leaf_node(node_B))
print(get_leaf_node(node_F), count_leaf_node(node_F))

```#결과#```
['D', 'E', 'F', 'G'] 4
['D', 'E'] 2
['F'] 1
`````````````

 

2.3.4 노드 차수와 트리 차수

■ 노드의 차수를 구하는 가장 간단한 방법은 각 노드를 방문해서 노드의 자식 여부를 확인해 노드의 차수를 계산하는 것이다.

■ 트리의 차수는 트리가 가지고 있는 노드의 차수 중 가장 큰 값이므로, 각 노드의 차수를 구하고 최댓값을 반환하면 된다.

def count_node_degree(node):
    if node is None: 
        return 0
    count = 0
    if node.left is not None:
        count += 1
    if node.right is not None:
        count += 1
    return count
    
def print_node_degree(node):
    if node is None:
        return {}
    node_degree = {}
    node_degree[node.data] = count_node_degree(node)
    node_degree.update(print_node_degree(node.left))
    node_degree.update(print_node_degree(node.right))
    return node_degree

node_degree_1 = print_node_degree(root_node)
for node, degree in node_degree_1.items():
    print(f'node: {node}, node degree: {degree}')

```#결과#```
node: A, node degree: 2
node: B, node degree: 2
node: D, node degree: 0
node: E, node degree: 0
node: C, node degree: 2
node: F, node degree: 0
node: G, node degree: 0
`````````````

def print_tree_degree(node):
    if node is None:
        return {}
    node_degree = {}
    node_degree[node.data] = count_node_degree(node)
    node_degree.update(print_node_degree(node.left))
    node_degree.update(print_node_degree(node.right))
    max_degree = max(node_degree.values())
    return f'tree degree: {max_degree}'

print_tree_degree(root_node)
```#결과#```
'tree degree: 2'
````````````

 

2.3.5 트리의 레벨과 높이

■ (레벨이 1부터 시작한다는 가정 하) 트리의 레벨은 루트 노드부터 시작해서 루트 노드의 왼쪽, 오른쪽 자식으로 계속 이동해서 노드가 None일 때까지 이동해 가장 많이 이동한 횟수를 반환하면 된다.

def count_tree_level(node):
    if node is None:
        return 0
    left = count_tree_level(node.left)
    right = count_tree_level(node.right)
    return max(left, right) + 1

- 트리의 높이는 트리가 가진 최대 레벨이므로, 여기서 전체 트리의 루트 노트를 입력값으로 넣으면 결과는 트리의 높이가 된다.

print(count_tree_level(root_node)); print(count_tree_level(node_B)); print(count_tree_level(node_D))
```#결과#```
3
2
1
`````````````

- 작동 방식은, 예를 들어 루트 노드를 입력값으로 넣었다면

1) count_tree_level(A)

- left = count_tree_level(A.left = B) 호출

2) count_tree_level(B)

- left = count_tree_level(B.left = D) 호출

3) count_tree_level(D)

- left = count_tree_level(D.left = None) 호출

4) count_tree_level(None)

- return 0

- D의 left = 0

5) right = count_tree_level(D.right = None) 호출

- count_tree_level(None) -> return 0

- D의 right = 0, D는 자식이 없으므로  count_tree_level(None)이 두 번 호출되고, 둘 다 0을 반환

- max(D.left, D.right) + 1 = 1. 따라서 D의 높이는 1

6) right = count_tree_level(B.right = E) 호출

- D와 동일하게 높이는 1로 반환된다.

7) B의 왼쪽(D)과 오른쪽(E) 높이를 사용하여 

- count_tree_level(B)에서 return max(left = 1, right = 1) + 1 = 2, 따라서 B의 높이는 2

8) right = count_tree_level(A.right = C) 호출

9) 여기서 동일하게 C의 높이는 2가 된다.

10) 최종적으로 루트 노드 A의 높이는 max(2, 2) + 1 = 3이 된다.

 

3. 레벨 순회

■ 레벨 순회(level order)는 각 노드를 레벨 순서대로, 왼쪽부터 오른쪽 순으로 방문하는 방법이다.

■ 레벨 순회는 먼저 루트 노드를 넣고, 루트 노드를 꺼내 방문한다. 그리고 좌에서 우, 루트의 왼쪽 자식부터 오른쪽 자식 순으로 삽입하고 이들을 꺼내 방문한다. 자식이 없으면 삽입하지 않는다.

■ 이렇게 레벨 순회는 선입선출의 특성으로 노드를 방문하기 때문에 순환을 사용하지 않고 큐를 사용한다.

■ 예를 들어 트리가 다음과 같을 때,

레벨 순회의 노드 방문 순서는 A \( \rightarrow \) B \( \rightarrow \) C \( \rightarrow \) D \( \rightarrow \) E \( \rightarrow \) F \( \rightarrow \) G이다.

- 먼저 루트 노드 A를 삽입하고 A를 꺼낸다.(= A를 방문한다.)

- 그 다음, A의 왼쪽과 오른쪽 자식을 큐에 삽입하는데, 왼쪽 자식부터 삽입한다.

- 그리고 노드를 하나 꺼내면 B가 나오고, B의 왼쪽과 오른쪽 자식이 큐에 삽입된다.

- 그리고 노드를 하나 꺼내면 C가 나오고, C의 왼쪽과 오른쪽 자식이 큐에 삽입된다.

- 그리고 노드를 하나 꺼내면 D가 나온다.

- 더 이상 삽입할 노드가 없고 큐가 공백상태가 될 때까지 노드를 하나씩 꺼내면 E F G 순으로 노드가 나오게 된다.

■ 삽입, 삭제 연산이 \( O(1) \)인 원형 큐를 사용하면 레벨 순회 구현은 다음과 같다.

def levelorder(root_node):
    CQ = CircularQueue()
    CQ.QEnqueue(root_node)
    while not CQ.QIsEmpty(): # 큐가 공백상태가 될 때까지
        node = CQ.QDequeue() # 처음 node는 root_node
        if node is not None:
            print(node.data, end = ' ')
            CQ.QEnqueue(node.left) # root의 left child부터 삽입 시작
            CQ.QEnqueue(node.right) # root의 right child 삽입    
            
levelorder(root_node)
```#결과#```
A B C D E F G 
````````````