![]()
1 #include"iostream"
2 #include"stdio.h"
3 #include"math.h"
4 using namespace std;
5
6 struct BinaryTreeNode
7 {
8 double m_Value;
9 BinaryTreeNode* m_pLeft;
10 BinaryTreeNode* m_pRight;
11 };
12
13 BinaryTreeNode* CreateBinaryTreeNode(double value)
14 {
15 BinaryTreeNode* pNode=new BinaryTreeNode();
16 pNode->m_Value=value;
17 pNode->m_pLeft=nullptr;
18 pNode->m_pRight=nullptr;
19
20 return pNode;
21 }
22
23 void ConnectTreeNodes(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight)
24 {
25 if(pParent!=nullptr)
26 {
27 pParent->m_pLeft=pLeft;
28 pParent->m_pRight=pRight;
29 }
30 }
31
32 void PrintTreeNode(const BinaryTreeNode* pNode)
33 {
34 if(pNode!=nullptr)
35 {
36 cout<<"value of this node is:"<<pNode->m_Value<<endl;
37
38 if(pNode->m_pLeft!=nullptr)
39 cout<<"value of its left child is:"<<pNode->m_pLeft->m_Value<<endl;
40 else
41 cout<<"left child is nullptr."<<endl;
42 if(pNode->m_pRight!=nullptr)
43 cout<<"value of its right child is:"<<pNode->m_pRight->m_Value<<endl;
44 else
45 cout<<"right child is nullptr."<<endl;
46 }
47 else
48 cout<<"this node is nullptr."<<endl;
49 cout<<endl;
50 }
51
52 void PrintTree(const BinaryTreeNode* pRoot)
53 {
54 PrintTreeNode(pRoot);
55
56 if(pRoot!=nullptr)
57 {
58 if(pRoot->m_pLeft!=nullptr)
59 PrintTreeNode(pRoot->m_pLeft);
60
61 if(pRoot->m_pRight!=nullptr)
62 PrintTreeNode(pRoot->m_pRight);
63 }
64 }
65
66 void DestroyTree(BinaryTreeNode* pRoot)
67 {
68 if(pRoot!=nullptr)
69 {
70 BinaryTreeNode* pLeft=pRoot->m_pLeft;
71 BinaryTreeNode* pRight=pRoot->m_pRight;
72
73 delete pRoot;
74 pRoot=nullptr;
75
76 DestroyTree(pLeft);
77 DestroyTree(pRight);
78 }
79 }
80
81 bool Equal(const double &a,const double &b)
82 {
83 if(fabs(a-b)<0.0000001)
84 return true;
85 return false;
86 }
87
88 bool DoesTreeAHaveTreeB(BinaryTreeNode* pRootA,BinaryTreeNode* pRootB)
89 {
90 if(pRootB==nullptr)
91 return true;
92 if(pRootA==nullptr)
93 return false;
94
95 if(Equal(pRootA->m_Value,pRootB->m_Value))
96 {
97 return DoesTreeAHaveTreeB(pRootA->m_pLeft,pRootB->m_pLeft)&&DoesTreeAHaveTreeB(pRootA->m_pRight,pRootB->m_pRight);
98 }
99 else
100 {
101 return false;
102 }
103 }
104 bool HasSubTree(BinaryTreeNode* pRootA,BinaryTreeNode* pRootB)
105 {
106 if(pRootB==nullptr)
107 return false;
108 if(pRootA==nullptr)
109 return false;
110
111 bool result=false;
112
113 if(Equal(pRootA->m_Value,pRootB->m_Value))
114 {
115 result=DoesTreeAHaveTreeB(pRootA,pRootB);
116 }
117 if(!result)
118 {
119 result=HasSubTree(pRootA->m_pLeft,pRootB);
120 }
121 if(!result)
122 {
123 result=HasSubTree(pRootA->m_pRight,pRootB);
124 }
125
126 return result;
127 }
函数
![]()
1 #include"BinaryTree.h"
2
3 // ====================测试代码====================
4 void Test(char* testName, BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2, bool expected)
5 {
6 if(HasSubTree(pRoot1, pRoot2) == expected)
7 printf("%s passed.
", testName);
8 else
9 printf("%s failed.
", testName);
10 }
11
12 // 树中结点含有分叉，树B是树A的子结构
13 // 8 8
14 // / /
15 // 8 7 9 2
16 // /
17 // 9 2
18 // /
19 // 4 7
20 void Test1()
21 {
22 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
23 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
24 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7);
25 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9);
26 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(2);
27 BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4);
28 BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7);
29
30 ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
31 ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
32 ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);
33
34 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
35 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
36 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2);
37
38 ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);
39
40 Test("Test1", pNodeA1, pNodeB1, true);
41
42 DestroyTree(pNodeA1);
43 DestroyTree(pNodeB1);
44 }
45
46 // 树中结点含有分叉，树B不是树A的子结构
47 // 8 8
48 // / /
49 // 8 7 9 2
50 // /
51 // 9 3
52 // /
53 // 4 7
54 void Test2()
55 {
56 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
57 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
58 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7);
59 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9);
60 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(3);
61 BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4);
62 BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7);
63
64 ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
65 ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
66 ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);
67
68 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
69 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
70 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2);
71
72 ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);
73
74 Test("Test2", pNodeA1, pNodeB1, false);
75
76 DestroyTree(pNodeA1);
77 DestroyTree(pNodeB1);
78 }
79
80 // 树中结点只有左子结点，树B是树A的子结构
81 // 8 8
82 // / /
83 // 8 9
84 // / /
85 // 9 2
86 // /
87 // 2
88 // /
89 // 5
90 void Test3()
91 {
92 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
93 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
94 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9);
95 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2);
96 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5);
97
98 ConnectTreeNodes(pNodeA1, pNodeA2, nullptr);
99 ConnectTreeNodes(pNodeA2, pNodeA3, nullptr);
100 ConnectTreeNodes(pNodeA3, pNodeA4, nullptr);
101 ConnectTreeNodes(pNodeA4, pNodeA5, nullptr);
102
103 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
104 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
105 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2);
106
107 ConnectTreeNodes(pNodeB1, pNodeB2, nullptr);
108 ConnectTreeNodes(pNodeB2, pNodeB3, nullptr);
109
110 Test("Test3", pNodeA1, pNodeB1, true);
111
112 DestroyTree(pNodeA1);
113 DestroyTree(pNodeB1);
114 }
115
116 // 树中结点只有左子结点，树B不是树A的子结构
117 // 8 8
118 // / /
119 // 8 9
120 // / /
121 // 9 3
122 // /
123 // 2
124 // /
125 // 5
126 void Test4()
127 {
128 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
129 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
130 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9);
131 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2);
132 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5);
133
134 ConnectTreeNodes(pNodeA1, pNodeA2, nullptr);
135 ConnectTreeNodes(pNodeA2, pNodeA3, nullptr);
136 ConnectTreeNodes(pNodeA3, pNodeA4, nullptr);
137 ConnectTreeNodes(pNodeA4, pNodeA5, nullptr);
138
139 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
140 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
141 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3);
142
143 ConnectTreeNodes(pNodeB1, pNodeB2, nullptr);
144 ConnectTreeNodes(pNodeB2, pNodeB3, nullptr);
145
146 Test("Test4", pNodeA1, pNodeB1, false);
147
148 DestroyTree(pNodeA1);
149 DestroyTree(pNodeB1);
150 }
151
152 // 树中结点只有右子结点，树B是树A的子结构
153 // 8 8
154 //
155 // 8 9
156 //
157 // 9 2
158 //
159 // 2
160 //
161 // 5
162 void Test5()
163 {
164 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
165 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
166 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9);
167 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2);
168 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5);
169
170 ConnectTreeNodes(pNodeA1, nullptr, pNodeA2);
171 ConnectTreeNodes(pNodeA2, nullptr, pNodeA3);
172 ConnectTreeNodes(pNodeA3, nullptr, pNodeA4);
173 ConnectTreeNodes(pNodeA4, nullptr, pNodeA5);
174
175 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
176 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
177 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2);
178
179 ConnectTreeNodes(pNodeB1, nullptr, pNodeB2);
180 ConnectTreeNodes(pNodeB2, nullptr, pNodeB3);
181
182 Test("Test5", pNodeA1, pNodeB1, true);
183
184 DestroyTree(pNodeA1);
185 DestroyTree(pNodeB1);
186 }
187
188 // 树A中结点只有右子结点，树B不是树A的子结构
189 // 8 8
190 //
191 // 8 9
192 // /
193 // 9 3 2
194 //
195 // 2
196 //
197 // 5
198 void Test6()
199 {
200 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
201 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
202 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9);
203 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2);
204 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5);
205
206 ConnectTreeNodes(pNodeA1, nullptr, pNodeA2);
207 ConnectTreeNodes(pNodeA2, nullptr, pNodeA3);
208 ConnectTreeNodes(pNodeA3, nullptr, pNodeA4);
209 ConnectTreeNodes(pNodeA4, nullptr, pNodeA5);
210
211 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
212 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
213 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3);
214 BinaryTreeNode* pNodeB4 = CreateBinaryTreeNode(2);
215
216 ConnectTreeNodes(pNodeB1, nullptr, pNodeB2);
217 ConnectTreeNodes(pNodeB2, pNodeB3, pNodeB4);
218
219 Test("Test6", pNodeA1, pNodeB1, false);
220
221 DestroyTree(pNodeA1);
222 DestroyTree(pNodeB1);
223 }
224
225 // 树A为空树
226 void Test7()
227 {
228 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
229 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
230 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3);
231 BinaryTreeNode* pNodeB4 = CreateBinaryTreeNode(2);
232
233 ConnectTreeNodes(pNodeB1, nullptr, pNodeB2);
234 ConnectTreeNodes(pNodeB2, pNodeB3, pNodeB4);
235
236 Test("Test7", nullptr, pNodeB1, false);
237
238 DestroyTree(pNodeB1);
239 }
240
241 // 树B为空树
242 void Test8()
243 {
244 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
245 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(9);
246 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(3);
247 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2);
248
249 ConnectTreeNodes(pNodeA1, nullptr, pNodeA2);
250 ConnectTreeNodes(pNodeA2, pNodeA3, pNodeA4);
251
252 Test("Test8", pNodeA1, nullptr, false);
253
254 DestroyTree(pNodeA1);
255 }
256
257 // 树A和树B都为空
258 void Test9()
259 {
260 Test("Test9", nullptr, nullptr, false);
261 }
262
263 int main(int argc, char* argv[])
264 {
265 Test1();
266 Test2();
267 Test3();
268 Test4();
269 Test5();
270 Test6();
271 Test7();
272 Test8();
273 Test9();
274
275 return 0;
276 }
