1. 학습
    2. /
  2. 강의
    3. /
  3. Python으로 배우는 자료구조와 알고리즘
Connected

연습 문제

폴란드 표기법을 위한 전위 순회 사용하기

식 트리(Expression tree)는 산술식을 표현하는 이진 트리의 한 종류입니다:

Graphical representation of a binary tree that has arithmetic expressions.

식 트리에 중위 순회(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*입니다.

이 표현식 트리의 접두 표기법을 얻을 수 있도록 전위 순회 코드를 작성하세요.

지침

100 XP
  • current_node가 존재하는지 확인하세요.
  • current_node의 값을 출력하세요.
  • 트리의 알맞은 부분에 대해 pre_order() 함수를 재귀적으로 호출하세요.