本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同。分享给大家供大家参考，具体如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | /*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法经调试可运行源码及分析如下：***/#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;} |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | /*测试结果如下：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 dc e f ga b c # # # d # # 如下： a b dca b c # # # x # # 如下： a b xc*/ |
希望本文所述对大家C++程序设计有所帮助。
