[자료구조] 수식 트리

수식 트리의 예시

수식 트리 : 산술식을 트리 형태로 표현한 것

단말노드 : 피연산자 (operand)

비단말노드 : 연산자 (operator)

 

수식 트리에서는 후위순회를 사용해서 연산을 진행한다.

 

### 수식 트리 계산 ###

int evaluate() { return evaluate(root); }
    int evaluate(BinaryNode* Node) {
        if (Node == NULL) return 0;
        // 재귀적으로 함수를 호출하다가 NULL을 만나면 0 반환
 
        if (Node->isLeaf()) return Node->getData();
        // 단말 노드일때 노드의 데이터를 반환, 피연산자로 쓰임
 
        else {
            int op1 = evaluate(Node->getLeft());
            // 왼쪽 서브트리를 매개변수로 함수를 호출하는데 단말노드일 경우 값을 반환해서 op1를 초기화
 
            int op2 = evaluate(Node->getright());
            // 오른쪽 서브트리를 매개변수로 함수를 호출하는데 단말노드일 경우 값을 반환해서 op2를 초기화
 
            switch (Node->getData()) {
            case '+': return op1 + op2;
            case '-': return op1 - op2;
            case '*': return op1 * op2;
            case '/': return op1 / op2;
            }
            // 자신 노드의 값에 맞는 연산을 수행 ( 값은 연산자로 구성되어 있음 )
            // 연산이 완료되면 값을 반환해서 상위 노드(연산자)의 피연산자로 사용됨
            
            return 0;
            // 위의 식을 모두 완료했는데도 함수가 반환되지 않으면 함수를 종료 ( 비정상적임 )
            
        }
    }