10. 트리의 응용과 구현

수식 표현

수식 트리는 수식을 표현하는 이진트리이다. $(2\times (a-1)/(3+b))$를 표현한 수식 트리는 다음과 같다.

수식의 평가를 위한 코드는 아래와 같다.
수식 평가는 후위순회를 이용한다.

def evaluate(v):
	if isExternal(v):
    	return elem(v)
    else
    	x = evaluate(left(v))
        y = evaluate(right(v))
        op = elem(v)
        return x op y

트리의 깊이와 높이 구하기

노드 v의 깊이(Depth)는 v가 루트일 때 0부터 시작한다.

def depth(v):
	if isRoot(v):
    	return 0
    else:
    	return 1+depth(parent(v))

노드 v의 높이(Height)는 v가 leaf 노드일 때 0부터 시작한다.

def height(v):
	if isExternal(v):
    	return 0
    else
    	h = max(height(leftChild(v)), height(rightChild(v)))
        return h+1

연결 트리 구현 ver. 1

각 노드는 다음을 저장한다.

• 원소
• 부모노드의 주소
• 자식노드들의 리스트

루트노드는 부모노드를 저장하지 않는다.

연결 트리 구현 ver. 2

각 노드는 다음을 저장한다.

• 원소
• 부모노드
• 첫째 자식노드
• 바로 아래의 동생노드 (즉, 다음 형제노드)

트리의 함수 성능

작업	이진트리 (배열, 연결리스트)	트리
size, isEmpty	1	1
root, parent	1	1
children(v)	1	자식 갯수만큼
leftChild, rightChild	1	없음
isInternal, isExternal, is Root	1	1
setElement, swapElement	1	1