Shulou(Shulou.com)06/03 Report--

How to determine whether the structure of the two binary trees in C++ recursive and non-recursive algorithms is exactly the same? I believe that many inexperienced people are at a loss about this. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

The details are as follows:

/ * whether the structure of two binary trees is the same (structure and data are the same)-the source code and analysis of recursive and non-recursive methods are as follows: * * / # include # include # include using std::cout;using std::cin;using std::endl;using std::queue;/* binary tree node definition * / typedef struct BTreeNode {char elem; struct BTreeNode * pleft; struct BTreeNode * pright;} BTreeNode / * initialize binary tree node * / BTreeNode* btree_init (BTreeNode* & bt) {bt = NULL; return bt;} / * create binary tree in advance * / 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);}} / * Recursive method: if the proot of both binary trees is empty, it is naturally the same, and true is returned. If one of the two binary trees proot is empty, the other is not empty, then it is different. Return false; if the data of the two binary trees are not equal, return false;. If neither of the two binary trees is empty, you need to compare the left and right subtrees respectively. According to the comparison results, it is determined that as long as one is false, false is returned. * / / * Recursively determine whether two binary trees are equal (structure and data) * / bool bitree_compare (BTreeNode* proot1, BTreeNode* proot2) {if (proot1 = = NULL & & proot2 = = NULL) / / both are empty return true; if ((proot1! = NULL & & proot2 = = NULL) | (proot1 = = NULL & & proot2! = NULL)) / / an empty return false; / * comparison element * / 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) } / * non-recursive implementation algorithm with the help of queues: first, both proot1 and proot2 of a given root node are queued. The first step: when the two queues are not empty, get the total number of nodes in the current level of the two trees (that is, the number of nodes in the current queue). First, compare whether the number of nodes is the same. If not, the two trees are naturally different. If the number of nodes is the same, you need to go out of the queue to compare (the data should also be compared). If one queue is not empty, exit the comparison. Step 2: if there is a queue that is not empty, empty the queue and return different. * / / * non-recursive method to determine whether two binary trees are equal (structure only) * / bool bitree_compare_leveltraverse (BTreeNode* proot1, BTreeNode* proot2) {if (proot1 = = NULL & & proot2 = = NULL) / / are both empty 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 (); / / set flag to false when the number of nodes is different, exit the loop 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 } / / judge whether the left and right children are the same, and different affirmative structures are different. Break if in advance (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 } / * nodes of the next layer join the queue * / 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

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.