4 - (2). 수식 트리 만들기( 수식 트리의 순회 )

아래의 내용에 이어서 진행하도록 하자.

designatedroom87.tistory.com/12?category=869064

4 - (1). 수식 트리 만들기 ( 수식 트리 구성 & 수식 트리 계산 )

 

수식 트리의 순회는 앞에서 이진 트리의 순회와 그 형태가 같다.

designatedroom87.tistory.com/10?category=869064

2. 이진 트리의 순회

아래의 수식 트리 순회 3개의 함수는 앞에서 만든

ExpressionTree 헤더 파일과 소스 파일에 정의한다.

트리의 노드의 데이터에는 숫자 혹은 연산자가 저장되므로

이에 따라 숫자 혹은 단일문자로 출력해주면 된다.

 

1. 수식 트리를 전위 순회하여 데이터를 출력하는 함수

 

2. 수식 트리를 중위 순회하여 데이터를 출력하는 함수

 

3. 수식 트리를 후위 순회하여 데이터를 출력하는 함수

 

메인 함수

 

프로그램 출력 결과

그리고 추가적으로 한 가지 더 프로그래밍을 해보자.

우리가 쓰는 수식은 중위 표기법의 수식이다.

이 수식에는 당연히 소괄호를 이용해서 표현할 수 있다.

여기에 소괄호를 추가한 중위 표기법의 수식을 출력하는 함수를 만들어보자.

아래의 그림을 보자.

이진 트리에서 중위 순회의 호출 스택은 아래와 같이 붉은 숫자로 표현된다.

단말 노드는 피 연산자 노드이다.

괄호를 추가하여 중위 순회를 하면 아래와 같다.

( ( 3 * 2 ) + ( 5 + 6 ) )

위의 내용을 중위 순회의 재귀 함수 호출 스택과 같이 살펴보면 

( 왼쪽 서브 트리 + 오른쪽 서브 트리 ) 

같이 볼 수 있다.

위 식의 왼쪽 서브 트리는 또 다시 *를 연산자로 하는 루트 노드이다.

오른쪽 서브 트리 또한 +를 연산자로 하는 루트 노드이다.

 

노드가 연산자 노드이면 왼쪽 소괄호를 출력하고

왼쪽 서브 트리 데이터를 출력하고 노드 자신의 데이터 출력하고 오른쪽 서브 트리 데이터를 출력하고 나서

노드가 연산자 노드이면 오른쪽 소괄호를 출력하면 된다.

 

조금 더 설명하면 위 처럼 루트 노드가 + 연산자 노드라면 하면

왼쪽 자식과 오른쪽 자식은 숫자 노드이므로

루트 노드가 연산자 노드이면 여는 소괄호를 출력하고 나서

왼쪽 자식과 오른쪽 자식의 노드들을 출력한 다음에

다시 닫는 소괄호를 출력하면 된다.

그러면 왼쪽 서브 트리의 루트 노드는 다시 * 연산자 노드이다.

위와 같은 과정을 반복 하면 된다.

오른쪽 서브 트리의 루트 노드 또한 + 연산자 노드이다.

또한 위와 같은 과정을 반복 하면 된다.

 

수식 트리를 중위 순회하여 소괄호 및 데이터를 같이 출력하는 함수

 

매인 함수

 

프로그램 결과

 

헤더 파일과 소스 파일

BinaryTree.c

0.00MB

BinaryTree.h

0.00MB

common.h

0.00MB

ExpressionTree.c

0.00MB

ExpressionTree.h

0.00MB

main.c

0.00MB

MyStack.c

0.00MB

MyStack.h

0.00MB