이진트리(Binary Tree) - 전위순회, 중위순회, 후위순회

 

🌲 트리(Tree) 

 

개념

 

트리는 비선형 구조로 원소들 간에 1:N 관계를 가지는 자료구조입니다. 원소들 간에 계층 관계를 가지며
상위 원소에서 하위원소로 내려가면서 확장되는 트리(나무) 모양의 구조입니다.

 

용어

• 루트(root) : 노드 중 최상위 노드
• 노드(node) : 트리의 원소
• 간선(edge) : 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
• 루트 노드(root node) : 트리의 시작 노드(부모가 없는 노드)
• 잎 노드(leaf node) : 단말 노드(자식이 없는 노드)

 

• 차수(degree) : 노드의 차수는 노드에 연결된 자식 노드의 수
• 단말 노드(리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드
• 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
• 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨

 

 

---

 

🌲 이진트리(Binary Tree)

 

개념

 

트리 중 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리입니다.

 

특징

• 레벨 i에서의 노드의 최대 개수는 2^i개
• 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수는 (h+1) 개
• 최대 개수는 (2^h+1 -1) 개
• 등비수열의 공식을 활용하여 최대 개수를 구함.

 

종류

• 포화 이진트리(Full Binary Tree)
• 완전 이진트리(Complete Binary Tree)
• 편향 이진트리(Skewed Binary Tree)

 

1. 순회(traversal)

개념

 

순회는 트리의 각 노드를 중복되지 않게 전부 방문하는 것을 의미합니다.
하지만 트리는 비선형 구조이기 때문에, 선형구조에서와 같이 선후 연결 관계를 알 수 없습니다.
따라서 다음과 같은 3가지 방법을 사용합니다.

 

 

1) 전위 순회(preorder traversal)

수행방법

1. 현재 노드 n을 방문하여 처리한다 -> V
2. 현재 노드 n의 왼쪽 서브 트리로 이동한다 → L
3. 현재 노드 n의 오른쪽 서브트리로 이동한다 → R

• 전위 순회 알고리즘

def preorder_traverse(T) : # 전위순회
		if T : # T is not None
				visit(T)  # print(T.item)
				preorder_traverse(T.left)
				preorder_traverse(T.right)

• DFS와 다른 점은 순서가 있는 상태에서 접근한다는 점입니다.

 

 

2) 중위 순회(inorder traversal)

수행방법

1. 현재 노드 n의 왼쪽 서브트리로 이동한다 → L
2. 현재 노드 n을 방문하여 처리한다 → V
3. 현재 노드 n의 오른쪽 서브트리로 이동한다 → R

• 중위 순회 알고리즘

def inodrder_traverse(T) : # 중위순회
		if T : # T is not None
				inodrder_traverse(T.left)
				visit(T)  # print(T.item)
				inodrder_traverse(T.right)

• 순회는 순서만 다르기 때문에 하나의 코드만 잘 작성하고 응용해도 된다.
• 일단 접근은 루트부터 하더라도 무조건 처리는 왼쪽부터!

 

 

 

3) 후위 순회(postorder traversal)

수행방법

1. 현재 노드 n의 왼쪽 서브트리로 이동한다 → L
2. 현재 노드 n의 오른쪽 서브트리로 이동한다 → R
3. 현재 노드 n을 방문하여 처리한다 → V

• 후위 순회 알고리즘

def postorder_traverse(T) : # 후위순회
		if T : # T is not None
				postorder_traverse(T.left)
				postorder_traverse(T.right)
				visit(T)  # print(T.item)

• 밑에 있는 정보들을 활용해서 부모 노드로 보내줄 때 활용