Week 8-1 : Binary Tree 2

<180605>

0) 트리에서 노드의 갯수 구하기

int getNodeCnt(TreeNode *root)
{
    if(root == NULL) return 0;
    return 1+getNodeCnt(root->left)+getNodeCnt(root->right);
}

>> 트리의 노드의 갯수 = 자기 자신 + 왼쪽 서브트리의 노드의 갯수  + 오른쪽 서브트리의 노드의 갯수

1) 단말노드의 갯수 구하기

int getLeafNode(TreeNode *root)
{
    if(root == NULL) return 0;
    if(root->left == NULL && root->right == NULL) return 1;
    return getLeafNode(root->left) + getLeafNode(root->right);
}

>> 트리에서 단말노드의 갯수 = 왼쪽 서브트리에서의 단말노드의 갯수 + 오른쪽 서브트리에서의 단말노드의 갯수

>> 3 라인에서의 탈출조건이 필요하다. 이 코드가 없다면, root == NULL 인 경우 에러가 발생한다.

>> root 가 NULL 이라는 것은  root 가 가리키는 트리노드가 없다는 뜻이다. 그런데 root->left 가 의미하는 것은 root가 가리키는 변수의 멤버 left 가 된다.

     가리키는 변수가 없는데, 가리키는 변수의 멤버를 찾는 셈이 된다. 

2) 전위순회, 중위순회의 순서가 주어졌을 때, 후위순회의 순서 구하기

전위순회 순서 : 0 1 3 6 7 4 2 5 8 9

중위순회 순서 : 6 3 7 1 4 0 2 8 5 9

1. 전위순회의 경우, 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 순회를 한다. 그렇기 때문에 맨 왼쪽에 있는 0 이 루트라는 사실을 알 수 있다.

2. 중위순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다. 

    그렇기 때문에 6 3 7 1 4 는 루트(0) 기준 왼쪽 서브트리에 있는 노드들이며,  2 8 5 9 는 루트(0) 기준 오른쪽 서브트리의 노드들이 된다.

    전위순회 순서 : [0] [1 3 6 7 4] [2 5 8 9]  

    중위순회 순서 : [6 3 7 1 4] [0] [2 8 5 9] 

    위와 같이 생각할 수 있다.

3.  이젠 왼쪽 서브트리에 대해 생각해보자. 

    전위순회 순서 : [1 3 6 7 4] 

    중위순회 순서 : [6 3 7 1 4] 

    위와 마찬가지로 전위 순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 순회를 한다. 그렇기 때문에 1 이 this 서브트리의 루트라는 사실을 알 수 있다.

4. 중위 순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다. 

    그렇기 때문에 [[6 3 7][1][4]] 와 같이 생각할 수 있다. 1 기준 [6 3 7] 은 왼쪽 서브트리의 노드들, [4]는 오른쪽 서브트리의 노드가 된다.

5. 이 과정을 반복하면 원래의 트리를 복구할 수 있다. 이를 토대로 후위순회를 구하면 된다...!!

>> 프로그래밍 해보고 싶다면 도전!! (http://boj.kr/4256)

>> 내가 푼 코드 (https://github.com/YongHoonJJo/BOJ/blob/master/4256.cpp)

3) 중위순회, 후위순회의 순서가 주어졌을 때, 전위순회의 순서 구하기.

중위순회 순서 : 6 3 7 1 4 0 2 8 5 9

후위순회 순서 : 6 7 3 4 1 8 9 5 2 0

1. 후위순회의 경우, 왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 순회를 한다. 그렇기 때문에 맨 오른쪽에 있는 0 이 루트라는 사실을 알 수 있다.

2. 중위순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다. 

    그렇기 때문에 6 3 7 1 4 는 루트(0) 기준 왼쪽 서브트리에 있는 노드들이며,  2 8 5 9 는 루트(0) 기준 오른쪽 서브트리의 노드들이 된다.

3. 후위순회의 순서에서는 [6 7 3 4 1][8 9 5 2][0] 으로 생각할 수 있다.

    여기서도 왼쪽 서브트리인 [6 7 3 4 1] 에 대해서 생각해보자. 후위순회는 왼쪽 서브트리에 대해서도 후위순회를 한다. 

    그렇기 때문에 1이 왼쪽 서브트리의 루트라는 것을 알 수 있다.

4. 중위 순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다. 

    그렇기 때문에 [[6 3 7][1][4]] 와 같이 생각할 수 있다. 1 기준 [6 3 7] 은 왼쪽 서브트리의 노드들, [4]는 오른쪽 서브트리의 노드가 된다.

5. 이 과정을 반복하면 원래의 트리를 복구할 수 있다. 이를 토대로 전위순회를 구하면 된다...!!

4) 트리의 삭제

int removeTree(TreeNode *root)
{
    if(root == NULL) return ;
    removeTree(root->left);
    removeTree(root->right);
    free(root);
}

>> 전위순회를 하면 왼쪽 서브트리와 오른쪽 서브트리의 루트를 찾아갈 수 없다.

>> 중위순회를 해도 오른쪽 서브트리의 루트를 찾아갈 수 없게 된다.

>> 그래서 후위순회로 삭제를 진행해야 한다.

5) 트리에서 데이터의 값이 홀수인 노드의 갯수를 구하기

\int getOddNode(TreeNode *root)
{
    int cnt=0;
    if(root == NULL) return 0;
    if(root->data & 1) cnt++;
    return cnt + getOddNode(root->left) + getOddNode(root->right);
}

>> 트리에서 테이터의 값이 홀수인 노드의 갯수 = 자신(1 or 0) + 왼쪽 서브트리에서 테이터의 값이 홀수인 노드의 갯수 + 오른쪽 서브트리에서 테이터의 값이 홀수인 노드의 갯수

6) 디렉토리 용량 구하기.

>> 왼쪽 서브트리의 디렉토리의 용량 + 오른쪽 서브트리의 디렉토리의 용량 + 자기 자신의 용량

7) 수식트리

>> 단말노드에 피연산자가 들어있고, 그 외 노드에는 연산자가 들어있다.

>> 후위순회로 계산할 수 있다. 왼쪽 서브트리에서 계산한 결과와 오른쪽 서브트리에서 계산한 결과를 루트에 있는 연산자에 의한 연산을 하면 된다.

8) 레벨순회

- 큐 라는 자료구조를 사용하며, 나중에 배울 그래프에서의 너비우선탐색(BFS) 알고리즘과 완전히 동일하다.

- 또한 TreeNode의 포인터를 담아야 하므로,  23 라인에서 보는 것 처럼 큐의 데이터 타입을 TreeNode* 로 변경하였다.

   (typedef element int 였다면 int를 TreeNode* 로 바꾸면 됬을텐데.. typedef element int 를 쓰는 이유를 다시한번 되새겨보자..!!)

- 알고리즘은 다음과 같다.

1) 우선 루트를 큐에 담는다.

2) 큐가 비어 있지 않다면, 

3) 큐에 있는 노드 하나를 꺼내 해당 데이터를 출력한다.

4) 꺼낸 노드의 왼쪽 자식노드와 오른쪽 자식노드를 큐에 담는다(노드가 존재할 경우). 그리고 2)로 돌아간다.

#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
// Tree
typedef struct TreeNode {
    int data;
    struct TreeNode * left;
    struct TreeNode * right;
} TreeNode;
 
TreeNode* makeTreeNode(int data, TreeNode * left, TreeNode * right) {
    TreeNode * tmp = (TreeNode*)malloc(sizeof(TreeNode));
    tmp->data = data;
    tmp->left = left;
    tmp->right = right;
    return tmp;
}
 
// Queue
typedef struct queue {
    TreeNode * data[MAX];
    int front;
    int rear;
} Queue;
 
void init(Queue * q) {
    q->front = 0;
    q->rear = 0;
}
 
int isEmpty(Queue * q) {
    return (q->front == q->rear);
}
 
int isFull(Queue * q) {
    return (q->rear + 1) % MAX == q->front;
}
 
void enqueue(Queue * q, TreeNode * data) {
    if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n");
    else {
        q->rear = (q->rear + 1) % MAX;
        q->data[q->rear] = data;
    }
}
 
TreeNode* peek(Queue * q) {
    if (isEmpty(q)) {
        printf("(peek)큐가 비어있습니다. : ");
        return NULL;
    }
    return q->data[(q->front + 1) % MAX];
}
 
void dequeue(Queue * q) {
    if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n");
    else {
        q->front = (q->front + 1) % MAX;
    }
}
 
void level(TreeNode * root) {
    Queue q;
    init(&q);
 
    if (root) enqueue(&q, root);
 
    while (!isEmpty(&q)) {
        TreeNode * tmp = peek(&q); dequeue(&q);
        printf("%d ", tmp->data);
        if (tmp->left) enqueue(&q, tmp->left);
        if (tmp->right) enqueue(&q, tmp->right);
    }
}
 
int main()
{
    TreeNode * t8 = makeTreeNode(8, NULL, NULL);
    TreeNode * t4 = makeTreeNode(4, t8, NULL);
    TreeNode * t5 = makeTreeNode(5, NULL, NULL);
    TreeNode * t6 = makeTreeNode(6, NULL, NULL);
    TreeNode * t7 = makeTreeNode(7, NULL, NULL);
    TreeNode * t2 = makeTreeNode(2, t4, t5);
    TreeNode * t3 = makeTreeNode(3, t6, t7);
    TreeNode * t1 = makeTreeNode(1, t2, t3);
 
    TreeNode * root = t1;
    level(root);
}