CH10. 정렬 (Sorting) 1 (단순한 정렬 알고리즘)

• 정렬?
  • 알고리즘 내용이 맞지만 자료구조에서도 다룸
  • 자료구조의 3대 연산인 삽입, 삭제, 탐색 중 탐색에서 다뤄지기 때문
  • 탐색의 성능을 얼마나 끌어올릴수 있느냐가 중요하며, 이와 직결적으로 연관되는것이 정렬 알고리즘이기 때문임
• 탐색에 앞서 수행되어야 하는것이 정렬 알고리즘

CH10-1. 단순한 정렬 알고리즘

• 복잡한 알고리즘들은 어렵게 구현되나 그 성능(속도)이 매우 좋음
• 반면 단순한 정렬 알고리즘은 쉽게 구현되지만 성능이 좋지 못함
  • 단순한 정렬 알고리즘의 방법이 다른 알고리즘에 적용되는 경우가 많음

버블 정렬: 이해

• 차례대로 비교해서 Swap하는 정렬 알고리즘
  • 순서대로 한단계씩
  • linear한 연산으로 정보량이 많아지면 매우 느려지는 단점이 존재
• 앞에서부터 뒤로 가며 중요도 순서대로 좌우로 순서를 바꿔가며 수행됨

버블 정렬: 구현

• 함수의 입력은 정렬할 데이터와 정렬한 데이터의 길이임
• 바깥쪽 for문은 전체 data를 돌기 위한 역할
  • 마지막 데이터 2개는 돌 필요 없으므로 n-1까지만 돌게 됨
• 안쪽 for문은 각 for 루틴마다 데이터를 비교하도록!
  • 즉, 바깥쪽 for문은 0번 인덱스부터 n-1 번째 인덱스까지 돌면서
  • 안쪽 for문은 그 다음 숫자와의 비교연산을 수행!
    • 인덱스 0, 1, 2, 3 -> 0번째에서 0, 1, 2, 3과 비교 -> 1번째에서 1, 2, 3과 비교 -> 2번째에서 2, 3과 비교

버블 정렬: 성능평가

• 시간 복잡도와 공간 복잡도중 시간 복잡도가 critical하기에 시간 복잡도만을 고려함
• 시간 복잡도는 이동보다는 비교 횟수에 critical함 (비교연산에 종속적)
• 비교 연산이 안쪽 for문 안에서 수행됨
  • Worst case의 비교 횟수를 계산하여 수식화 한 후 빅-오를 계산하면 $O(n^{2})$ 가 됨
    • 등차수열의 합 식에서 최고차항만 고려하기때문

선택 정렬: 이해

• 기본적으로 정렬결과 메모리공간을 별도로 할당해야함
  • 메모리 효율 낮음
• 방법은, 가장 작은 값을 찾아서 하나씩 이동시키게 됨
  • 우선순위 높은거 하나씩 찾아서 결과에 갖다놓기
• 메모리 효율을 높게 하기 위해 swap을 이용하여 메모리 낭비를 줄임
  • 동일하게 수행하되, 해당 순서의 우선순위가 높은 data가 갈 자리에 존재하는 data와 자리를 바꿈(swap)

선택 정렬: 구현

• 버블 정렬과 동일하게 바깥 for문은 전체 숫자를 돌게하는 역할
• 안쪽 for문은 해당 숫자가 존재해야 할 자리를 찾도록 숫자들을 오른쪽으로 scan하며 알맞은 index를 정함
• 마지막으로 swap 연산 수행

선택 정렬: 성능평가

• 버블 정렬과 동일함
• Worst case와 Best case의 구분 없이 데이터 이동 횟수는 동일하다는 단점이 존재

삽입 정렬: 이해

• 언뜻 보면 선택정렬과 동일하다고 생각할 수 있음
• 삽입정렬은 맨 왼쪽 첫번째 숫자를 정렬이 되어있다고 가정하고, 나머지 오른쪽 숫자들을 정렬되지 않은 상태로 하여 해당 숫자들이 올바른 자리로 찾아가도록 알맞은 자리에 삽입시킴
• 선택정렬
  • 우선순위가 높은걸 차례대로 가져와서 집어넣음
  • 선택하는 순간에 정렬 알고리즘이 적용됨
• 삽입정렬
  • 기준을 잡아놓고 맞는 자리로 데이터를 집어넣으며 정렬
  • 데이터를 삽입하는 과정에 정렬 알고리즘이 적용됨
• 기본 알고리즘은 동작이 삽입할 위치를 찾고 삽입(이동)되는 식으로 구분되어 있음
• 이를 한번에 수행되도록 구현을 고려하여 최적화
  • 한칸씩 데이터를 밀어내며 알맞은 자리를 만들어놓은 후 최종적으로 해당 자리에 삽입

삽입 정렬: 구현

• 바깥쪽 for문은 첫 번째 data를 정렬되어있다고 fix 해 놓기 때문에 n=1 부터 시작
• 안쪽 for문은 정렬된 데이터들에서 올바른 위치를 찾아가야 하므로 왼쪽으로 가며 탐색
• 이 과정에서 알맞은 자리를 밀어놓고 들어갈 자리를 만들어둠

삽입 정렬: 성능평가

• if문이 안쪽 for문에 존재
• 앞과 동일한 빅-오를 가짐 ( $O(n^{2})$ )

CH9-2. 힙의 구현과 우선순위 큐의 완성

원리 이해 중심의 힙 구현: HDelete

• 편의를 위해 약간의 연산과정 변경을 거쳐 코드로 구현
  • 논리상 삭제 시 맨 마지막 노드의 값이 1번 자리로 이동해야 하지만, 이렇게 될 경우 소모적인 swap 연산이 계속 반복되어야 함
  • 따라서 구지 옮기지 않고, 가야할 자리의 인덱스(1)와 마지막 노드의 값을 임시로 저장해 이를 이용한 비교연산 수행
• while 문에서 우선순위 높은 자식의 인덱스 값을 childIdx로 받아
  • 마지막 노드의 우선순위와 비고하여 마지막 노드의 우선순위가 높으면 while문 탈출
    • parentIdx엔 마지막 노드가 저장될 인덱스(위치)가 저장됨
  • 아니면 레벨을 올리기 위한 대입연산 수행
• 최종적으로 삭제된 노드의 값을 반환

원리 이해 중심의 힙 구현: HInsert

• 마지막 노드 자리에 새 노드를 넣으면 delete와 마찬가지로 반복/소모적인 swap 연산을 계속 해야함

• 따라서 delete와 동일한 방법으로 insert 수행

• 새 노드가 저장될 인덱스 값을 임시로 받고, 새 노드의 생성 및 초기화(임시)
• idx가 1이면 root 자리이므로, 1이 아닐 동안 while문을 돌음
  • if문으로 새 노드와 부모노드의 우선순위를 비교해 새 노드의 우선순위가 높다면
    • 부모 노드를 한 레벨 내림(대입연산으로 실제로 내림)
    • 새 노드를 한 레벨 올림(인덱스 값만 갱신하여 실제로 올리지 않음)
  • 아닐 경우 break
• 마지막으로 새 노드를 만들어진 자리(idx)에 집어넣고 전체 데이터 갯수 numOfData 1개 증가

힙의 확인을 위한 main 함수와 단점

• 위와 같은 구성은 사용자가 직접 데이터의 우선순위를 결정해야 하는 방식
• 일반적인 경우, 일관성을 위해 입력된 data를 기반으로 자동으로 프로그램이 알아서 우선순위를 결정하는것이 합리적인 구성

쓸만한 수준의 힙 구현: 구조체 변경

• 기존에는 pr과 data를 따로 HeapElem 에서 받아 Heap 구조체가 완성됨
• 이를 data와 data에 근거해 자동으로 우선순위를 결정하는 함수를 멤버로 선언한 구조체를 생성하고, 이를 Heap으로 정의
  • * comp 멤버에 우선순위 결정하는 함수의 주솟값 저장
  • 우선순위 결정 함수에 의해 자동으로 data에 따라 우선순위가 반환됨

• HeapInit 함수에서도 노드의 갯수 초기화 외에 우선순위 결정하는 함수의 등록도 수행되어야 함

• 함수 포인터?
  • 일반적인 경우 typedef int *FunctionName(int A, int B) 또는 typedef *int FunctionName(int A, int B)로 구성
  • 이럴 경우, 구조체 멤버 변수 선언 시 *가 포함되면 안됨
  • 반대로 위와 같이 함수가 typedef int FunctionName(int A, int B)로 선언 된 경우, 구조체 멤버 변수 선언시 멤버 변수에 *가 포함되어야 함
  • 이는 일종의 약속, 단 매개변수 선언은 예외가 됨(위 약속을 따르지 않음)

쓸만한 수준의 힙 구현: PriorityComp

• 함수에 인자가 두개 전달될 경우 경우에 따라 반환되는 값들이 달라짐
• 또한 Insert 함수에서도 pr을 별도 인자로 받지 않고 구조체 내의 comp함수와 data로 자동으로 계산되어 우선순위 설정되도록 함
• 이는 임의로 설정된 조건으로, 사용자의 편의에 따라 아무렇게나 바뀌어도 됨

쓸만한 수준의 힙 구현: Helper 함수의 변경

• if문의 조건에서 대소가 바뀌는것은 앞의 PriorityComp함수의 조건에 따라 바뀌는 것임
  • 따져보면 동일한 조건

쓸만한 수준의 힙 구현: HInsert의 변경

• 위와 마찬가지로 비교함수 조건에 따른 if문의 대소만 변경

쓸만한 수준의 힙 구현: HDelete의 변경

• 위와 동일함

쓸만한 수준의 힙 구현: main 함수

• 구조체의 data를 이용하여 자동으로 우선순위를 결정하는 함수를 정의
  • 아스키 코드 값이 작은 문자의 우선순위가 더 높도록 설정
• main 문에서 순서대로 A, B, C 힙에 저장 후 A 출력, 또 A, B, C 힙에 저장 후 A 출력, while문에서 순서대로 B, B, C, C 출력됨

쓸만한 수준의 힙을 이용한 우선순위 큐의 구현

• 앞의 힙은 우선순위 큐에만 최적화하여 구현됨
• 다라서 껍데기만 우선순위 큐로 씌워주면 그대로 우선순위 큐가 됨

CH9-2. 힙의 구현과 우선순위 큐의 완성

• 힙을 이용해 우선순위 큐를 구현
  • 힙은 우선순위 큐의 구현에 사용되는 도구
  • 우선순위 큐와 힙은 어느정도 맥락이 상통하지만, 엄연히 다름
  • 힙의 데이터 저장 및 삭제가 가장 관건
• 힙은 우선순위 큐의 구현에 가장 효율적인 자료구조형

힙에서의 데이터 저장과정

• 우선순위는 값이 낮을수록 우선순위가 높다고 가정 (오름차순)
• 새로운 노드의 추가에는 반드시 아래의 두 조건이 만족되어야 함
  • 부모 노드 데이터의 우선순위는 항상 자식 노드 데이터의 우선순위보다 같거나 높아야 함
  • 트리의 형태는 항상 완전이진트리를 만족해야 함
    • 왼쪽 아래부터 꽉 채워지도록 차례대로 추가
• 새로운 노드의 추가
  1. 우선 새 노드가 들어올 경우 맨 아래에 저장
  2. 다음으로, 저장된 위치 상단의 부모 노드와 비교를 통해 자기 자리를 찾아감
  3. 부모 노드보다 중요도가 떨어질 경우, 해당 자리에 저장됨
• 이런 방식으로 추가되면 위의 두 조건을 모두 만족하며 새 데이터를 저장 할 수 있음
• 단, 우선 순위 정렬을 봤을 때 같은 층에는 왼쪽엔 작은 수(우선순위가 높은 수)가, 오른쪽으로 갈수록 큰 수 (우선순위가 낮은 수)가 저장되어야 함

힙에서의 데이터 삭제과정

• 루트 노드의 삭제만 고려됨
  • 우선순위 큐의 구현이 목적이기 때문에
    • 우선순위 큐는 우선순위가 가장 높은 루트 노드의 값만 한번에 하나씩 참조되므로
• 기존 노드의 삭제는 반드시 아래의 과정을 따름
  1. 우선 루트 노드가 참조되어 사라짐
  2. 참조된 루트노드의 빈자리는 트리의 가장 마지막 노드의 데이터가 이동되어 채워짐
  3. 루트 노드에 위치한 가장 마지막 노드의 데이터는 우선순위 비교를 통해 자신의 자리로 찾아감
  4. 자신의 자리가 찾아 진 경우 해당 위치에 데이터가 최종적으로 저장됨
• 루트 노드에 위치한 데이터의 비교는 우선순위 비교를 통해 우선순위가 높은 데이터와만 1대1로 비교가 됨
• 애초에 힙에 데이터 저장 시 같은 층에서 맨 왼쪽이 가장 우선순위가 높은 데이터가 저장되므로 맨 왼쪽 노드와의 비교만 수행하면 됨

삽입과 삭제의 과정에서 보인 성능의 평가

• 배열 및 연결리스트 기반의 데이터 삽입/삭제 시간 복잡도는 worst case에서 O(n)임
  • 이는 n개 데이터에 대한 참조 및 비교를 수행해야 하기 때문임
• 힙은 $O(\log_{2}{n})$ 의 시간 복잡도를 보임
  • 이는 heap의 각 단계가 2의 최대 2의 배수개 만큼의 데이터를 저장 할 수 있기 때문
  • 새로운 데이터가 저장 될 경우, 층수 만큼의 참조 및 비교 연산만을 수행하면 되기 때문임
• 만약 15번째까지 데이터가 저장되어있고 16번째 데이터가 들어오는 경우
  • 배열 및 연결리스트는 참조 및 비교가 최대 16번 수행되어야 함(worst case)
  • 힙은 각 층별 1, 2, 4, 8개로 총 15개의 데이터에 대해 층별 비교만 수행하면 되므로 최대 4번의 참조 및 비교만 수행되면 됨

배열을 기반으로 힙을 구현하는데 필요한 지식들

• 힙은 배열을 기반으로 구현하는 대표적인 이진 트리 구조임
• 연결 리스트 기반으로 힙을 구현할 경우 새 노드를 힙의 마지막 노드에 위치시키는것이 어려움
• 또한 연결리스트 기반은 참조의 과정도 복잡함 (루트부터 타고 넘어가야 하므로)
• 배열 기반의 이진트리를 이용할 경우, 각 노드의 배열 인덱스가 갖는 규칙성을 이용하여 쉽게 자식/부모간의 인덱스 상관관계를 찾을 수 있음
  • 각 관계는 위 사진 참고
    • 2번 인덱스 기준 왼쪽 자식은 4, 오른쪽 자식은 5이므로 관계 성립
    • 5번 인덱스 기준 부모는 5//2=2 이므로 관계 성립
• 무엇보다 배열 기반의 이진트리는 최상단/마지막 노드의 접근이 용이함
• 참고로 배열 기반의 이진트리는 앞 챕터에서 설명된것처럼 0번 인덱싱을 사용하지 않음(안정성)

원리 이해 중심의 힙 구현: 헤더파일의 소개

• 위에서 정의된 힙 헤더는 우선순위 큐에 최적화되어 구현됨
• 각각 heap에 저장되는 data의 구조체와 heap의 구조체가 차례대로 정의
  • 여기서 데이터와 우선순위 정보 pr을 구분하여 저장함
• HDelete 함수도 우선순위 큐에 최적화되어 구현됨

원리 이해 중심의 힙 구현: 숙지할 내용

• 힙은 완전 이진 트리
• 힙의 구현은 배열을 기반으로 하며 0번 인덱스는 사용하지 않음
• 힙에 저장된 노드의 개수와 마지막 노드 인덱스는 일치
  • 이는 index가 1부터 시작되기 때문임
  • 새로 추가될 노드는 마지막 index + 1로 쉽게 정의 가능
• 노드 고유번호가 노드에 저장되는 인덱스 값
• 우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정
• 무엇보다 배열을 사용하므로 첫번째/마지막번째 노드의 인덱스 값을 쉽게 얻을 수 있음

원리 이해 중심의 힙 구현: 초기화와 Helper

• 각 helper function은 앞에서 정의된 부모 노드간의 인덱스 관계를 이용하여 각 인덱스 값을 반환함

원리 이해 중심의 힙 구현: Helper

• 위 함수는 우선순위가 높은 자식의 인덱스 값을 반환함
  • 우선순위 숫자 pr이 작을수록 우선순위가 높게 정의됨
  • 우선, 자식 노드가 존재하지 않는다면 0을 반환
    • numOfData는 마지막 노드의 인덱스이므로, 자식 노드의 인덱스가 이 값보다 크다면 존재하지 않는 자식 노드임
  • 만약, 자식 노드가 왼쪽 자식 노드 하나만 존재한다면
    • 완전 이진트리 형식으로 데이터가 저장되므로 numOfData값은 자식 노드가 왼쪽 자식 노드 하나만 존재할경우 항상 왼쪽 자식 노드의 인덱스와 동일하게 됨
  • 자식 노드가 양쪽에 존재할 경우
    • 오른쪽 자식 노드의 우선순위가 높으면 오른쪽 자식 노드의 인덱스 값을
      • pr 값은 작을수록 우선순위가 높게 정의됨
    • 아니라면 왼쪽 자식노드의 인덱스 값을 반환

CH9. 우선순위 큐 (Priority Queue) 1 (우선순위 큐의 이해)

• 기존에 공부했던 큐의 연장선이 아님
  • 적절한 비교가 아님
  • 기존의 큐는 반드시 선입선출 되는 꼴
• Chapter 8의 이진트리의 연장선상에서 보는게 옳음
  • 선형 자료구조의 큐와 우선순위 큐는 완전히 다름! (비교하기 애매함)
• 우선순위 큐는 비선형 자료구조

CH9-1. 우선순위 큐의 이해

• 내용 자체는 어렵지 않음
• 기존의 선형 자료구조의 큐
  • 선입 선출
  • 먼저 들어온 자료가 먼저 출력됨
• 우선순위 큐
  • 큐와 구조만 동일
  • 입구 출구가 구분되어 있어서 큐라고 불림
  • 저장되는 데이터의 우선순위를 정하고, 그 우선순위에 따라 데이터가 저장되어 그 순서대로 데이터가 출력됨
  • 예를 들어
    • 중요도가 A>B>C 인 자료가 우선순위 큐에 C, A, B 순으로 저장될 경우?
      • 저장시에 자동 정렬되어 중요도 순으로 저장이 됨
    • 출력은 중요도 순인 A - B - C 순으로 출력됨

우선순위 큐와 우선순위의 이해

• 일반 큐와 우선순위 큐는 이름만 같지 완전히 다른 구조를 가짐
• 우선순위 큐는 들어간 순서에 상관없이 우선순위를 근거로 dequeue 연산이 진행됨
  • 우선순위의 근거는 활용에 따라 프로그래머가 직접 정할 수 있음

우선순위 큐의 구현 방법

• 우선순위 큐의 구현 방법
  • 배열을 기반으로 구현
  • 연결 리스트를 기반으로 구현
  • 힙을 이용하여 구현
• 위 구현 방법 중 배열과 연결리스트의 구현 방법은 쉬움
• 하지만 두 방법은 치명적인 단점이 존재
• 배열 기반으로 우선순위 큐가 구현 될 경우
  • 저장될 data가 많아 질 경우 매우 불리해짐
    • 새로 저장 될 데이터를 중요도에 근거해 일일히 전체 비교를 거쳐 알맞은 자리를 찾은 후
    • 알맞은 자리에 자료를 넣기 위해 전체 자료를 밀어내야 함
    • 자료가 참조되어 삭제 될 경우 빈 자리를 메꾸기 위해 뒤의 모든 자료를 당겨야 함
• 연결 리스트 기반으로 우선순위 큐가 구현 될 경우
  • 저장될 data가 많아 질 경우 불리함
    • 배열과 다르게 이동은 필요 없지만, 노드간의 연결을 타고 모든 노드에 접근하여(주소) 비교연산을 해야 함
    • 비교 연산시의 비용이 매우 큼
• 결과적으로 배열/연결리스트 기반 구현은 쉽지만 동작이 굉장히 비효율적
• 힙을 이용한 우선순위 큐의 구현이 가장 효율적으로

힙 (Heap) 의 소개

• 완전 이진트리의 일종 (수식트리처럼)
  • 완전이진트리: 왼쪽에서 오른쪽으로 데티러르 차곡차곡 채워나가는 꼴
• 최대 힙에서, 중요도 순서는 상 하 관계만 따짐
  • 좌 우 관계는 상관없음.
• 즉, 우선순위가 가장 높은 값이 루트 노드쪽에 저장 되어야 함
  • 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 함
• 최소 힙은 최대 힙과 반대로 작은 값일수록 루트 노드쪽에 저장됨
• 힙은 우선순위 큐의 구현에 가장 효율적인 방법임

CH8. 트리(Tree) 4 (수식 트리 (Expression Tree) 의 구현)

• 지난 시간까지 만들어놓은 이진 트리를 구성하는 도구를 이용하여 수식트리를 구현
• 수식트리는 이진트리의 일종으로, 수식을 트리 형식으로 구현하는것을 의미
• 전, 중, 후위 연산자처럼 도 하나의 수식 표기 방법
  • 다만, 메모리 관점에서 내용이 설명됨(루트 노드의 주소를 저장)

수식 트리의 이해

• 중위 표기법의 수식을 수식 트리로 변환하는 프로그램을 작성하는것이 목적
• 중위 표기법 수식은 사람이 이해하기 쉽지만 기계가 인식하기에는 어려움
• 따라서 중위 표기법 수식을 수식 트리로 재구성
• 수식 트리는 해석이 쉬움
  • 연산 과정에서 연산자의 우선순위 고려가 필요 없음
• 가운데 루트노드 자리가 연산자, 아래의 하위 노드가 피연산자 역할을 하게 됨

수식 트리의 계산과정

• 자식 노드가 피연산자, 루트 노드가 연산자 역할을 함

수식 트리를 만드는 절차

• 중위 표기법의 수식을 후위 표기법의 수식으로 변환 후, 이를 기반으로 수식 트리를 만듦
  • 후위 표기법 수식으로 수식트리를 만드는게 가장 쉽기 때문에 두 단계로 나눔
• 앞 스택 단원에서 사용한 코드를 이용

수식 트리의 구현과 관련된 헤더파일

• 앞에서 정의된 트리를 만드는 도구를 기반으로 함수를 정의함
  • 본 단원에선 수식 트리를 만드는데 필요한 함수들을 정의
• 전위, 중위, 후위 순회는 앞에서 다룬대로 참조의 순서만 바꾸면 됨

수식 트리의 구성 방법: 그림 이해

• 후위 표기법의 수식이 들어오면
• 앞에서부터 차례대로 참조하여 숫자가 등장하면 stack에 저장
• 저장하다가 연산자가 나오면 연산자를 root 노드로 하여 트리를 구성
• 구성된 트리를 다시 숫자가 저장되는 stack에 통째로 저장(피연산자처럼!)
  • 저장에는 root 노드의 주소만 저장하면 됨
• 만들어진 하위 트리를 피연산자로 하여 앞의 연산을 반복하고, 상위 트리를 구성
• 전체 완료된 경우 이를 또 stack에 넣음
  • root 주소만 저장
• 후위 표기법 수식에서 먼저 등장하는 피연산자와 연산자를 이용해 트리의 하단부터 구성해가고, 이어서 윗부분을 구성하면 됨

수식 트리의 구성 방법: 코드로 옮기기

• Rule 1. 피연산자는 무조건 스택으로
• Rule 2. 연산자 만나면 스택에서 피연산자 두개 꺼내서 트리 구성

• Rule 3. 형성된 트리는 다시 스택으로 (루트 주소 저장)
• Rule 4. 최종 결과도 스택으로

• 함수에선 피연산자인지, 아닌지에 따라 if문으로 동작을 구분
  • 피연산자(숫자)가 등장한 경우 문자를 정수로 바꿔서 stack에 저장할 준비를 하고
  • 연산자라면, pop으로 stack에서 두 피연산자를 꺼낸 후 해당 연산자로 tree를 구성 해 stack에 저장할 준비를 하고
• stack에 저장할 준비가 된 값을 stack에 저장 (Spush(&stack, phone);)
• 최종적으로 수식 트리의 루트 노드의 주솟값을 반환
  • stack에는 무조건 root 노드의 주솟값이 저장되어있을것이므로 Spop 함수를 이용

수식 트리의 순회 결과

• 전위 순회하여 데이터를 출력하면 -> 전위 표기법 수식
  • 중위, 후위도 순회 방법에 따라 각각 중위 표기법, 후위 표기법의 수식이 출력됨
• 수식을 수식 트리로 구성하면 전위, 중위, 후위 표기법으로의 수식 표현이 쉬움
• 전위, 중위, 후위 순회하며 출력되는 결과물을 통해 MakeExpTree 함수를 검증 할 수 있음

수식 트리의 순회 방법

• 수식 출력 함수는 연산자/피연산자에 따라 구분해 출력

수식 트리 관련 예제 실행

수식 트리의 계산: 기본 구성

• 서브 트리가 고려되지 않은 구성

수식 트리의 계산: 재귀적 구성

• 재귀적 구성을 통해 하위 트리를 구성했지만, 최 하단 단말 노드에 대한 고려가 되어있지 않음
  • 즉, 재귀 함수에 탈출 조건이 존재하지 않음

수식 트리의 계산

• 좌, 우 서브트리가 각각 NULL 포인터 주소를 가질 경우, 해당 노드의 데이터를 반환하도록 구성

1. 최 상단 트리에서 왼쪽 하위 트리를 참조했을 때
2. 말단 노드가 아니므로 또 왼쪽 하위 트리를 참조했을 때
3. 말단 노드인지 판단키 위해 해당 노드에서 하위 트리 주소를 보면
4. 두 하위 트리 주소가 모두 NULL 포인터이므로
5. 말단 노드로 판단하고 1을 반환
6. 다음으로 오른쪽 하위 트리로 가서 해당 노드가 말단 노드인지 판단키 위해 하위 트리 주소를 보면
7. 두 주소가 모두 NULL이므로
8. 말단 노드로 판단하고 2를 반환
9. 반환된 두 값 (1, 2)과 연산자(+)를 이용해여 결과 3을 만들어 반환
10. 다음으로 오른쪽 하위 트리로 가서 해당 트리가 말단 노드인지 판단키 위해 하위 트리 주소를 보면
11. 두 주소 모두 NULL 포인터이므로 말단 노드로 판단하고
12. 해당 노드의 값 7을 반환
13. 두 하위 노드에서 반환된 값 3과 7을 이용해 루트 노드에 저장된 연산자 (*)를 이용해 값을 계산하여 21을 반환