[자료구조] Program to determine whether two trees are identical

원문링크 : https://www.javatpoint.com/program-to-determine-whether-two-trees-are-identical

Program to Determine Whether two Trees are Identical - javatpoint

 

초기 알고리즘 구상

exception

if root is null

 

compare group of data while traversing the trees in in-order way

1. declare fuction that takes two parameters that are struct node point

2. get two roots from each tree

4. function(node_1->left, node_2->left) unless they are not NULL

5. check if datas are same

6. function(node_1->right, node_2->right) unless they are not NULL

7. return;

 

struct와 node추가 함수

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
struct node{
    int data;
    struct node *right;
    struct node *left;
};
 
struct node *root = NULL;
struct node *root_2 = NULL;
 
struct node* createNode(int data){
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->right = NULL;
    newNode->left = NULL;
    
    return newNode;
}
 

identical을 따지는 함수와 메인함수

bool isIdentical(struct node* node_1, struct node* node_2){
    if(root==NULL&&root_2==NULL){
        printf("these are empty\n");
        return;
    }
    else{
        if(node_1==NULL&&node_2==NULL){
            return true;
        }
        else if(node_1==NULL||node_2==NULL){
            return false;
        }
        else{
            if(node_1->left!=NULL&&node_2->left!=NULL){
                isIdentical(node_1->left,node_2->left);
            }
            if(node_1->data!=node_2->data){
                return false;
            }
            if(node_1->right!=NULL&&node_2->right!=NULL){
                isIdentical(node_1->right,node_2->right);
            }
        }
    }
}
 
int main()
{
    root = createNode(1);  
    root->left = createNode(2);  
    root->right = createNode(3);  
    root->left->left = createNode(4);  
    root->right->left = createNode(5);  
    root->right->right = createNode(6);
    
    root_2 = createNode(1);  
    root_2->left = createNode(2);  
    root_2->right = createNode(3);  
    root_2->left->left = createNode(4);  
    root_2->right->left = createNode(5);  
    root_2->right->right = createNode(6);  
      
    if(isIdentical(root,root_2)){
        printf("Trees are identical\n");
    }
    else{
        printf("Trees are not identical\n");
    }
    
    return 0;
}

 

이렇게 구조를 짜도 두 트리가 동일한지 따지는 함수를 구현하는 것이 가능했다.

원문을 보면, 알고리즘은 비슷하지만 코딩이 좀 더 간단하게 되어있었다.

원문 코드는 나의 코드 중 불필요한 부분을 빼고 조금 심플하게 작성되었다.

 

원문 코드를 참고하여 isIdentical함수를 최적화하면 아래의 코드를 도출할 수 있다.

 

bool isIdentical(struct node* node_1, struct node* node_2){
    
    if(node_1==NULL&&node_2==NULL){
        return true;
    }
    else if(node_1==NULL||node_2==NULL){
        return false;
    }
    else{
        return ((node_1->data==node_2->data)&&
        isIdentical(node_1->left,node_2->left)&&
        isIdentical(node_1->right,node_2->right));
        }
    return false;
}

  

만약 in-order traversal을 이용하여 tree의 data를 print를 한다고 하면,  내가 처음 짠 코드처럼

if문으로 걸러서 in-order traversal을 구현하는 것이 맞다. if문으로 거르지 않고 바로 printf를 해버리면 NULL값을 print해야하는 상황이 생기기 때문이다.

하지만 지금처럼 data를 비교하는 경우에는 NULL값이 함수의 인수로 들어와도 상관이 없다. 함수의 첫 번째, 두 번째 조건문에서 NULL 인 경우를 걸러내기 때문이다.

참고로 위의 코드는 in-order(left-root-right) 순서가 아니라 pre-order(root-left-right) 순서로 tree를 traverse하며 두 트리의 동일성을 따진다. in-order 순서로 바꾸고 싶다면 코드 10번줄의 return 뒷부분과 11번줄의 내용을 바꾸면 된다.