比较两个二叉树是否相同（结构和数据），递归和非递归

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本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-01/111643.htm