[Data Structure] 이진 트리 : 수식 트리

수식 트리 - 산술 연산자(+, -, *, /), 피연산자로 구성 - 피연산자 = 단말노드 - 산술 연산자 = 비단말노드 - 각 루트노드들은 산술 연산자이기 때문에 루트보다 자식 노드(피연산자)들을 먼저 방문해야한다 그러므로 후위 순회를 사용 알고리즘 root에서부터 시작해서 해당 node가 NULL이면 그냥 return (종료) -- (1) 해당 node의 left, right가 모두 NULL이면 해당 node는 단말노드 = 피연산자 ∴ return 해당 node의 data -- (2) - (1), (2)에 해당이 안되면, 각 node의 left, right에서 (1), (2) 반복 Example) root(+) → evaluate(root->left) = '*' / evaluate(root->righ..

2021.12.13