题目18 树的子结构

野性酷女 2021-11-02 01:02 240阅读 0赞

/  
// 8. 题目18 树的子结构  
// 输入两颗二叉树A和B,判断B是不是A的子结构

template<typename TYPE>
    struct BinaryTreeNode
    {
        TYPE m_stValue;
        BinaryTreeNode* m_pLeftNode;
        BinaryTreeNode* m_pRightNode;
    
        BinaryTreeNode(TYPE stValue, const BinaryTreeNode* pLeftNode = NULL, BinaryTreeNode* pRightNode = NULL)
            :m_stValue(stValue), m_pLeftNode(pLeftNode), m_pRightNode(pRightNode)
        {
    
        }
    };
    
    bool DoesTree1HaveTree2(BinaryTreeNode<int>* pRoot1, BinaryTreeNode<int>* pRoot2)
    {
        if (NULL == pRoot1)
        {
            return false;
        }
    
        if (NULL == pRoot2)
        {
            return true;
        }
    
        if (pRoot1->m_stValue != pRoot2->m_stValue)
        {
            return false;
        }
    
        return DoesTree1HaveTree2(pRoot1->m_pLeftNode, pRoot2->m_pLeftNode) && DoesTree1HaveTree2(pRoot1->m_pRightNode, pRoot2->m_pRightNode);
    }
    
    bool HasSubTree(BinaryTreeNode<int>* pRoot1, BinaryTreeNode<int>* pRoot2)
    {
        bool bHave = false;
    
        while (pRoot1 && pRoot2)
        {
            if (pRoot1->m_stValue == pRoot2->m_stValue)
            {
                bHave = DoesTree1HaveTree2(pRoot1, pRoot2);
            }
    
            // 如果当前节点不相等，继续取左子树或右子树继续比较
            if (!bHave)
            {
                bHave = HasSubTree(pRoot1->m_pLeftNode, pRoot2);
            }
    
            if (!bHave)
            {
                bHave = HasSubTree(pRoot1->m_pRightNode, pRoot2);
            }
        }
    
        return bHave;
    }
    
    void SubStructureInTreeTestFunc()
    {
        cout << "\n\n --------------- SubStructureInTreeTestFunc Start -------------->" << endl;
        int aiArray[] = {
        8, 8, 7, 9, 2, 4, 7};
        int aiSubArray[] = {
        8, 9, 2};
        int iLen = sizeof(aiArray) / sizeof(int);
        int iSubLen = sizeof(aiSubArray) / sizeof(int);
    
    
        CBinarySearchTree<int>* pTreeA = new CBinarySearchTree<int>();
        if (NULL == pTreeA)
        {
            return;
        }
    
        CBinarySearchTree<int>* pTreeB = new CBinarySearchTree<int>();
        if (NULL == pTreeB)
        {
            SAVE_DELETE(pTreeA);
            return;
        }
    
    
        // 释放内存
        SAVE_DELETE(pTreeA);
        SAVE_DELETE(pTreeB);
    
        cout << "\n\n --------------- SubStructureInTreeTestFunc End -------------->" << endl;
    
    }

转载于:https://www.cnblogs.com/yzdai/p/11258709.html