C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)
本文实例讲述了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; queue que1; queue que2; 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_count1 elem!=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++程序设计有所帮助。