比較兩個二叉樹是否相同（結構和數據），遞歸和非遞歸

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;
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm