数据结构与算法中二叉树子结构的详解

什么是二叉树子结构

二叉树是一种数据结构，由包含根节点的节点组成，可以拓展为左子树和右子树。二叉树子结构指的是，在一棵二叉树中，具有连续节点的子树。

如何判断是否为二叉树子结构

对于一棵二叉树T和另外一棵二叉树S，我们可以判断S是否为T的子树，遵循以下判断原则：

1. 如果树S为空，则表示S不是T的子树；
2. 如果树S的根节点和树T的根节点的值相同，则需要判断两者左右子节点是否相同；
3. 如果树S的根节点和树T的根节点的值不相同，则需要分别判断S是否为T的左子树或右子树的子结构。

如下为判断二叉树子结构的代码示例：

bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
    bool result = false;

    if (pRoot1 != nullptr && pRoot2 != nullptr)
    {
        if (Equal(pRoot1->m_value, pRoot2->m_value))
        {
            result = DoesTree1HaveTree2(pRoot1, pRoot2);
        }
        if (!result)
        {
            result = HasSubtree(pRoot1->m_pLeft, pRoot2);
        }
        if (!result)
        {
            result = HasSubtree(pRoot1->m_pRight, pRoot2);
        }
    }

    return result;
}

实例1

下面是一棵二叉树T：

     1
   /   \
  2     3
 /     / \
4     5   6
     /
    7

下面是一棵二叉树S：

   3
 /   \
5     6
 \
  7

我们可以用刚才提到的代码判断树S是否为树T的子树。具体步骤如下：

1. 比较树T根节点的值1和树S根节点的值3，不相等，则继续下一步；
2. 比较树T左子树的根节点的值2和树S的根节点的值3，不相等，则继续下一步；
3. 比较树T左子树的左子树的根节点的值4和树S的根节的节点值3，不相等，则继续下一步；
4. 比较树T右子树的根节点的值3和树S的根节点的值3，相等，则判断左右子节点是否相等；
5. 比较树T右子树的左子节点的值5和树S的左子节点的值5，相等，则继续下一步；
6. 比较树T右子树的右子节点的值6和树S的右子节点的值6，相等，则继续下一步；
7. 经过以上判断，得出结论，树S为树T的子树。

实例2

下面是一棵二叉树T：

     8
   /   \
  6     10
 / \   / \
5   7 9   11

下面是一棵二叉树S：

  10
 / \
9   11

我们同样可以用刚才提到的代码判断树S是否为树T的子树。具体步骤如下：

1. 比较树T根节点的值8和树S根节点的值10，不相等，则继续下一步；
2. 比较树T右子树的根节点的值10和树S的根节点的值10，相等，则继续下一步；
3. 比较树T右子树的左子节点的值9和树S的左子节点的值9，相等，则继续下一步；
4. 比较树T右子树的右子节点的值11和树S的右子节点的值11，相等，则判断左右子节点是否相等；
5. 经过以上判断，得出结论，树S为树T的子树。

总结

以上就是判断二叉树子结构的详细攻略。要注意的是，在判断子树相等时，需要遍历整颗树每一个节点的值进行比较，这个过程需要用到递归。判断树S是否为树T的子树，通常会考虑遍历树T的每个节点，找到跟S树根节点一样的节点进行判断。判断subtree是基础中的基础，大多数二叉树的问题都离不开这个。