C++ determines whether two binary tree structures are identical based on recursive and non recursive algorithms
- 2020-05-19 05:21:22
- OfStack
In this paper, the example of C++ is used to determine whether two two-tree structures are identical based on recursive and non-recursive algorithms. I will share it with you for your reference as follows:
/* two 2 Whether the fork tree structure is the same ( The structure and the data are the same ) -- Recursive and non-recursive methods
Debugging and running source code and analysis as follows:
***/
#include <stdlib.h>
#include <iostream>
#include <queue>
using std::cout;
using std::cin;
using std::endl;
using std::queue;
/*2 Fork tree node definition */
typedef struct BTreeNode
{
char elem;
struct BTreeNode *pleft;
struct BTreeNode *pright;
}BTreeNode;
/* Initialize the 2 Fork tree node */
BTreeNode* btree_init(BTreeNode* &bt)
{
bt = NULL;
return bt;
}
/* Create the first sequence 2 tree */
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);
}
}
/*
recursively :
If the two 2 tree proot Both are empty trees, then nature is the same, return true ;
If the two 2 tree proot1 One is an empty tree, another 1 Not an empty tree, not the same, return false ;
If the two 2 The data of the fork tree is not equal, return false;
If the two 2 Fork trees are not empty trees, then we need to compare the left and right subtrees, according to the comparison results, as long as there is 1 A for false , the return false .
*/
/* Recursively judge two 2 Whether the fork tree is equal ( Structure and data )*/
bool bitree_compare(BTreeNode* proot1, BTreeNode* proot2)
{
if (proot1 == NULL && proot2 == NULL)// All is empty
return true;
if((proot1 != NULL && proot2 == NULL) ||
(proot1 == NULL && proot2 != NULL))//1 An empty, 1 A non-empty
return false;
/* Comparison of 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
Implement with queues
Implementation algorithm:
The root node is first given proot1 and proot2 All the team
The first 1 Step: when the two queues are not empty, get the total number of nodes in the current hierarchy of the two trees respectively (that is, the number of nodes in the current queue),
First compare the number of nodes is the same, if not the same, the two trees are naturally different;
If you have the same number of nodes, you need to go out and compare ( Data are also compared ) . If you have 1 If the queue is not empty, exit the comparison.
The first 2 Step: if there is 1 If the queue is not empty, the queue is emptied and returned differently.
*/
/* Non-recursive way to judge two 2 Is the fork tree equal (structure only) */
bool bitree_compare_leveltraverse(BTreeNode* proot1, BTreeNode* proot2)
{
if (proot1 == NULL && proot2 == NULL)// All is empty
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();
// Number of nodes 1 When the sample flag Set to false , 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();
/* Element data comparison */
if(proot1->elem != proot2->elem)
{
flag = false;
break;
}
// Judge whether the children are the same, different positive structure is not the same, in advance 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;
}
/* Under the 1 The nodes of the layer are queued */
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 << " Non-recursive: reslut is false." << endl;
return false;
}else
{
cout << " Non-recursive: reslut is true." << endl;
return true;
}
return true;
}
int main()
{
BTreeNode *bt1;
BTreeNode* bt2;
bool flag;
btree_init(bt1);// Initializes the root node
btree_init(bt2);// Initializes the root node
cout << "creat 1th tree:" << endl;
pre_crt_tree(bt1);// create 2 tree
cout << "creat 2th tree:" << endl;
pre_crt_tree(bt2);// create 2 tree
/* Regression test */
flag = bitree_compare(bt1, bt2);
if(flag == true)
cout<< " Recursive: result is true." << endl;
else
cout << " Recursive: result is false." << endl;
/* Non-recursive testing */
bitree_compare_leveltraverse(bt1, bt2);
system("pause");
return 0;
}
/*
The test results are as follows:
creat 1th tree:
a b c # # # d e # # f # g # #
creat 2th tree:
a b c # # # d e # # f # g # #
Recursive: result is true.
Non-recursive: reslut is true.
Please press any key to continue . . .
------------------ Dividing line -----------------------
creat 1th tree:
a b c # # # d # #
creat 2th tree:
a b c # # # x # #
Recursive: result is false.
Non-recursive: reslut is false.
Please press any key to continue . . .
Created for this example 2 Fork tree shape:
a b c # # # d e # # f # g # # As follows:
a
b d
c e f
g
a b c # # # d # # As follows:
a
b d
c
a b c # # # x # # As follows:
a
b x
c
*/
I hope this article is helpful to you C++ programming.