package BinaryTree.LinkedList;
publicclassBinaryTreeMain{
publicstaticvoidmain(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) 오른쪽 서브트리 순회
중위표기법을 후위표기법으로 변환 중위 표기법을 바로 트리로 구현하기 어려움 (괄호 또는 연산자 우선순위 때문에)
후위표기법을 수식트리로 변환 스택을 이용하여 구현 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) 항목 반복
publicdoublecalculate(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;
}
return0;
}
구현
후위표기법으로 변환을 위한 클래스 생성
package Stack;
import Stack.Stack;
import Stack.LinkedList.LinkedListStack;
publicclassPostfixNotation{
publicstatic 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);
}
// 연산자 스택이 비어있을 경우 값 pushelseif (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우// 스택에 저장된 모든 연산자를 반환elseif (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();
}
// 연산자 우선순위 반환publicstaticintgetOpPriority(char c){
switch (c) {
case'*':
case'/':
return3;
case'+':
case'-':
return2;
case'(':
return1;
default:
return -1;
}
}
// 연산자 우선순위 비교publicstaticintcompareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우if (stackOpPriority < curOpPriority){
return1;
}
// 우선순위가 같은 경우elseif (stackOpPriority == curOpPriority){
return0;
}
// 스택의 우선순위가 더 높은 경우else {
return -1;
}
}
}
수식트리 구현을 위한 클래스 (BinaryTree 상속)
package BinaryTree.LinkedList;
import java.util.Stack;
import Stack.PostfixNotation;
publicclassExpressionTreeextendsBinaryTree{
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();
}
publicdoublecalculate(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;
}
return0;
}
}
