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:"<
      
       m_Value<
       
        m_pLeft!=nullptr) 39             cout<<"value of its left child is:"<
        
         m_pLeft->m_Value<
         
          m_pRight!=nullptr) 43             cout<<"value of its right child is:"<
          
           m_pRight->m_Value<
           
            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 else100 {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.\n", testName);  8     else  9         printf("%s failed.\n", 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                  8118 //              /                   /119 //             8                   9120 //           /                    /121 //          9                    3122 //         /123 //        2124 //       /125 //      5126 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                   8154 //        \                   \155 //         8                   9156 //          \                   \157 //           9                   2158 //            \159 //             2160 //              \161 //               5162 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                   8190 //        \                   \191 //         8                   9192 //          \                 / \193 //           9               3   2194 //            \195 //             2196 //              \197 //               5198 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 }