用C語(yǔ)言判斷一個(gè)二叉樹是否為另一個(gè)的子結(jié)構(gòu)

來(lái)源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語(yǔ)言|點(diǎn)擊：次

1、問題描述：

如何判斷一個(gè)二叉樹是否是另一個(gè)的子結(jié)構(gòu)？
比如：

        2
      /   \
     9    8
    / \    /
   2 3 5
/
6

有個(gè)子結(jié)構(gòu)是
9
/ \
2 3

2、分析問題：
有關(guān)二叉樹的算法問題，一般都可以通過遞歸來(lái)解決。那么寫成一個(gè)正確的遞歸程序，首先一定要分析正確遞歸結(jié)束的條件。

拿這道題來(lái)講，什么時(shí)候遞歸結(jié)束。

<1>第二個(gè)二叉樹root2為空時(shí)，說明root2是第一棵二叉樹的root1的子結(jié)構(gòu)，返回true。

<2>當(dāng)root1為空時(shí)，此時(shí)root2還沒為空，說明root2不是root1的子結(jié)構(gòu)，返回false。

<3>遞歸下面有兩種思路：

方法一：現(xiàn)在root1中找結(jié)點(diǎn)值與root2的值相等的結(jié)點(diǎn)，如果找到就判斷root2是不是這個(gè)結(jié)點(diǎn)開頭的子結(jié)構(gòu)。所以，首先IsSubTree()判斷。

方法二：就是直接判斷，相同就遞歸判斷root2左右子樹是不是也是相應(yīng)的子結(jié)構(gòu)。如果值不相同，就分別遞歸到root1的左右子樹尋找。尤其要注意最后兩句遞歸的邏輯判斷。

3、習(xí)題實(shí)例

    題目描述：
    輸入兩顆二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。
    輸入：
    輸入可能包含多個(gè)測(cè)試樣例，輸入以EOF結(jié)束。
    對(duì)于每個(gè)測(cè)試案例，輸入的第一行一個(gè)整數(shù)n,m(1<=n<=1000,1<=m<=1000)：n代表將要輸入的二叉樹A的節(jié)點(diǎn)個(gè)數(shù)（節(jié)點(diǎn)從1開始計(jì)數(shù)），m代表將要輸入的二叉樹B的節(jié)點(diǎn)個(gè)數(shù)（節(jié)點(diǎn)從1開始計(jì)數(shù)）。接下來(lái)一行有n個(gè)數(shù)，每個(gè)數(shù)代表A樹中第i個(gè)元素的數(shù)值，接下來(lái)有n行，第一個(gè)數(shù)Ki代表第i個(gè)節(jié)點(diǎn)的子孩子個(gè)數(shù)，接下來(lái)有Ki個(gè)樹，代表節(jié)點(diǎn)i子孩子節(jié)點(diǎn)標(biāo)號(hào)。接下來(lái)m+1行，與樹A描述相同。
    輸出：
    對(duì)應(yīng)每個(gè)測(cè)試案例，
    若B是A的子樹輸出”YES”(不包含引號(hào))。否則，輸出“NO”（不包含引號(hào)）。
    樣例輸入：
    7 3
    8 8 7 9 2 4 7
    2 2 3
    2 4 5
    0
    0
    2 6 7
    0
    0
    8 9 2
    2 2 3
    0
    0

實(shí)現(xiàn)
第一步，在A樹中查找和B樹根節(jié)點(diǎn)一樣的值，其實(shí)就是樹的前序遍歷，建議遞歸，方便（ps：非遞歸無(wú)非就是用個(gè)棧存儲(chǔ)結(jié)點(diǎn)而已，沒什么技術(shù)含量）

 /** 
   * 第一步判斷，遍歷A樹查找是否有等于B樹根結(jié)點(diǎn)的子樹 
   */ 
  int judgeChildTree(struct btree *ahead, int numa, struct btree *bhead, int numb) 
  { 
    int flag = 0; 
   
    if (numa != -1 && numb != -1) { 
      if (ahead[numa].value == bhead[numb].value) 
        flag = doesTree1HasTree2(ahead, numa, bhead, numb); 
   
      if (! flag && ahead[numa].lchild != -1) 
        flag = judgeChildTree(ahead, ahead[numa].lchild, bhead, numb); 
   
      if (! flag && ahead[numa].rchild != -1) 
        flag = judgeChildTree(ahead, ahead[numa].rchild, bhead, numb); 
    } 
   
    return flag; 
  }

第二步，進(jìn)一步判斷A中以R為根節(jié)點(diǎn)的子樹是不是與B樹具有相同的結(jié)點(diǎn)

  /** 
   * 第二步判斷，判斷A樹是否有B樹的子結(jié)構(gòu) 
   */ 
  int doesTree1HasTree2(struct btree *ahead, int numa, struct btree *bhead, int numb) 
  { 
    if (numb == -1)  
      return 1; 
    if (numa == -1) 
      return 0; 
   
    if (ahead[numa].value != bhead[numb].value) 
      return 0; 
   
    return (doesTree1HasTree2(ahead, ahead[numa].lchild, bhead, bhead[numb].lchild) && 
      doesTree1HasTree2(ahead, ahead[numa].rchild, bhead, bhead[numb].rchild)); 
  }

完整代碼

 #include <stdio.h> 
  #include <stdlib.h> 
   
  // 二叉樹結(jié)點(diǎn)定義 
  struct btree 
  { 
    int value; 
    int lchild, rchild; 
  }; 
   
  // A樹和B樹的最多結(jié)點(diǎn)數(shù) 
  int n, m; 
   
  /** 
   * 第二步判斷，判斷A樹是否有B樹的子結(jié)構(gòu) 
   */ 
  int doesTree1HasTree2(struct btree *ahead, int numa, struct btree *bhead, int numb) 
  { 
    if (numb == -1)  
      return 1; 
    if (numa == -1) 
      return 0; 
   
    if (ahead[numa].value != bhead[numb].value) 
      return 0; 
   
    return (doesTree1HasTree2(ahead, ahead[numa].lchild, bhead, bhead[numb].lchild) && 
      doesTree1HasTree2(ahead, ahead[numa].rchild, bhead, bhead[numb].rchild)); 
  } 
   
  /** 
   * 第一步判斷，遍歷A樹查找是否有等于B樹根結(jié)點(diǎn)的子樹 
   */ 
  int judgeChildTree(struct btree *ahead, int numa, struct btree *bhead, int numb) 
  { 
    int flag = 0; 
   
    if (numa != -1 && numb != -1) { 
      if (ahead[numa].value == bhead[numb].value) 
        flag = doesTree1HasTree2(ahead, numa, bhead, numb); 
   
      if (! flag && ahead[numa].lchild != -1) 
        flag = judgeChildTree(ahead, ahead[numa].lchild, bhead, numb); 
   
      if (! flag && ahead[numa].rchild != -1) 
        flag = judgeChildTree(ahead, ahead[numa].rchild, bhead, numb); 
    } 
   
    return flag; 
  } 
   
  int main(void) 
  { 
    int i, data, count, left, right, flag; 
    struct btree *ahead, *bhead; 
   
    while (scanf("%d %d", &n, &m) != EOF) { 
      // 獲取A樹的節(jié)點(diǎn)值 
      ahead = (struct btree *)malloc(sizeof(struct btree) * n); 
      for (i = 0; i < n; i ++) { 
        scanf("%d", &data); 
        ahead[i].value = data; 
        ahead[i].lchild = ahead[i].rchild = -1; 
      } 
   
      for (i = 0; i < n; i ++) { 
        scanf("%d", &count); 
        if (count == 0) { 
          continue; 
        } else { 
          if (count == 1) { 
            scanf("%d", &left); 
            ahead[i].lchild = left - 1; 
          } else { 
            scanf("%d %d", &left, &right); 
            ahead[i].lchild = left - 1; 
            ahead[i].rchild = right - 1; 
          } 
        } 
      } 
   
      // 獲取B樹的節(jié)點(diǎn)值 
      bhead = (struct btree *)malloc(sizeof(struct btree) * m); 
      for (i = 0; i < m; i ++) { 
        scanf("%d", &data); 
        bhead[i].value = data; 
        bhead[i].lchild = bhead[i].rchild = -1; 
      } 
   
      for (i = 0; i < m; i ++) { 
        scanf("%d", &count); 
        if (count == 0) { 
          continue; 
        } else { 
          if (count == 1) { 
            scanf("%d", &left); 
            bhead[i].lchild = left - 1; 
          } else { 
            scanf("%d %d", &left, &right); 
            bhead[i].lchild = left - 1; 
            bhead[i].rchild = right - 1; 
          } 
        } 
      } 
   
      // 判斷B樹是否為A的子樹 
      if (n == 0 || m == 0) { 
        printf("NO\n"); 
        continue; 
      } 
   
      flag = judgeChildTree(ahead, 0, bhead, 0); 
      if (flag) 
        printf("YES\n"); 
      else 
        printf("NO\n"); 
   
      free(ahead); 
      free(bhead); 
    } 
   
    return 0; 
  }

上一篇：詳解C語(yǔ)言中的常量指針和指針常量

欄目：C語(yǔ)言

下一篇：C語(yǔ)言中的sscanf()函數(shù)使用詳解

本文標(biāo)題：用C語(yǔ)言判斷一個(gè)二叉樹是否為另一個(gè)的子結(jié)構(gòu)

本文地址：http://www.jygsgssxh.com/a1/Cyuyan/2882.html

更多C語(yǔ)言

雷火电竞-中国电竞赛事及体育赛事平台

C語(yǔ)言

用C語(yǔ)言判斷一個(gè)二叉樹是否為另一個(gè)的子結(jié)構(gòu)

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機(jī)閱讀