C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

2024-02-23 22:10:03 46
本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同。分享给大家供大家参考，具体如下：
/*两个二叉树结构是否相同(结构和数据都相同)--递归和非递归方法
经调试可运行源码及分析如下：
***/
#include
#include
#include
usingstd::cout;
usingstd::cin;
usingstd::endl;
usingstd::queue;
/*二叉树结点定义*/
typedefstructBTreeNode
{
charelem;
structBTreeNode*pleft;
structBTreeNode*pright;
}BTreeNode;
/*初始化二叉树节点*/
BTreeNode*btree_init(BTreeNode*&bt)
{
bt=NULL;
returnbt;
}
/*先序创建二叉树*/
voidpre_crt_tree(BTreeNode*&bt)
{
charch;
cin>>ch;
if(ch=='#')
{
bt=NULL;
}
else
{
bt=newBTreeNode;
bt->elem=ch;
pre_crt_tree(bt->pleft);
pre_crt_tree(bt->pright);
}
}
/*
递归方式:
如果两个二叉树proot都为空树，则自然相同，返回true；
如果两个二叉树proot一个为空树，另一个不为空树，则不相同，返回false；
如果两个二叉树的数据不相等，返回false;
如果两个二叉树都不为空树，则需要分别比较左右子树后，根据比较结果共同判定，只要有一个为false，则返回false。
*/
/*递归判断两个二叉树是否相等(结构和数据)*/
boolbitree_compare(BTreeNode*proot1,BTreeNode*proot2)
{
if(proot1==NULL&&proot2==NULL)//都为空
returntrue;
if((proot1!=NULL&&proot2==NULL)||
(proot1==NULL&&proot2!=NULL))//一个空，一个非空
returnfalse;
/*比较元素*/
if(proot1->elem!=proot2->elem)
returnfalse;
boolleft_compare=bitree_compare(proot1->pleft,proot2->pleft);
boolright_compare=bitree_compare(proot1->pright,proot2->pright);
return(left_compare&&right_compare);
}
/*
非递归方式
借助队列实现
实现算法：
首先将给定根节点proot1和proot2都入队
第一步：当两个队列未空时，分别获取两个树的当前层次中节点总数（即当前队列中节点个数），
先比较节点个数是否相同，如果不相同，则两个树自然不同；
如果节点个数相同，需要出队进行比较(数据也要比较)。如果有一个队列未空，则退出比较。
第二步：如果有一个队列未空，则清空队列并返回不同。
*/
/*非递归方式判断两个二叉树是否相等（仅仅结构）*/
boolbitree_compare_leveltraverse(BTreeNode*proot1,BTreeNode*proot2)
{
if(proot1==NULL&&proot2==NULL)//都为空
returntrue;
queueque1;
queueque2;
que1.push(proot1);
que2.push(proot2);
intcur_level_nodes_num1=0;
intcur_level_nodes_num2=0;
boolflag=true;
while(!que1.empty()&&!que2.empty())
{
cur_level_nodes_num1=que1.size();
cur_level_nodes_num2=que2.size();
//节点数目不一样时flag设为false，退出循环
if(cur_level_nodes_num1!=cur_level_nodes_num2)
{
flag=false;
break;
}
intcur_level_node_count1=0;
intcur_level_node_count2=0;
while(cur_level_node_count1elem!=proot2->elem)
{
flag=false;
break;
}
//判断左右孩子是否相同，不同肯定结构不相同，提前break
if(proot1->pleft==NULL&&proot2->pleft!=NULL||
proot1->pleft!=NULL&&proot2->pleft==NULL||
proot1->pright==NULL&&proot2->pright!=NULL||
proot1->pright!=NULL&&proot2->pright==NULL)
{
flag=false;
break;
}
/*下一层的节点入队*/
if(proot1->pleft)
que1.push(proot1->pleft);
if(proot1->pright)
que1.push(proot1->pright);
if(proot2->pleft)
que2.push(proot2->pleft);
if(proot2->pright)
que2.push(proot2->pright);
}
if(flag==false)
break;
}
if(flag==false)
{
while(!que1.empty())
que1.pop();
while(!que2.empty())
que2.pop();
cout<<"非递归：reslutisfalse."<
/*
测试结果如下：
creat1thtree:
abc###de##f#g##
creat2thtree:
abc###de##f#g##
递归：resultistrue.
非递归：reslutistrue.
请按任意键继续...
------------------分界线-----------------------
creat1thtree:
abc###d##
creat2thtree:
abc###x##
递归：resultisfalse.
非递归：reslutisfalse.
请按任意键继续...
本例创建的二叉树形状：
abc###de##f#g##如下：
a
bd
cef
g
abc###d##如下：
a
bd
c
abc###x##如下：
a
bx
c
*/


希望本文所述对大家C++程序设计有所帮助。
C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

热门推荐

随机推荐
