[자료구조]이진 트리를 복사하는 법(Copying Binary Trees)

재귀적인 방식을 통해 기존의 이진 트리를 복사할 수 있습니다.

 

 

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

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

 

 

아래 함수에 기존 이진 트리의 root(treePointer)를 넣으면 재귀적인 방식으로 복사되어, 최종적으로는 복사되어 만들어진 이진 트리의 root(treePointer)가 반환됩니다.

 

treePointer copyBinaryTree(treePointer original){
    treePointer temp;
    if(original)
    {
        temp = (treePointer)malloc(sizeof(*temp));
        temp->leftChild = copyBinaryTree(original->leftChild);
        temp->rightChild = copyBinaryTree(original->rightChild);
        temp->data = driginal->data;
        return temp;
    }
    return NULL;
}

 

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

 

1. original을 복사할 temp를 만듭니다.
2. original이 NULL이면 if문을 실행하지 않고 NULL을 반환합니다.
3. original이 NULL이 아니면 if문의 본문을 실행합니다.
4. temp는 treeNode의 포인터이므로 temp에 data, leftChild, rightChild를 담기 위해서는 동적 할당을 해야 합니다. 따라서 malloc으로 temp를 동적 할당 해줍니다.
5. 그 다음, copyBinaryTree를 통해 original의 왼쪽 서브 트리와 오른쪽 서브 트리를 복사한 결과를 각각 leftChild와 rightChild에 저장합니다. 여기서 copyBinaryTree를 재귀적으로 실행됩니다.
6. 그 이후 original의 data 값을 복사하고 temp를 리턴합니다.

 

 

즉, 기존 트리의 root부터 시작하여 copyBinaryTree가 재귀적으로 실행됩니다. copyBinaryTree 함수가 실행될 때마다 왼쪽 서브 트리와 오른쪽 서브 트리를 복사하기 위해 original의 leftChild, rightChild를 매개변수로 넣은 각각의 copyBinaryTree가 재귀적으로 호출되면서 트리 전체를 복사하고, 최종적으로는 기존 트리를 복사한 새로운 트리의 root 노드의 포인터를 반환합니다.