大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
如何判定C++递归和非递归算法中两个二叉树结构是否完全相同,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。
10年积累的网站设计、成都做网站经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先做网站设计后付款的网站建设流程,更有东胜免费网站建设让你可以放心的选择与我们合作。
具体如下:
/*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法 经调试可运行源码及分析如下: ***/ #include#include #include using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef struct BTreeNode { char elem; struct BTreeNode *pleft; struct BTreeNode *pright; }BTreeNode; /*初始化二叉树节点*/ BTreeNode* btree_init(BTreeNode* &bt) { bt = NULL; return bt; } /*先序创建二叉树*/ void pre_crt_tree(BTreeNode* &bt) { char ch; cin >> ch; if (ch == '#') { bt = NULL; } else { bt = new BTreeNode; bt->elem = ch; pre_crt_tree(bt->pleft); pre_crt_tree(bt->pright); } } /* 递归方式: 如果两个二叉树proot都为空树,则自然相同,返回true; 如果两个二叉树proot一个为空树,另一个不为空树,则不相同,返回false; 如果两个二叉树的数据不相等,返回false; 如果两个二叉树都不为空树,则需要分别比较左右子树后,根据比较结果共同判定,只要有一个为false,则返回false。 */ /*递归判断两个二叉树是否相等(结构和数据)*/ bool bitree_compare(BTreeNode* proot1, BTreeNode* proot2) { if (proot1 == NULL && proot2 == NULL)//都为空 return true; if((proot1 != NULL && proot2 == NULL) || (proot1 == NULL && proot2 != NULL))//一个空,一个非空 return false; /*比较元素*/ if(proot1->elem != proot2->elem) return false; bool left_compare = bitree_compare(proot1->pleft, proot2->pleft); bool right_compare = bitree_compare(proot1->pright, proot2->pright); return (left_compare && right_compare); } /* 非递归方式 借助队列实现 实现算法: 首先将给定根节点proot1和proot2都入队 第一步:当两个队列未空时,分别获取两个树的当前层次中节点总数(即当前队列中节点个数), 先比较节点个数是否相同,如果不相同,则两个树自然不同; 如果节点个数相同,需要出队进行比较(数据也要比较)。如果有一个队列未空,则退出比较。 第二步:如果有一个队列未空,则清空队列并返回不同。 */ /*非递归方式判断两个二叉树是否相等(仅仅结构)*/ bool bitree_compare_leveltraverse(BTreeNode* proot1, BTreeNode* proot2) { if (proot1 == NULL && proot2 == NULL)//都为空 return true; queue que1; queue que2; que1.push(proot1); que2.push(proot2); int cur_level_nodes_num1 = 0; int cur_level_nodes_num2 = 0; bool flag = 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; } int cur_level_node_count1 = 0; int cur_level_node_count2 = 0; while (cur_level_node_count1 < cur_level_nodes_num1 && cur_level_node_count2 < cur_level_nodes_num2) { ++cur_level_node_count1; ++cur_level_node_count2; proot1 = que1.front(); que1.pop(); proot2 = que2.front(); que2.pop(); /*元素数据比较*/ if(proot1->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 << "非递归:reslut is false." << endl; return false; }else { cout << "非递归:reslut is true." << endl; return true; } return true; } int main() { BTreeNode *bt1; BTreeNode* bt2; bool flag; btree_init(bt1);//初始化根节点 btree_init(bt2);//初始化根节点 cout << "creat 1th tree:" << endl; pre_crt_tree(bt1);//创建二叉树 cout << "creat 2th tree:" << endl; pre_crt_tree(bt2);//创建二叉树 /*递归测试*/ flag = bitree_compare(bt1, bt2); if(flag == true) cout<< "递归:result is true." << endl; else cout << "递归:result is false." << endl; /*非递归测试*/ bitree_compare_leveltraverse(bt1, bt2); system("pause"); return 0; }
/* 测试结果如下: creat 1th tree: a b c # # # d e # # f # g # # creat 2th tree: a b c # # # d e # # f # g # # 递归:result is true. 非递归:reslut is true. 请按任意键继续. . . ------------------分界线----------------------- creat 1th tree: a b c # # # d # # creat 2th tree: a b c # # # x # # 递归:result is false. 非递归:reslut is false. 请按任意键继续. . . 本例创建的二叉树形状: a b c # # # d e # # f # g # # 如下: a b d c e f g a b c # # # d # # 如下: a b d c a b c # # # x # # 如下: a b x c */
看完上述内容,你们掌握如何判定C++递归和非递归算法中两个二叉树结构是否完全相同的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注创新互联行业资讯频道,感谢各位的阅读!