후위 순회2 [SWEA - Java] 1232. 사칙연산 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD 설명 위 트리는 식 (9/(6-4))*3을 이진트리로 표현한 것이고 이를 계산한 값을 출력하면 된다. 사람들은 사칙 연산을 할때 (9/(6-4))*3식과 같은 중위 표기식으로 계산을 한다.하지만 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위 표기식으로 변환해 계산해야 한다.즉 (9/(6-4))*3 → 964-/3*으로 변환되고 이를 계산한다. 따라서 해당 문제에서는 트리를 입력받고 후위 순회하며 각 단계에서 계산을 해주면 된다. 트리에서 후위 표기식 계산 방법 스택을 이용해 계산하면 된다. 숫자일 경우 바로 스택에 넣는다.. 2021. 10. 24. [Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현 1. 트리 1차원 배열로 구현 주로 포화 이진 트리나 완전 이진트리의 경우 많이 쓰이는 방법이다. 그외의 이진트리도 저장이 불가능한 것은 아니지만 기억공간의 낭비가 심해진다. 따라서 포화 이진 트리이진트리 또는 완전 이진트리를 1차원 배열로 구현해보자. 루트 노드는 1부터 시작한다.(인덱스 0은 사용하지 않는 편이 계산을 간단하게 함) 원하는 노드 n개까지 총 n+1 크기의 1차원 배열을 만든다. 그다음 이진트리의 번호대로 노드들을 저장한다. 배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다. 노드 i의 부모 노드 인덱스 = i / 2 노드 i의 왼쪽 자식 인덱스 = 2i 노드i의 오른쪽 자식 인덱스 = 2i + 1 /** * @author Gwon Minha * * 루트가 1인 완.. 2020. 11. 5. 이전 1 다음 반응형
