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

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