package BinaryTree.LinkedList;
public class BinaryTreeMain {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BTreeNode node1 = binaryTree.createBTreeNode();
BTreeNode node2 = binaryTree.createBTreeNode();
BTreeNode node3 = binaryTree.createBTreeNode();
BTreeNode node4 = binaryTree.createBTreeNode();
BTreeNode node5 = binaryTree.createBTreeNode();
binaryTree.setData(node1, 'A');
binaryTree.setData(node2, 'B');
binaryTree.setData(node3, 'C');
binaryTree.setData(node4, 'D');
binaryTree.setData(node5, 'E');
binaryTree.createLeftSubTree(node1, node2); // B를 A의 왼쪽 서브트리로 등록
binaryTree.createRightSubTree(node1, node3); // C를 A의 오른쪽 서브트리로 등록
binaryTree.createLeftSubTree(node2, node4); // D를 B의 왼쪽 서브트리로 등록
binaryTree.createRightSubTree(node2, node5); // E를 B의 오른쪽 서브트리로 등록
BTreeNode tmpNode = null;
System.out.println(binaryTree.getData(node1)); // 루트 노드 데이터 반환
tmpNode = binaryTree.getLeftSubTree(node1);
System.out.println(binaryTree.getData(tmpNode)); // A의 왼쪽 서브트리 데이터 반환
tmpNode = binaryTree.getRightSubTree(node1);
System.out.println(binaryTree.getData(tmpNode)); // A의 오른쪽 서브트리 데이터 반환
tmpNode = binaryTree.getLeftSubTree(node2);
System.out.println(binaryTree.getData(tmpNode)); // B의 왼쪽 서브트리 데이터 반환
tmpNode = binaryTree.getRightSubTree(node2);
System.out.println(binaryTree.getData(tmpNode)); // B의 오른쪽 서브트리 데이터 반환
}
}
결과
이진트리의 순회
전위순회 (Preorder Traversal) : 루트 노드를 먼저 순회
중위순회 (Inorder Traversal) : 루트 노드를 중간에 순회
후위순회 (Postorder Traversal) : 루트 노드를 마지막에 순회
중위순회 방법 - 재귀적으로 순회 가능
1) 왼쪽 서브트리 순회 2) 루트 노드 방문 3) 오른쪽 서브트리 순회
중위순회 구현
// 중위 순회
void InorderTraverse(BTreeNode node) {
if (node == null){
return;
}
InorderTraverse(node.leftNode);
System.out.println(node.data);
InorderTraverse(node.rightNode);
}
전위순회 및 후위순회 - 중위순회의 방법 1, 2, 3의 순서를 변경 - 중위순회
// 전위 순회
void PreorderTraverse(BTreeNode node) {
if (node == null) {
return;
}
System.out.println(node.data);
PreorderTraverse(node.leftNode);
PreorderTraverse(node.rightNode);
}
- 후위순회
// 후위 순회
void PostorderTraverse(BTreeNode node) {
if (node == null) {
return;
}
PostorderTraverse(node.leftNode);
PostorderTraverse(node.rightNode);
System.out.println(node.data);
}
순회결과
이진트리를 이용한 수식 표현 (수식트리)
이진트리를 이용한 수식 표현 (수식트리)
부모노드의 자식노드 두 개를 피연산자로 한 후 연산 ex) 7+4*2-1
이진트리를 이용한 수식 구현
중위표기법을 후위표기법으로 변환 중위 표기법을 바로 트리로 구현하기 어려움 (괄호 또는 연산자 우선순위 때문에)
후위표기법을 수식트리로 변환 스택을 이용하여 구현 1) 후위표기법의 앞에서부터 스캔 2) 스캔한 문자가 숫자인 경우 스택에 저장 3) 스캔한 문자가 연산자인 경우 스택에서 두 개를 꺼내 연결한 후 다시 스택에 저장
public BTreeNode createExpTree(String exp){
String postfixExp = PostfixNotation.convPostfix(exp);
Stack<BTreeNode> stack = new Stack<>();
char c = ' ';
for(int i=0; i<postfixExp.length(); i++){
node = createBTreeNode();
c = postfixExp.charAt(i);
// 숫자면
if (Character.isDigit(c)){
setData(node, Character.getNumericValue(c));
}
// 숫자가 아니면 (연산자면) 연결
else {
setData(node, c);
createRightSubTree(node, stack.pop());
createLeftSubTree(node, stack.pop());
}
stack.push(node);
}
return stack.pop();
}
ex) 중위표기법 1+2+3
후위표기법
스택
결과
12+3+
+3+
2 1
3+
3+
+
3
수식트리 계산 - 재귀로 구현 1) 단말노드까지 왼쪽으로 이동 (노드의 좌우가 null일 경우) 후 값 반환 2) 단말노드까지 오른쪽으로 이동 (노드의 좌우가 null일 경우) 후 값 반환 3) 부모노드 값(연산자) 반환 4) 연산자에 맞게 계산 진행 5) 1) ~ 4) 항목 반복
public double calculate(BTreeNode node){
double op1 = 0;
double op2 = 0;
// 단말노드인지 확인
if (getLeftSubTree(node) == null && getRightSubTree(node) == null){
// 단말노드일 경우 해당 노드의 값을 가져와 Double 형식으로 변환
return Double.valueOf(getData(node).toString());
}
// 노드의 왼쪽 피연산자 값 반환
op1 = calculate(getLeftSubTree(node));
// 노드의 오른쪽 피연산자 값 반환
op2 = calculate(getRightSubTree(node));
// 연산자 확인 후 계산
switch (String.valueOf(getData(node))){
case "+":
return op1+op2;
case "-":
return op1-op2;
case "*":
return op1*op2;
case "/":
return op1/op2;
}
return 0;
}
구현
후위표기법으로 변환을 위한 클래스 생성
package Stack;
import Stack.Stack;
import Stack.LinkedList.LinkedListStack;
public class PostfixNotation {
public static String convPostfix(String infix){
char c = ' ';
Stack opStack = new LinkedListStack();
StringBuilder sb = new StringBuilder();
for(int i=0; i<infix.length(); i++){
c = infix.charAt(i);
// 숫자이면 표현
if (Character.isDigit(c)){
sb.append(c);
}
// 연산자 스택이 비어있을 경우 값 push
else if (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로
if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우
// 스택에 저장된 모든 연산자를 반환
else if (c == ')'){
char check = ' ';
while(true) {
check = (char) opStack.pop();
if (check == '(') {
break;
}
else {
sb.append(check);
}
}
continue;
}
// 현재 연산자의 우선순위가 더 높은 경우
// 스택에 연산자 저장
if (compareOp((char)opStack.peek(), c) > 0){
opStack.push(c);
}
// 현재 연산자의 우선순위가 더 낮거나 같은 경우
// 스택에 있는 우선순위가 높은 연산자를 빼서 표현
else {
while(!opStack.isEmpty()){
if (compareOp((char)opStack.peek(), c) <= 0){
sb.append(opStack.pop());
}
else {
break;
}
}
opStack.push(c);
}
}
}
char check = ' ';
while(!opStack.isEmpty()) {
check = (char) opStack.pop();
if (check != '(') {
sb.append(check);
}
}
return sb.toString();
}
// 연산자 우선순위 반환
public static int getOpPriority(char c){
switch (c) {
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
default:
return -1;
}
}
// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우
if (stackOpPriority < curOpPriority){
return 1;
}
// 우선순위가 같은 경우
else if (stackOpPriority == curOpPriority){
return 0;
}
// 스택의 우선순위가 더 높은 경우
else {
return -1;
}
}
}
수식트리 구현을 위한 클래스 (BinaryTree 상속)
package BinaryTree.LinkedList;
import java.util.Stack;
import Stack.PostfixNotation;
public class ExpressionTree extends BinaryTree {
BTreeNode node;
public BTreeNode createExpTree(String exp){
String postfixExp = PostfixNotation.convPostfix(exp);
Stack<BTreeNode> stack = new Stack<>();
char c = ' ';
for(int i=0; i<postfixExp.length(); i++){
node = createBTreeNode();
c = postfixExp.charAt(i);
// 숫자면
if (Character.isDigit(c)){
setData(node, Character.getNumericValue(c));
}
// 숫자가 아니면 (연산자면) 연결
else {
setData(node, c);
createRightSubTree(node, stack.pop());
createLeftSubTree(node, stack.pop());
}
stack.push(node);
}
return stack.pop();
}
public double calculate(BTreeNode node){
double op1 = 0;
double op2 = 0;
// 단말노드인지 확인
if (getLeftSubTree(node) == null && getRightSubTree(node) == null){
// 단말노드일 경우 해당 노드의 값을 가져와 Double 형식으로 변환
return Double.valueOf(getData(node).toString());
}
// 노드의 왼쪽 피연산자 값 반환
op1 = calculate(getLeftSubTree(node));
// 노드의 오른쪽 피연산자 값 반환
op2 = calculate(getRightSubTree(node));
// 연산자 확인 후 계산
switch (String.valueOf(getData(node))){
case "+":
return op1+op2;
case "-":
return op1-op2;
case "*":
return op1*op2;
case "/":
return op1/op2;
}
return 0;
}
}
수식트리 테스트 구현
package BinaryTree.LinkedList;
public class ExpressionTreeMain {
public static void main(String[] args) {
ExpressionTree expTree = new ExpressionTree();
BTreeNode expNode = expTree.createExpTree("(1+2)*3");
System.out.println(expTree.calculate(expNode));
}
}
