首页 > 代码库 > 二叉树(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 ); }
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)----比较两个二叉树是否相同(结构和数据),递归和非递归
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。