파이썬 자료구조 - 트리 : 높이

늦었지만 먼저 트리 관련 용어들을 정리하고 시작한다.

루트(root) : 트리의 최상단에 위치한 노드(해당 그림에선 A)

깊이 : 어떠한 노드와 루트와의 거리

레벨 : 깊이가 같은 노드들의 집합

높이 : 루트와 가장 멀리 떨어진 노드와의 거리

 

이번 시간에는 높이를 찾아 볼 것이다.

재귀를 이용해 왼쪽 자식으로 끝까지 이동한 다음, 0을 리턴한다.

이는 좌우 하위 노드가 None이면 끝까지 이동한 것으로 생각할 것이다.

거슬러 올라가며 좌우의 하위노드에서 리턴한 값들 중 값을 비교하여 가장 큰 값에 +1을 하여 리턴한다.

 

코드를 보자.

def height(self,node):
	if node is None:
    	return 0
        
    else:
    	lheight = self.height(node.left)
        rheight = self.height(node.right)
    
    	if lheight > rheight: #좌우를 비교해서 더 큰 값에 +1
        	return lheight + 1
        else:
        	return rheight+1

위에 써놓은 알고리즘을 구현해봤는데, 재귀가 들어가서 이해하기 어렵다.

노트에 그려보면서 이해하는 걸 추천한다.

 

다음 시간에는 높이를 이용해 같은 레벨에 해당하는 노드들을 찾아볼 것이다.