如何判定C++递归和非递归算法中两个二叉树结构是否完全相同

如何判定C++递归和非递归算法中两个二叉树结构是否完全相同，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

具体如下：

/*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法 经调试可运行源码及分析如下： ***/ #include <stdlib.h> #include <iostream> #include <queue> 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 <BTreeNode*> que1;   queue <BTreeNode*> 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++递归和非递归算法中两个二叉树结构是否完全相同的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注亿速云行业资讯频道，感谢各位的阅读！