數的子結構，子結構

數的子結構，子結構

題目：輸入兩棵二叉樹A和B，判斷B是不是A的子結構。

二叉樹結點的定義如下：

struct BinaryTreeNode
{
    int             m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
};

分析:采用遞歸，先找到值相同的結點，再判斷是否相同。

  1 #include<stdio.h>
  2 
  3 struct BinaryTreeNode
  4 {
  5     int              m_nValue;
  6     BinaryTreeNode*  m_pLeft;
  7     BinaryTreeNode*  m_pRight;
  8 };
  9 
 10 BinaryTreeNode* CreateBinaryTreeNode(int value)
 11 {
 12     BinaryTreeNode* pNode = new BinaryTreeNode();
 13     pNode->m_nValue = value;
 14     pNode->m_pLeft = NULL;
 15     pNode->m_pRight = NULL;
 16 }
 17 
 18 void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, 
 19                     BinaryTreeNode* pRight)
 20 {
 21     if(pParent != NULL)
 22     {
 23         pParent->m_pLeft = pLeft;
 24         pParent->m_pRight = pRight;
 25     }
 26 }
 27 
 28 void DestroyTree(BinaryTreeNode* pRoot)
 29 {
 30     if(pRoot != NULL)
 31     {
 32         BinaryTreeNode* pLeft = pRoot->m_pLeft;
 33         BinaryTreeNode* pRight = pRoot->m_pRight;
 34         
 35         delete pRoot;
 36         pRoot = NULL;
 37         
 38         DestroyTree(pLeft);
 39         DestroyTree(pRight);
 40     }
 41 }
 42 
 43 bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2);
 44 
 45 bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
 46 {
 47     bool result = false;
 48     
 49     if(pRoot1 != NULL && pRoot2 != NULL)
 50     {
 51         if(pRoot1->m_nValue == pRoot2->m_nValue)
 52             result = DoesTree1HaveTree2(pRoot1, pRoot2);
 53         if(!result)
 54             result = HasSubtree(pRoot1->m_pLeft, pRoot2);
 55         if(!result)
 56             result = HasSubtree(pRoot1->m_pRight, pRoot2);
 57     }
 58     
 59     return result;
 60 }
 61 
 62 bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
 63 {
 64     //如果pRoot2 == NULL 說明樹B已經到達葉子結點了
 65     //無論pRoot1是否到達一個葉子結點，都應該返回真 
 66     if(pRoot2 == NULL)
 67         return true;
 68     
 69     //如果程序執行到這裡，則pRoot2一定不是NULL，
 70     //如果pRoot1 == NULL, 則說明樹A不包含樹B 
 71     if(pRoot1 == NULL)
 72         return false;
 73     
 74     if(pRoot1->m_nValue != pRoot2->m_nValue)
 75         return false;
 76         
 77     return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) && 
 78         DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
 79     
 80 }
 81 
 82 //         樹A              樹B 
 83 //          8               8
 84 //       /   \            /  \
 85 //     8      7          9    2
 86 //    /  \     
 87 //   9    2  
 88 //      /  \
 89 //     4    7
 90 //樹B是樹A的子樹 
 91 
 92 int main()
 93 {
 94     BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8);
 95     BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8);
 96     BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7);
 97     BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9);
 98     BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(2);
 99     BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4);
100     BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7);
101     
102     ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
103     ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
104     ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);
105     
106     BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8);
107     BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9);
108     BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2);
109     
110     ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);
111     
112     if(HasSubtree(pNodeA1, pNodeB1))
113         printf("tree B is Subtree of tree A\n");
114     else
115         printf("tree B is't Subtree of tree A\n");
116     
117     DestroyTree(pNodeA1);
118     DestroyTree(pNodeB1);
119 }