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 que1;
? ? queue 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 );
}