폴란드 표기법을 위한 전위 순회 사용하기
식 트리(Expression tree)는 산술식을 표현하는 이진 트리의 한 종류입니다:
식 트리에 중위 순회(in-order)를 적용하면 중위 표기법(infix notation)을 얻을 수 있습니다. 위 트리의 표기법은 (10-5)*3입니다.
식 트리에 전위 순회(pre-order)를 적용하면 연산자가 피연산자보다 먼저 나오는 접두 표기법(prefix notation), 즉 Polish notation을 얻을 수 있습니다. 위 트리의 표기법은 *-10 5 3입니다.
식 트리에 후위 순회(post-order)를 적용하면 연산자가 피연산자 뒤에 오는 접미 표기법(postfix notation), 즉 reverse Polish notation을 얻을 수 있습니다. 위 트리의 표기법은 10 5- 3*입니다.
이 표현식 트리의 접두 표기법을 얻을 수 있도록 전위 순회 코드를 작성하세요.
이 연습은 강의의 일부입니다
Python으로 배우는 자료구조와 알고리즘
연습 안내
current_node가 존재하는지 확인하세요.current_node의 값을 출력하세요.- 트리의 알맞은 부분에 대해
pre_order()함수를 재귀적으로 호출하세요.
실습형 인터랙티브 연습
이 예제를 이 샘플 코드를 완성하여 풀어보세요.
import queue
class ExpressionTree:
def __init__(self):
self.root = None
def pre_order(self, current_node):
# Check if current_node exists
____:
# Print the value of the current_node
____
# Call pre_order recursively on the appropriate half of the tree
____
____
et = CreateExpressionTree()
et.pre_order(et.root)