[자료구조]두 이진 트리가 같은지 판별하는 법(Testing for Equality of Binary Trees)

재귀적인 방식을 통해 두 이진 트리의 구조와 각 노드에서의 값을 비교함으로써 두 이진 트리가 같은지 판별할 수 있다.

 

 

아래는 이진 트리의 각 노드로 사용될 구조체입니다.

 

typedef struct treeNode* treePointer;
typedef struct treeNode{
    int data;
    treePointer leftChild;
    treePointer rightChild;
} treeNode;

 

아래 함수의 매개변수로 두 이진 트리의 root를 넣으면, isEqual 함수가 재귀적으로 실행되면서 두 이진 트리의 구조와 각 노드에서의 값을 비교하면서 같은지 같지 않은지를 판별합니다. 같으면 1을 리턴하고, 같지 않다면 0을 리턴합니다.

 

int isEqual(treePointer first, treePointer second){
    return ((!first && !second) || (first && second && (first->data == second->data) && isEqual(first->leftChild, second->leftChild) && isEqual(first->rightChild, second->rightChild);
}

 

위 함수가 실행되는 방식은 다음과 같습니다.

1. 먼저 first와 second가 모두 NULL인지를 확인합니다. 둘다 NULL이라면 같으므로 1을 반환합니다.
2. 만약 first와 second가 모두 NULL이 아니라면, first와 second의 data 값과 왼쪽 서브 트리, 오른쪽 서브 트리가 서로 같은지를 확인해줍니다. 같다면 1을 반환합니다. first와 second의 왼쪽 서브 트리와 오른쪽 서브 트리가 서로 같은지 확인하는 과정에서 isEqual 함수가 호출됩니다.

 

즉, 두 이진 트리의 root인 first와 second를 isEqual 함수의 매개변수로 넣어주면 isEqual 함수가 재귀적으로 실행되면서 두 이진 트리가 같은지를 판별합니다. 이러한 과정을 통해 두 이진 트리의 구조와 각 노드에서의 값이 서로 같은지를 비교합니다.

 

isEqual 함수가 실행될 때마다, first와 second의 왼쪽 서브 트리와 오른쪽 서브 트리를 비교하기 위해, first와 second의 leftChild와 rightChild를 매개변수로 넣은 각각의 isEqual 함수가 재귀적으로 실행됩니다.

 

만약 first와 second 둘 중 하나만 NULL이라면, 이는 두 트리의 구조가 다르다는 것이므로 0이 리턴됩니다.