输入两棵二叉树A和B，判断B是不是A的子结构。
struct BinaryTreeNode
{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; bool Tree1HaveTree2(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2) { if(pRoot2 == NULL) return true; if(pRoot1 == NULL) return false; if(pRoot1->m_nValue != pRoot2->m_nValue) return false; return Tree1HaveTree2( pRoot1->m_pLeft, pRoot2->m_pLeft) && Tree1HaveTree2( pRoot1->m_pRight, pRoot2->m_pRight); } bool HasSubTree(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2) { bool result = false; if(pRoot1 != NULL && pRoot2 != NULL) { if(pRoot1->m_nValue == pRoot2->m_nValue) result = Tree1HaveTree2(pRoot1,pRoot2); if(!result) result = HasSubTree(pRoot1->m_pLeft,pRoot2); if(!result) result = HasSubTree(pRoot1->m_pRight,pRoot2); } return result; } BinaryTreeNode* CreateBinaryTreeNode(int value) { BinaryTreeNode* pNode = new BinaryTreeNode(); pNode->m_nValue = value; pNode->m_pLeft = NULL; pNode->m_pRight = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* parent,BinaryTreeNode* pLeft,BinaryTreeNode*pRight) { if(parent != NULL) { parent->m_pLeft = pLeft; parent->m_pRight = pRight; } } void DestroyTree(BinaryTreeNode* pRoot) { if(pRoot != NULL) { BinaryTreeNode* pLeft = pRoot->m_pLeft; BinaryTreeNode* pRight = pRoot->m_pRight; delete pRoot; pRoot = NULL; DestroyTree(pLeft); DestroyTree(pRight); } } void Test(char* testName, BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2, bool expected) { if(HasSubTree(pRoot1, pRoot2) == expected) printf("%s passed.\n", testName); else printf("%s failed.\n", testName); } void Test1() { BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7); BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(2); BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4); BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7); ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5); ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7); BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3); Test("Test1", pNodeA1, pNodeB1, true); DestroyTree(pNodeA1); DestroyTree(pNodeB1); } void Test2() { BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7); BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(3); BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4); BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7); ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5); ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7); BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3); Test("Test2", pNodeA1, pNodeB1, false); DestroyTree(pNodeA1); DestroyTree(pNodeB1); } void Test3() { BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5); ConnectTreeNodes(pNodeA1, pNodeA2, NULL); ConnectTreeNodes(pNodeA2, pNodeA3, NULL); ConnectTreeNodes(pNodeA3, pNodeA4, NULL); ConnectTreeNodes(pNodeA4, pNodeA5, NULL); BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); ConnectTreeNodes(pNodeB1, pNodeB2, NULL); ConnectTreeNodes(pNodeB2, pNodeB3, NULL); Test("Test3", pNodeA1, pNodeB1, true); DestroyTree(pNodeA1); DestroyTree(pNodeB1); } void Test4() { BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5); ConnectTreeNodes(pNodeA1, pNodeA2, NULL); ConnectTreeNodes(pNodeA2, pNodeA3, NULL); ConnectTreeNodes(pNodeA3, pNodeA4, NULL); ConnectTreeNodes(pNodeA4, pNodeA5, NULL); BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3); ConnectTreeNodes(pNodeB1, pNodeB2, NULL); ConnectTreeNodes(pNodeB2, pNodeB3, NULL); Test("Test4", pNodeA1, pNodeB1, false); DestroyTree(pNodeA1); DestroyTree(pNodeB1); } void Test5() { BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5); ConnectTreeNodes(pNodeA1, NULL, pNodeA2); ConnectTreeNodes(pNodeA2, NULL, pNodeA3); ConnectTreeNodes(pNodeA3, NULL, pNodeA4); ConnectTreeNodes(pNodeA4, NULL, pNodeA5); BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); ConnectTreeNodes(pNodeB1, NULL, pNodeB2); ConnectTreeNodes(pNodeB2, NULL, pNodeB3); Test("Test5", pNodeA1, pNodeB1, true); DestroyTree(pNodeA1); DestroyTree(pNodeB1); } void Test6() { BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(5); ConnectTreeNodes(pNodeA1, NULL, pNodeA2); ConnectTreeNodes(pNodeA2, NULL, pNodeA3); ConnectTreeNodes(pNodeA3, NULL, pNodeA4); ConnectTreeNodes(pNodeA4, NULL, pNodeA5); BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3); BinaryTreeNode* pNodeB4 = CreateBinaryTreeNode(2); ConnectTreeNodes(pNodeB1, NULL, pNodeB2); ConnectTreeNodes(pNodeB2, pNodeB3, pNodeB4); Test("Test6", pNodeA1, pNodeB1, false); DestroyTree(pNodeA1); DestroyTree(pNodeB1); } void Test7() { BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(3); BinaryTreeNode* pNodeB4 = CreateBinaryTreeNode(2); ConnectTreeNodes(pNodeB1, NULL, pNodeB2); ConnectTreeNodes(pNodeB2, pNodeB3, pNodeB4); Test("Test7", NULL, pNodeB1, false); DestroyTree(pNodeB1); } void Test8() { BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(3); BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(2); ConnectTreeNodes(pNodeA1, NULL, pNodeA2); ConnectTreeNodes(pNodeA2, pNodeA3, pNodeA4); Test("Test8", pNodeA1, NULL, false); DestroyTree(pNodeA1); } void Test9() { Test("Test9", NULL, NULL, false); } int main( ) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); Test7(); Test8(); Test9(); return 0; }