#includestruct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; BinaryTreeNode* createBinaryTreeNode(int value) { BinaryTreeNode* pNewNode = new BinaryTreeNode(); pNewNode->m_nValue = value; pNewNode->m_pLeft = NULL; pNewNode->m_pRight = NULL; return pNewNode; } void connectBinaryTreeNode(BinaryTreeNode* pParent,BinaryTreeNode* pLeftChild, BinaryTreeNode* pRightChild) { if(!pParent) return; pParent->m_pLeft = pLeftChild; pParent->m_pRight = pRightChild; } /* bool hasTheSubTeeWithRoot(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree); //判断pSmallTree是不是pBigTree的子树 bool isSubtreeInBinaryTree(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree) { if(pSmallTree == NULL || pBigTree == NULL) return false; bool result = false; bool result1 = false; bool result2 = false; result = hasTheSubTeeWithRoot(pBigTree,pSmallTree); if(pBigTree->m_pLeft) result1 = isSubtreeInBinaryTree(pBigTree->m_pLeft,pSmallTree); if(pBigTree->m_pRight) result2 = isSubtreeInBinaryTree(pBigTree->m_pRight,pSmallTree); return (result || result1 || result2); } //两棵树已包含根节点为条件，判断是否为子树 bool hasTheSubTeeWithRoot(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree) { if(pSmallTree == NULL) return true; if(pBigTree == NULL) return false; bool result = false; bool result1 = false; bool result2 = false; if(pBigTree->m_nValue == pSmallTree->m_nValue) { result = true; result1 = hasTheSubTeeWithRoot(pBigTree->m_pLeft,pSmallTree->m_pLeft); result2 = hasTheSubTeeWithRoot(pBigTree->m_pRight,pSmallTree->m_pRight); } return result && result1 && result2; } */ //以上注释的代码能实现基本功能，但效率很差,原因是上述方法即使一开始确定 //是子树，也会继续遍历较大树下面的每个节点。 //下面方法可以避免这个问题 bool hasTheSubTeeWithRoot(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree); bool isSubtreeInBinaryTree(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree) { bool result = false; if(pBigTree != NULL && pSmallTree != NULL) { if(pBigTree-> m_nValue == pSmallTree->m_nValue) result = hasTheSubTeeWithRoot(pBigTree,pSmallTree); if(!result) //如果查找出子树就停止往下查找 result = isSubtreeInBinaryTree(pBigTree->m_pLeft,pSmallTree); if(!result) result = isSubtreeInBinaryTree(pBigTree->m_pRight,pSmallTree); } return result; } bool hasTheSubTeeWithRoot(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree) { if(pSmallTree == NULL) return true; if(pBigTree == NULL) return false; if(pBigTree->m_nValue != pSmallTree->m_nValue) return false; //用return语句递归 return hasTheSubTeeWithRoot(pBigTree->m_pLeft,pSmallTree->m_pLeft) && hasTheSubTeeWithRoot(pBigTree->m_pRight,pSmallTree->m_pRight); } //单元测试 void test1() { BinaryTreeNode* pNode1 = createBinaryTreeNode(8); BinaryTreeNode* pNode2 = createBinaryTreeNode(8); BinaryTreeNode* pNode3 = createBinaryTreeNode(7); BinaryTreeNode* pNode4 = createBinaryTreeNode(9); BinaryTreeNode* pNode5 = createBinaryTreeNode(2); BinaryTreeNode* pNode6 = createBinaryTreeNode(4); BinaryTreeNode* pNode7 = createBinaryTreeNode(7); connectBinaryTreeNode(pNode1,pNode2,pNode3); connectBinaryTreeNode(pNode2,pNode4,pNode5); connectBinaryTreeNode(pNode5,pNode6,pNode7); BinaryTree