《剑指offer》第二十六题（树的子结构）

时间：2022-02-01 17:04:41
// 面试题26：树的子结构

// 题目：输入两棵二叉树A和B，判断B是不是A的子结构。

#include <iostream>

struct BinaryTreeNode

{

    double                 m_dbValue;

    BinaryTreeNode*        m_pLeft;

    BinaryTreeNode*        m_pRight;

};

bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2);

bool Equal(double num1, double num2);

bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)//遍历树1，看看有没有树2的头结点

{

    bool result = false;

    if (pRoot1 != nullptr && pRoot2 != nullptr)//对于树结构，时刻判断节点为空的情况

    {

        if (Equal(pRoot1->m_dbValue, pRoot2->m_dbValue))//注意该题树结构中值的类型是double，不能用==

            result = DoesTree1HaveTree2(pRoot1, pRoot2);//如果头结点一样，就看看是否真的包含

        if (!result)

            result = HasSubtree(pRoot1->m_pLeft, pRoot2);//如果头结点不一样，就开始遍历全树

        if (!result)

            result = HasSubtree(pRoot1->m_pRight, pRoot2);

    }

    return result;

}

bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)

{

    if (pRoot2 == nullptr)//如果这个节点为空代表什么，把树2熬到头就赢了

        return true;

    if (pRoot1 == nullptr)//如果这个节点为空代表什么，完了，树1先熬到头了

        return false;

    if (!Equal(pRoot1->m_dbValue, pRoot2->m_dbValue))//都在啊，那等不等啊

        return false;

    return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&

        DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);//相等，那就递归的检测

}

bool Equal(double num1, double num2)

{

    if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))

        return true;

    else

        return false;

}

// ====================辅助测试代码====================

BinaryTreeNode* CreateBinaryTreeNode(double dbValue)

{

    BinaryTreeNode* pNode = new BinaryTreeNode();

    pNode->m_dbValue = dbValue;

    pNode->m_pLeft = nullptr;

    pNode->m_pRight = nullptr;

    return pNode;

}

void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)

{

    if (pParent != nullptr)

    {

        pParent->m_pLeft = pLeft;//这个时候不用说pLeft为不为空了，为空又怎样

        pParent->m_pRight = pRight;

    }

}

void DestroyTree(BinaryTreeNode* pRoot)

{

    if (pRoot != nullptr)

    {

        BinaryTreeNode* pLeft = pRoot->m_pLeft;

        BinaryTreeNode* pRight = pRoot->m_pRight;

        delete pRoot;

        pRoot = nullptr;

        DestroyTree(pLeft);

        DestroyTree(pRight);

    }

}

// ====================测试代码====================

void Test(const char* testName, BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2, bool expected)

{

    if (HasSubtree(pRoot1, pRoot2) == expected)

        printf("%s passed.\n", testName);

    else

        printf("%s failed.\n", testName);

}

//去吧，把能想到全想到

// 树中结点含有分叉，树B是树A的子结构

//                  8                8

//              /       \           / \

//             8         7         9   2

//           /   \

//          9     2

//               / \

//              4   7

void Test1()

{

    BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);

    ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);

    ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);

    BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);

    Test("Test1", pNodeA1, pNodeB1, true);

    DestroyTree(pNodeA1);

    DestroyTree(pNodeB1);

}

// 树中结点含有分叉，树B不是树A的子结构

//                  8                8

//              /       \           / \

//             8         7         9   2

//           /   \

//          9     3

//               / \

//              4   7

void Test2()

{

    BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);

    ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);

    ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);

    BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);

    Test("Test2", pNodeA1, pNodeB1, false);

    DestroyTree(pNodeA1);

    DestroyTree(pNodeB1);

}

// 树中结点只有左子结点，树B是树A的子结构

//                8                  8

//              /                   /

//             8                   9

//           /                    /

//          9                    2

//         /

//        2

//       /

//

void Test3()

{

    BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeA1, pNodeA2, nullptr);

    ConnectTreeNodes(pNodeA2, pNodeA3, nullptr);

    ConnectTreeNodes(pNodeA3, pNodeA4, nullptr);

    ConnectTreeNodes(pNodeA4, pNodeA5, nullptr);

    BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeB1, pNodeB2, nullptr);

    ConnectTreeNodes(pNodeB2, pNodeB3, nullptr);

    Test("Test3", pNodeA1, pNodeB1, true);

    DestroyTree(pNodeA1);

    DestroyTree(pNodeB1);

}

// 树中结点只有左子结点，树B不是树A的子结构

//                8                  8

//              /                   /

//             8                   9

//           /                    /

//          9                    3

//         /

//        2

//       /

//

void Test4()

{

    BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeA1, pNodeA2, nullptr);

    ConnectTreeNodes(pNodeA2, pNodeA3, nullptr);

    ConnectTreeNodes(pNodeA3, pNodeA4, nullptr);

    ConnectTreeNodes(pNodeA4, pNodeA5, nullptr);

    BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeB1, pNodeB2, nullptr);

    ConnectTreeNodes(pNodeB2, pNodeB3, nullptr);

    Test("Test4", pNodeA1, pNodeB1, false);

    DestroyTree(pNodeA1);

    DestroyTree(pNodeB1);

}

// 树中结点只有右子结点，树B是树A的子结构

//       8                   8

//        \                   \

//         8                   9

//          \                   \

//           9                   2

//            \

//             2

//              \

//               5

void Test5()

{

    BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeA1, nullptr, pNodeA2);

    ConnectTreeNodes(pNodeA2, nullptr, pNodeA3);

    ConnectTreeNodes(pNodeA3, nullptr, pNodeA4);

    ConnectTreeNodes(pNodeA4, nullptr, pNodeA5);

    BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeB1, nullptr, pNodeB2);

    ConnectTreeNodes(pNodeB2, nullptr, pNodeB3);

    Test("Test5", pNodeA1, pNodeB1, true);

    DestroyTree(pNodeA1);

    DestroyTree(pNodeB1);

}

// 树A中结点只有右子结点，树B不是树A的子结构

//       8                   8

//        \                   \

//         8                   9

//          \                 / \

//           9               3   2

//            \

//             2

//              \

//               5

void Test6()

{

    BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeA1, nullptr, pNodeA2);

    ConnectTreeNodes(pNodeA2, nullptr, pNodeA3);

    ConnectTreeNodes(pNodeA3, nullptr, pNodeA4);

    ConnectTreeNodes(pNodeA4, nullptr, pNodeA5);

    BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB4 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeB1, nullptr, pNodeB2);

    ConnectTreeNodes(pNodeB2, pNodeB3, pNodeB4);

    Test("Test6", pNodeA1, pNodeB1, false);

    DestroyTree(pNodeA1);

    DestroyTree(pNodeB1);

}

// 树A为空树

void Test7()

{

    BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeB4 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeB1, nullptr, pNodeB2);

    ConnectTreeNodes(pNodeB2, pNodeB3, pNodeB4);

    Test("Test7", nullptr, pNodeB1, false);

    DestroyTree(pNodeB1);

}

// 树B为空树

void Test8()

{

    BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNodeA1, nullptr, pNodeA2);

    ConnectTreeNodes(pNodeA2, pNodeA3, pNodeA4);

    Test("Test8", pNodeA1, nullptr, false);

    DestroyTree(pNodeA1);

}

// 树A和树B都为空

void Test9()

{

    Test("Test9", nullptr, nullptr, false);

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    Test7();

    Test8();

    Test9();

    system("pause");

    return ;

}

相关文章