剑指offer第十八题：树的子结构
1 //============================================================================ 2 // Name : JZ-C-18.cpp 3 // Author : Laughing_Lz 4 // Version : 5 // Copyright : All Right Reserved 6 // Description : 树的子结构 7 //============================================================================ 8 9 #include <iostream> 10 #include <stdio.h> 11 #include "BinaryTree.h" 12 using namespace std; 13 14 bool DoesTree(BinaryTreeNode* pRoot, BinaryTreeNode* qRoot); //先函数原型声明 15 16 bool HasSubTree(BinaryTreeNode* pRoot, BinaryTreeNode* qRoot) { 17 bool result = false; 18 if (pRoot != NULL && qRoot != NULL) { 19 if (pRoot->m_nValue == qRoot->m_nValue) { 20 result = DoesTree(pRoot, qRoot); 21 } 22 if (!result) { 23 result = HasSubTree(pRoot->m_pLeft, qRoot); 24 } 25 if (!result) { 26 result = HasSubTree(pRoot->m_pRight, qRoot); 27 } 28 } 29 return result; 30 } 31 bool DoesTree(BinaryTreeNode* pRoot, BinaryTreeNode* qRoot) { 32 if (qRoot == NULL) { 33 return true; 34 } 35 if (pRoot == NULL) { 36 return false; 37 } 38 if (pRoot->m_nValue != qRoot->m_nValue) { 39 return false; 40 } 41 return DoesTree(pRoot->m_pLeft, qRoot->m_pLeft) 42 && DoesTree(pRoot->m_pRight, qRoot->m_pRight); 43 } 44 // ====================测试代码==================== 45 void Test(char* testName, BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2, 46 bool expected) { 47 if (HasSubTree(pRoot1, pRoot2) == expected) 48 printf("%s passed. ", testName); 49 else 50 printf("%s failed. ", testName); 51 } 52 53 // 树中结点含有分叉，树B是树A的子结构 54 // 8 8 55 // / / 56 // 8 7 9 2 57 // / 58 // 9 2 59 // / 60 // 4 7 61 void Test1() { 62 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); 63 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); 64 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7); 65 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9); 66 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(2); 67 BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4); 68 BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7); 69 70 ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); 71 ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5); 72 ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7); 73 74 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); 75 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); 76 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); 77 78 ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3); 79 80 Test("Test1", pNodeA1, pNodeB1, true); 81 82 DestroyTree(pNodeA1); 83 DestroyTree(pNodeB1); 84 } 85 86 // 树中结点含有分叉，树B不是树A的子结构 87 // 8 8 88 // / / 89 // 8 7 9 2 90 // / 91 // 9 3 92 // / 93 // 4 7 94 void Test2() { 95 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); 96 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); 97 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7); 98 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9); 99 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(3); 100 BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4); 101 BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7); 102 103 ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); 104 ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5); 105 ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7); 106 107 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); 108 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); 109 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); 110 111 ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3); 112 113 Test("Test2", pNodeA1, pNodeB1, false); 114 115 DestroyTree(pNodeA1); 116 DestroyTree(pNodeB1); 117 } 118 119 // 树中结点只有左子结点，树B是树A的子结构 120 // 8 8 121 // / / 122 // 8 9 123 // / / 124 // 9 2 125 // / 126 // 2 127 // / 128 // 5 129 void Test3() { 130 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); 131 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); 132 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9); 133 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); 134 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5); 135 136 ConnectTreeNodes(pNodeA1, pNodeA2, NULL); 137 ConnectTreeNodes(pNodeA2, pNodeA3, NULL); 138 ConnectTreeNodes(pNodeA3, pNodeA4, NULL); 139 ConnectTreeNodes(pNodeA4, pNodeA5, NULL); 140 141 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); 142 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); 143 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); 144 145 ConnectTreeNodes(pNodeB1, pNodeB2, NULL); 146 ConnectTreeNodes(pNodeB2, pNodeB3, NULL); 147 148 Test("Test3", pNodeA1, pNodeB1, true); 149 150 DestroyTree(pNodeA1); 151 DestroyTree(pNodeB1); 152 } 153 154 // 树中结点只有左子结点，树B不是树A的子结构 155 // 8 8 156 // / / 157 // 8 9 158 // / / 159 // 9 3 160 // / 161 // 2 162 // / 163 // 5 164 void Test4() { 165 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); 166 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); 167 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9); 168 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); 169 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5); 170 171 ConnectTreeNodes(pNodeA1, pNodeA2, NULL); 172 ConnectTreeNodes(pNodeA2, pNodeA3, NULL); 173 ConnectTreeNodes(pNodeA3, pNodeA4, NULL); 174 ConnectTreeNodes(pNodeA4, pNodeA5, NULL); 175 176 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); 177 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); 178 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3); 179 180 ConnectTreeNodes(pNodeB1, pNodeB2, NULL); 181 ConnectTreeNodes(pNodeB2, pNodeB3, NULL); 182 183 Test("Test4", pNodeA1, pNodeB1, false); 184 185 DestroyTree(pNodeA1); 186 DestroyTree(pNodeB1); 187 } 188 189 // 树中结点只有右子结点，树B是树A的子结构 190 // 8 8 191 // 192 // 8 9 193 // 194 // 9 2 195 // 196 // 2 197 // 198 // 5 199 void Test5() { 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, NULL, pNodeA2); 207 ConnectTreeNodes(pNodeA2, NULL, pNodeA3); 208 ConnectTreeNodes(pNodeA3, NULL, pNodeA4); 209 ConnectTreeNodes(pNodeA4, NULL, pNodeA5); 210 211 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); 212 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); 213 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); 214 215 ConnectTreeNodes(pNodeB1, NULL, pNodeB2); 216 ConnectTreeNodes(pNodeB2, NULL, pNodeB3); 217 218 Test("Test5", pNodeA1, pNodeB1, true); 219 220 DestroyTree(pNodeA1); 221 DestroyTree(pNodeB1); 222 } 223 224 // 树A中结点只有右子结点，树B不是树A的子结构 225 // 8 8 226 // 227 // 8 9 228 // / 229 // 9 3 2 230 // 231 // 2 232 // 233 // 5 234 void Test6() { 235 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); 236 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); 237 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9); 238 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); 239 BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5); 240 241 ConnectTreeNodes(pNodeA1, NULL, pNodeA2); 242 ConnectTreeNodes(pNodeA2, NULL, pNodeA3); 243 ConnectTreeNodes(pNodeA3, NULL, pNodeA4); 244 ConnectTreeNodes(pNodeA4, NULL, pNodeA5); 245 246 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); 247 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); 248 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3); 249 BinaryTreeNode* pNodeB4 = CreateBinaryTreeNode(2); 250 251 ConnectTreeNodes(pNodeB1, NULL, pNodeB2); 252 ConnectTreeNodes(pNodeB2, pNodeB3, pNodeB4); 253 254 Test("Test6", pNodeA1, pNodeB1, false); 255 256 DestroyTree(pNodeA1); 257 DestroyTree(pNodeB1); 258 } 259 260 // 树A为空树 261 void Test7() { 262 BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); 263 BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); 264 BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3); 265 BinaryTreeNode* pNodeB4 = CreateBinaryTreeNode(2); 266 267 ConnectTreeNodes(pNodeB1, NULL, pNodeB2); 268 ConnectTreeNodes(pNodeB2, pNodeB3, pNodeB4); 269 270 Test("Test7", NULL, pNodeB1, false); 271 272 DestroyTree(pNodeB1); 273 } 274 275 // 树B为空树 276 void Test8() { 277 BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); 278 BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(9); 279 BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(3); 280 BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); 281 282 ConnectTreeNodes(pNodeA1, NULL, pNodeA2); 283 ConnectTreeNodes(pNodeA2, pNodeA3, pNodeA4); 284 285 Test("Test8", pNodeA1, NULL, false); 286 287 DestroyTree(pNodeA1); 288 } 289 290 // 树A和树B都为空 291 void Test9() { 292 Test("Test9", NULL, NULL, false); 293 } 294 295 int main(int argc, char** argv) { 296 Test1(); 297 Test2(); 298 Test3(); 299 Test4(); 300 Test5(); 301 Test6(); 302 Test7(); 303 Test8(); 304 Test9(); 305 return 0; 306 }