C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

时间：2022-03-19 11:08:05

本文实例讲述了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    d
c     e  f
       g
a b c # # # d # # 如下：
    a
  b    d
c
a b c # # # x # # 如下：
    a
  b    x
c
*/

希望本文所述对大家C++程序设计有所帮助。

标签：

相关文章