4주차 2번 문제
📌문제2. 수식 트리
✅ 수식 트리 expression tree
- 산술식을 트리 형태로 표현한 것
- 비단말 노드 : 연산자
- 단말노드 : 피연산자
⭐ Postorder traversal 을 사용해야함!! --> 2개의 피연산자가 있어야 연산이 가능함(피연산자 먼저 방문,왼/오 자식 노드) , 표현 방식은 postfix expression
⭐ 왼쪽, 오른쪽 서브트리의 값(피연산자)을 구하고, 루트에 있는 연산자 계산
✅ evaluate 함수 정의
// BinaryTree 클래스에 작성
int evalute(){return evaluate(root);}
int evaluate(Binary// 수식 트리 계산
int BinaryTree::evaluate(BinaryNode* node) {
if(node == NULL) return 0; // 1. 노드가 NULL이면 0 반환 (기저 조건)
if(node->isLeaf()) return node->getData(); // 2. 리프 노드이면 그 값을 반환
else {
int op1 = evaluate(node->getLeft()); // 3. 왼쪽 자식을 재귀적으로 평가
int op2 = evaluate(node->getRight()); // 4. 오른쪽 자식을 재귀적으로 평가
switch(node->getData()) { // 5. 현재 노드의 연산자로 연산 수행
case '+' : return op1 + op2;
case '-' : return op1 - op2;
case '*' : return op1 * op2;
case '/' : return op1 / op2;
}
return 0;
}
}📢 코드 설명
if(node==NULL) return 0;: 재귀 함수의 종료 조건
if(node->isLeaf()) return node->getData();: 리프 노드일 경우에는 그 데이터를 반환
- 수식 트리에서는 연산을 수행하려면 우선 피연산자를 상위 연산 노드에 제공해야함.
else { ... }: 리프 노드가 아닌 경우 그 노드의 연산자 +,-,*,/를 기반으로 좌우 자식의 피연산자 값을 연산함
int op1,op2 = evaluate(node->getLeft(),getRight());: 현재 노드의 왼쪽/오른쪽 자식을 반환 --> 재귀적으로 evaluate를 호출함
📝 수식 트리 예시
⭐ 주의할 점
⚠️ 재귀 호출은 함수가 완전히 종료되기 전까지는 다음 단계로 넘어가지 않음!!
1) evaluate(+)가 호출된 후
2)int op1 = evaluate(node->getLeft())단계에서 왼쪽 자식인 evaluate(*)가 먼저 완전히 처리된 후에 op1값이 저장됨
3) 그 다음에 op2를 구하는 단계로 넘어감
⚠️ op1 = evaluate() --> evaluate()가 호출되고, 재귀호출이 완료된 후에야 그 결과값 8이 op1에 할당
⚠️ op1,op2를 구하는 과정(아래 코드)이 끝나면 피연산자 2개를 구해서 switch문 수행 --> operator 연산 수행
✅ 문제설명
✅ 테스트 케이스
✅ 아이디어
(1) 1~5번 노드 : 피연산자 노드 생성
(2) 6~9번 노드 : 연산자 노드 생성
(3) 트리 생성 : 노드간 링크 연결하기
(4) 수식 계산
✅ 정답
⭐ BinaryNode 클래스 설계
#include <iostream>
#include <vector>
using namespace std;
class BinaryNode
{
int data;
BinaryNode* left;
BinaryNode* right;
public:
BinaryNode(int val = 0, BinaryNode* l = NULL, BinaryNode* r = NULL)
: data(val), left(l), right(r) { }
~BinaryNode() { }
void setData(int val) { data = val; }
void setLeft(BinaryNode* l) { left = l; }
void setRight(BinaryNode* r) { right = r; }
int getData() { return data; }
BinaryNode* getLeft() { return left; }
BinaryNode* getRight() { return right; }
bool isLeaf() { return left == NULL && right == NULL; }
};
⭐ operator 함수 정의
int
evaluate(BinaryNode* node) { // 수식 트리 계산
if (node == NULL) return 0;
if (node->isLeaf()) return node->getData(); // 단말 노드이면, 피연산자
else { // 비단말 노드이면, 연산자
int op1 = evaluate(node->getLeft()); // 왼쪽 서브트리 계산
int op2 = evaluate(node->getRight()); // 오른쪽 서브트리 계산
switch ((char)node->getData()) { // 수식 계산
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
default: return 0;
}
}
}⭐ 메인 함수
1. N선언, 피연산자,연산자 변수 선언, BinaryNode 벡터 선언
⚠️ tree : BinaryNode 타입의 벡터로, 각 노드의 포인터를 저장함 --> 트리의 노드들은 BinaryNode* 포인터로 관리되기에, 벡터의 크기는 트리의 노드 수 2N-1 에 맞춰야함.
int N, val;
char type;
vector<BinaryNode*> tree;2. N 입력 및 BinaryNode 벡터 크기 확보
⚠️ 자꾸 N 입력 받는거 까먹음
⚠️ vector를 선언했다면 꼭 크기를 설정해줘야함 --> 설정을 놓치면 에러 발생!!
cin >> N;
tree.resize(2 * N, NULL); // 벡터 크기 확보3. 피연산자 노드 생성(=숫자)
⚠️ 1~N번까지 피연산자(=정수) 데이터를 입력받고, BinaryNode 객체로 생성해 tree[i]에 저장
for (int i = 1; i <= N; i++) {
cin >> val;
tree[i] = new BinaryNode(val); // 피연산자 노드 생성
}4. 연산자 노드 생성 및 연결할 자식 정보 저장
⚠️ 연산자 노드를 생성해야하기 때문에 tree[i] = new BinaryNode(type)을 꼭 해줘야함
⚠️ left[i] , right[i] 에 자식 노드 정보를 저장하지 않으면, 자식 노드를 제대로 연결할 수 없음 --> left,right 벡터 생성해주기!!!
vector<int> left(2 * N);
vector<int> right(2 * N);
for (int i = N + 1; i < 2 * N; i++) {
cin >> type >> left[i] >> right[i];
tree[i] = new BinaryNode(type); // 연산자 노드 생성
}5. 트리 생성 : 노드 간의 링크 연결
for (int i = N + 1; i < 2 * N; i++) {
tree[i]->setLeft(tree[left[i]]);
tree[i]->setRight(tree[right[i]]);
}6. 수식 트리 : 트리를 postorder로 방문하여 계산
⚠️ tree[루트 노드] 로 evaluate 한테 넘겨줘야한다!! 그래서 tree[2 * N -1]
cout << evaluate(tree[2 * N - 1]); // 루트 노드에서 수식 계산⚠️ operator node 생성하면서 바로 노드간 링크 연결해도 될까 ? X
= 한꺼번에 노드를 생성하고 바로 노드간 링크를 하면 안됨 --> 노드를 다 만들어놓은 다음에 연결을 해야 left에 8을 할당할 수 있음. 그래서 노드를 다 만들어야, 노드간 링크과정을 거치면서 트리를 생성할 수 있음!!
✅ 내가 짠 코드 --> BinaryTree 클래스까지 만들어서 풀었음
#include <iostream>
#include <vector>
using namespace std;
class BinaryNode
{
int data;
BinaryNode* left;
BinaryNode* right;
public:
BinaryNode(int val = 0, BinaryNode* l = NULL, BinaryNode* r = NULL)
: data(val), left(l), right(r) {}
~BinaryNode() {}
void setData(int val) { data = val; }
void setLeft(BinaryNode* l) { left = l; }
void setRight(BinaryNode* r) { right = r; }
int getData() { return data; }
BinaryNode* getLeft() { return left; }
BinaryNode* getRight() { return right; }
bool isLeaf() { return left == NULL && right == NULL; }
};class BinaryTree {
BinaryNode* root;
public:
BinaryTree() : root(NULL) {}
~BinaryTree() {}
void setRoot(BinaryNode* node) { root = node; }
BinaryNode* getRoot() { return root; }
bool isEmpty() { return root == NULL; }
// 수식 트리 계산
int evaluate() { return evaluate(root); }
int evaluate(BinaryNode* node);
};int BinaryTree::evaluate(BinaryNode* node) {
if (node == NULL) return 0;
if (node->isLeaf()) return node->getData(); // 피연산자인 경우
else {
int op1 = evaluate(node->getLeft()); // 왼쪽 서브트리 계산
int op2 = evaluate(node->getRight()); // 오른쪽 서브트리 계산
switch ((char)node->getData()) { // 수식 계산
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
default: return 0;
}
}
}int main() {
int N, input;
char op;
cin >> N;
vector<BinaryNode*> node;
node.resize(2 * N);
for (int i = 1; i <= N; i++) {
cin >> input;
node[i] = new BinaryNode(input);
}
vector<int> left, right;
left.resize(2 * N);
right.resize(2 * N);
for (int i = N + 1; i <= 2 * N - 1; i++) {
cin >> op >> left[i] >> right[i];
node[i] = new BinaryNode(op);
}
for (int i = N + 1; i <= 2 * N - 1; i++) {
node[i]->setLeft(node[left[i]]);
node[i]->setRight(node[right[i]]);
}
BinaryTree* tree = new BinaryTree();
tree->setRoot(node[2 * N - 1]);
BinaryNode* root = tree->getRoot();
cout << tree->evaluate(root) << endl;
return 0;
}
개발 & 공부 기록