首页 > 代码库 > 二叉树(10)----比较两个二叉树是否相同(结构和数据),递归和非递归

二叉树(10)----比较两个二叉树是否相同(结构和数据),递归和非递归

1、二叉树定义

typedef struct BTreeNodeElement_t_ {
    void *data;
} BTreeNodeElement_t;


typedef struct BTreeNode_t_ {
    BTreeNodeElement_t     *m_pElemt;
    struct BTreeNode_t_    *m_pLeft;
    struct BTreeNode_t_    *m_pRight;
} BTreeNode_t;


2、比较两个二叉树结构是否相同,不涉及存储的数据

(1)递归方式

如果两个二叉树pRoot都为空树,则自然相同,返回true;

如果两个二叉树pRoot一个为空树,另一个不为空树,则不相同,返回false;

如果两个二叉树都不为空树,则需要分别比较左右子树后,根据比较结果共同判定,只要有一个为false,则返回false。


bool  BTreeCompare( BTreeNode_t *pRoot1, BTreeNode_t *pRoot2)
{
    //如果都为空树,则相同
    if( pRoot1 == NULL && pRoot2 == NULL )
        return true;
    //如果一个为空,一个不为空,则不相同
    if( ( pRoot1 != NULL && pRoot2 == NULL )  ||
        ( pRoot1 == NULL && pRoot2 != NULL ) )
        return false;
    //如果都不为空,则 需要比较左右子树后,再根据比较结果断定
    bool  leftCmp = BTreeCompare( pRoot1->m_pLeft, pRoot2->m_pLeft);
    bool  rightCmp = BTreeCompare( pRoot1->m_pRight, pRoot2->m_pRight);

    return ( leftCmp && rightCmp );
}

(2)非递归方式

借助队列实现

实现算法:

首先将给定根节点pRoot1和pRoot2都入队

第一步:当两个队列未空时,分别获取两个树的当前层次中节点总数(即当前队列中节点个数),先比较节点个数是否相同,如果不相同,则两个树自然不同;如果节点个数相同,需要出队进行比较。如果有一个队列未空,则退出比较。

第二步:如果有一个队列未空,则清空队列并返回不同。


bool  BTreeCompare(BTreeNode_t *pRoot1, BTreeNode_t *pRoot2)
{
    if( pRoot1 == NULL && pRoot2 == NULL )
        return false;

    queue <BTreeNode_t *> que1;
    queue <BTreeNode_t *> que2;

    que1.push(pRoot1);
    que2.push(pRoot2);

    int curLevelNodeTotal1 = 0;
    int curLevelNodeTotal2 = 0;

    bool flag = true; //作为比较不一致时跳出标识
    while( ( !que1.empty()) && ( !que2.empty())) //当两个队列均不为空时,才进行比较
    {
        curLevelNodeTotal1 = que1.size();  //获取树1的当前层节点总数
        curLevelNodeTotal2 = que2.size(); //获取树2的当前层节点总数
        if( curLevelNodeTotal1 != curLevelNodeTotal2){
            flag = false;//当前层节点总数都不一致,不需要比较了,直接跳出
            break;
        }
        int cnt1 = 0;//遍历本层节点时的计数器
        int cnt2 = 0;
        while( cnt1 < curLevelNodeTotal1  && cnt2 < curLevelNodeTotal2){
            ++cnt1;
            ++cnt2;
            pRoot1 = que1.front();
            que1.pop();
            pRoot2 = que2.front();
            que2.pop();

            //判断pRoot1和pRoot2左右节点结构是否相同
            if( ( pRoot1->m_pLeft != NULL && pRoot2->m_pLeft == NULL )    ||
                ( pRoot1->m_pLeft == NULL && pRoot2->m_pLeft != NULL )    ||
                ( pRoot1->m_pRight != NULL && pRoot2->m_pRight == NULL )    ||
                ( pRoot1->m_pRight == NULL && pRoot2->m_pRight != NULL )
            ){
                flag = false;
                break;
            }
 
            //将左右节点入队
            if( pRoot1->m_pLeft != NULL )
                que1.push( pRoot1->m_pLeft);
            if( pRoot1->m_pRight != NULL )
                que1.push( pRoot1->m_pRight);
            if( pRoot2->m_pLeft != NULL )
                que2.push( pRoot2->m_pLeft);
            if( pRoot2->m_pRight != NULL )
                que2.push( pRoot2->m_pRight);
        }

        if( flag == false )
            break;
    }

    //如果比较标志为false,则不相同
    if( flag == false ){
        while( !que1.empty() )
            que1.pop();
        while( !que2.empty())
            que2.pop();

        return false;
    }

    return true;
}


3、比较两个二叉树结构和数据是否同时相同,即两个一模一样的树

与上面的不同之处在于:在比较结构是否相同之后,需要比较当前节点的数据是否一致。

算法是一致的,只需要添加一行代码即可。


(1)递归方式:

bool  BTreeCompare( BTreeNode_t *pRoot1, BTreeNode_t *pRoot2)
{
    //如果都为空树,则相同
    if( pRoot1 == NULL && pRoot2 == NULL )
        return true;
    //如果一个为空,一个不为空,则不相同
    if( ( pRoot1 != NULL && pRoot2 == NULL )  ||
        ( pRoot1 == NULL && pRoot2 != NULL ) )
        return false;
    //比较当前节点中的数据
    if( pRoot1->m_pElemt != pRoot2->m_pElemt)
        return false;
    //如果都不为空,则 需要比较左右子树后,再根据比较结果断定
    bool  leftCmp = BTreeCompare( pRoot1->m_pLeft, pRoot2->m_pLeft);
    bool  rightCmp = BTreeCompare( pRoot1->m_pRight, pRoot2->m_pRight);

    return ( leftCmp && rightCmp );
}


(2)非递归方式

bool  BTreeCompare(BTreeNode_t *pRoot1, BTreeNode_t *pRoot2)
{
    if( pRoot1 == NULL && pRoot2 == NULL )
        return false;


    queue <BTreeNode_t *> que1;
    queue <BTreeNode_t *> que2;


    que1.push(pRoot1);
    que2.push(pRoot2);


    int curLevelNodeTotal1 = 0;
    int curLevelNodeTotal2 = 0;


    bool flag = true; //作为比较不一致时跳出标识
    while( ( !que1.empty()) && ( !que2.empty())) //当两个队列均不为空时,才进行比较
    {
        curLevelNodeTotal1 = que1.size();  //获取树1的当前层节点总数
        curLevelNodeTotal2 = que2.size(); //获取树2的当前层节点总数
        if( curLevelNodeTotal1 != curLevelNodeTotal2){
            flag = false;//当前层节点总数都不一致,不需要比较了,直接跳出
            break;
        }
        int cnt1 = 0;//遍历本层节点时的计数器
        int cnt2 = 0;
        while( cnt1 < curLevelNodeTotal1  && cnt2 < curLevelNodeTotal2){
            ++cnt1;
            ++cnt2;
            pRoot1 = que1.front();
            que1.pop();
            pRoot2 = que2.front();
            que2.pop();

            //比较当前节点中数据是否一致
            if( pRoot1->m_pElemt != pRoot2->m_pElemt ){
                flag = false;
                break;
            }
            //判断pRoot1和pRoot2左右节点结构是否相同
            if( ( pRoot1->m_pLeft != NULL && pRoot2->m_pLeft == NULL )    ||
                ( pRoot1->m_pLeft == NULL && pRoot2->m_pLeft != NULL )    ||
                ( pRoot1->m_pRight != NULL && pRoot2->m_pRight == NULL )    ||
                ( pRoot1->m_pRight == NULL && pRoot2->m_pRight != NULL )
            ){
                flag = false;
                break;
            }
 
            //将左右节点入队
            if( pRoot1->m_pLeft != NULL )
                que1.push( pRoot1->m_pLeft);
            if( pRoot1->m_pRight != NULL )
                que1.push( pRoot1->m_pRight);
            if( pRoot2->m_pLeft != NULL )
                que2.push( pRoot2->m_pLeft);
            if( pRoot2->m_pRight != NULL )
                que2.push( pRoot2->m_pRight);
        }


        if( flag == false )
            break;
    }

    //如果比较标志为false,则不相同
    if( flag == false ){
        while( !que1.empty() )
            que1.pop();
        while( !que2.empty())
            que2.pop();


        return false;
    }


    return true;
}




二叉树(10)----比较两个二叉树是否相同(结构和数据),递归和非递归