이진트리의 추가 연산

📌 이진트리의 추가 연산

💡 이진트리의 추가 연산

1. 추가 연산의 종류
   1. 이진트리의 복사
   2. 이진트리가 동일한지 검사
   3. 이진트리의 노드 수 계산
   4. 이진트리의 단말 노드 수 계산

      이진트리의 모든 노드들을 모두 한번씩 다 방문해야 한다.

2. 트리의 모든 노드들을 방문할 필요성
   1. 이진트리의 순회 알고리즘 등을 응용한다.

💡 이진트리의 복사

1. 문제 설명
   1. 입력 이진트리의 노드 구조와 동일한 새로운 이진트리를 생성하고 루트 노드의 주소 반환
   2. 후위순회 알고리즘을 사용한다.

💡 이진트리의 복사 알고리즘

struct node *copy(struct node *original){
    # original 트리를 복사한 새로운 이진트리를 반환한다.
    struct node *temp;

    if(original != NULL){
        temp = (struct node *) malloc(sizeof(struct node));
        temp -> left_child = copy(original -> left_child);
        temp -> right_child = copy(original -> right_child);
        temp -> data = original -> data;
        return temp;
    }
    return NULL;
}

💡 이진 트리의 동일성 검사

1. 문제 설명
   1. 두 개의 이진 트리가 동일한 데이터와 동일한 구조를 갖는지 검사한다.
   2. 여기서 구조란 부모-자식, 형제 노드 등을 말한다.
   3. 전위 순회 알고리즘을 응용한다.

💡 이진 트리의 동일성 검사 알고리즘

int queal(struct node *first, struct node *second){
    # first 와 second 트리가 다를 경우 False, 트리가 동일할 경우 True 를 반환한다.
    return (
        (!first && !second)                                         # 1 
            || (first && second && (first -> data == second -> first) # 2 
                && equal(first -> left_child, second -> left_child) 
                && qeual(first -> right_child, second -> right_child))); # 3
}

1. #1 : first 와 second가 둘 다 NULL 일 경우 True
2. #2 : first 와 second가 둘 다 NULL 이 아니고, 각 노드의 데이터가 같다면?
3. #3 : 노드의 왼쪽 자식, 오른쪽 자식이 같다면 재귀 호출

💡 이진트리의 노드 수 계산

1. 접근 방법
   1. 루트 노드가 NULL dlaus 0 반환
   2. NULL 이 아니면 1 + 왼쪽 서브트리의 노드 수 + 오른쪽 서브트리의 노드 수 를 반환
      1. 서브트리의 노드 수 는 순환 알고리즘으로 구할 수 있다.

         int get_node_cnt(struct node *ptr){
            int cnt = 0;
            if(ptr != NULL){
                cnt = 1 + get_node_cnt(ptr -> left_child) + get_node_cnt(ptr -> right_child);
            }
            return cnt
         }

💡 이진트리의 단말 노드 수 계산

1. 접근 방법
   1. 루트 노드가 NULL 이면 0을 반환
   2. 단말 노드이면 1 반환
   3. 자식이 있을 경우, 왼쪽 서브트리의 단말 노드 수 + 오른쪽 서브트리의 단말 노드 수 를 반환한다.
      1. 서브트리의 단말 노드 수는 순환알고리즘으로 구할 수 있다.

💡 이진트리의 단말 노드 수 계산 알고리즘

int get_leaf_cnt(struct node *ptr){
    int cnt = 0;
    if (ptr != NULL){
        if(ptr -> left_child == NULL && ptr -> right_child == NULL){
            return 1;
        } 
    }
    else{
        cnt = get_leaf_cnt(ptr -> left_child) + get_leaf_cnt(ptr -> right_child);
    }
    return cnt;
}