두 갈래 나무 동일 판단

1232 단어
To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees.
Algorithm:
sameTree(tree1, tree2) 1: If both trees are empty then return 1. 2: Else If both trees are non -empty (a) Check data of the root nodes (tree1->data == tree2->data) (b) Check left subtrees recursively i.e., call sameTree( tree1->left_subtree, tree2->left_subtree) (c) Check right subtrees recursively i.e., call sameTree( tree1->right_subtree, tree2->right_subtree) (d) If a,b and c are true then return 1. 3: Else return 0 (one is empty and other is not)
/* Given two trees, return true if they are
 structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
    /*1. both empty */
    if (a==NULL && b==NULL)
        return 1;
    /* 2. both non-empty -> compare them */
    if (a!=NULL && b!=NULL)
    {
        return
        (
            a->data == b->data &&
            identicalTrees(a->left, b->left) &&
            identicalTrees(a->right, b->right)
        );
    }
    /* 3. one empty, one not -> false */
    return 0;
}

좋은 웹페이지 즐겨찾기