이진 트리는 preorder를 기반으로 트리를 구성합니다.

Question

주어진 순서대로 트리를 구성하면 충분히 쉽습니다. 하지만 예를 들어 preorder (예 : + + y z + * x y z)를 기반으로 트리를 구성해야한다고 가정 해 보겠습니다.

+이 루트이고 거기에서 왼쪽 하위 트리를 계속하는 방법을 쉽게 알 수 있습니다. 하지만 .. 언제 당신이 올바른 하위 트리로 "전환"해야하는지 어떻게 알 수 있습니까?

Answer 1

일반적으로 inorder는 어려운 경우로 간주됩니다.

예약 주문의 경우 다음과 같은 문법이 있습니다.

expr ::= operator expr expr | var 

는 오퍼레이터 정확히 두 잘 형성된 식 이어진다. 재귀를 사용하여 쉽게 파싱 할 수 있습니다.

트리를 구문 분석하고 변수를 얻으면 변수를 반환하십시오. 트리를 구문 분석하고 연산자를 얻는 경우 다음 두 트리를 오른쪽/왼쪽 하위 트리로 구문 분석하십시오.