이진트리 ( binary tree ) 표현법

 

최대 2개의 자식노드를 가지는 트리자료 구조

 

용어 정리

루트 노드 ( root node ) : 맨 상위 노드, 부모가 없는 노드
리프 노트 ( leaf node ) : 자식이 없는 노드
레벨 ( level ) : 트리의 깊이
링크 ( link ) : 노드를 연결하는 선 ( edge )
높이 ( height ) : 루트 노드부터 가장 깊은 레벨의 리프노드까지 링크 개수

 

이진트리 용어 설명

레벨의 수와 트리의 높이는 같다는 것도 알수 있다.

경로 ( path ) : 노드 v 에서 노드 w 로 가는데 거쳐가는 노드

- 위의 그림에서 출발 노드를 1, 도착 노드를 7로 한다면 경로는 1 → 2 → 5 → 7

 

이진트리 표현법

아래의 이진트리를 다음과 같이 3가지 방법으로 표현할수 있다.

예시 그림

1. 리스트로 표현

리스트로 표현

루트 레벨에서 시작해서 아래로 내려오면서 왼쪽부터 리스트에 저장 ( level by level )

A = [a, b, c, None, d, e, f]

None 은 현재 노드 b 의 왼쪽 자식이 없기 때문에 None 으로 표현하였다.

2. 리스트로 표현, 재귀적인 방법을 쓴 경우

아래에서부터 차근 차근 알아보자.

노드 d, e, f 는 리프노드이므로 sub tree 는 없다.

따라서 b와 c 의 sub tree 를 알아보겠다.

b_right_sub_tree = [d, [], []] 
c_left_sub_tree = [e, [], []]
c_right_sub_tree = [f, [], []]

첫번재 index 는 sub tree 에서 최상위 부모 노드,

두번째 index 는 왼쪽 sub tree 최상위 부모노드의 sub tree,

세번째 index 는 오른쪽 sub tree 최상위 부모노드의 sub tree

d, e, f 노드가 전부 리프노드이므로 d, e, f 노드의 서브트리쪽은 전부 빈배열이 들어간다.

 

노드 a 의 sub tree 는 다음과 같이 나타낼수 있다.

a_left_sub_tree = [b, [], [d, [], []]] # 노드 a의 왼쪽 서브트리
a_right_sub_tree = [c, [e, [], []], [f, [], []]] # 노드 a의 오른쪽 서브트리

최종적으로 다음과 같이 나타낼수 있다.

tree = [a, [b, [], [d, [], []]], [c, [e, [], []], [f, [], []]]]

3. 노드를 class 로 표현

클래스화한 노드

바이너리 트리를 표현하기 위해서 정의해야할 클래스의 멤버는 기본적으로 key 값과과, left 링크, right 링크, parent 링크 4개가 필요하다. 그렇게 하면 트리를 직접적으로 표현할수 있다.

a 노드를 만들고 자식 노드를 링크하는 코드는 다음과 같다.

class Node:
	def __init__(self, key=None):
    	self.key = key
        self.left = None
        self.right = None
        self.parent = None
        

node_a = Node('a')
node_a.left = Node('b')
node_a.right = Node('c')

 

Reference

한국외대, 컴퓨터전자시스템공학부, 자료구조 2020-1

https://www.youtube.com/watch?v=w-1w4ood7Bc