📦 자료 구조 구현 과제

---

📌 Q1_E_BT

int identical(BTNode *tree1, BTNode *tree2)

{
    // 트리가 비어있을 경우 예외처리
    if(tree1 == NULL || tree2 == NULL){
        if(tree1 == tree2) {
            return true;
        } else {
            return false;
        }
    }

    // 노드가 다르면 false 반환
    if(tree1->item != tree2->item){
        return false;
    } else if(tree1->item == NULL) {
        return true;
    }
    // 노드가 같은데
    // 자식 중 NULL이 하나라도 있으면 둘 다 NULL인지 확인하고 탐색 종료
    // 자식 중 NULL이 없으면 탐색 진행
    else {
        bool isLeftNULL = tree1->left == NULL || tree2->left == NULL;
        bool isRightNULL = tree1->left == NULL || tree2->left == NULL;
        
        if(isLeftNULL){
            if(tree1->left != tree2->left){
                return false;
            }
        } else {
            if(!(identical(tree1->left, tree2->left))){
                return false;
            }
        }
        
        if(isRightNULL){
            if(tree1->right != tree2->right){
                return false;
            }
        } else {
            if(!(identical(tree1->right, tree2->right))){
                return false;
            }
        }

        return true;
    }
}

트리를 어떻게 구현해놨는지 파악하는게 제일 어려웠고,
NULL일때 자식 노드로 탐색을 시작해버리면 tree1->item 했을 때 오류나는거 잡는게 어려웠다.

bool identical(TreeNode *tree1, TreeNode *tree2) {
    // 두 트리가 모두 NULL이면 true 반환
    if (tree1 == NULL && tree2 == NULL) {
        return true;
    }

    // 한 쪽 트리만 NULL이면 false 반환
    if (tree1 == NULL || tree2 == NULL) {
        return false;
    }

    // 현재 노드의 값이 다르면 false 반환
    if (tree1->item != tree2->item) {
        return false;
    }

    // 현재 노드의 값이 같으면 자식 노드로 재귀 호출
    return identical(tree1->left, tree2->left) && identical(tree1->right, tree2->right);
}

gpt한테 개선해달라고 했더니 훨씬 간단하게 짜줬다.

다시 내 코드를 살펴보니

return을 identical && identical로 묶는 것까진 놓칠 수 있다 쳐도
나머지는 말도 안되는 중복이 많았었다.

자식 노드가 NULL인지 아닌지 왼쪽인지 오른쪽인지 생각하면 뭔가 경우의 수가 늘어날거라는 착각을 해버려서 그랬던 것 같다.

1. 두 트리가 모두 NULL
2. 한 쪽만 NULL
3. 둘 다 값 가짐

이것까진 알았는데, 이대로 구현하질 못했다.
다음엔 분기 트리를 작성해봐야하나? 더 복잡해질수도.
일단 앞에서 거른 조건을 뒤에서 또 볼 필요 없다는 것 먼저 가져가보자.

애초에 자식 노드를 살펴봐야한다는 고정관념 때문에 코드가 복잡해진듯?