欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間：2015年08月11日 15:42:14   作者：zinss26914  
這篇文章主要介紹了用C語(yǔ)言判斷一個(gè)二叉樹(shù)是否為另一個(gè)的子結(jié)構(gòu),是數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)當(dāng)中的基礎(chǔ)知識(shí),需要的朋友可以參考下

1、問(wèn)題描述：

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

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

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

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

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

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

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

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

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

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

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

    題目描述：  
    輸入兩顆二叉樹(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代表將要輸入的二叉樹(shù)A的節(jié)點(diǎn)個(gè)數(shù)（節(jié)點(diǎn)從1開(kāi)始計(jì)數(shù)），m代表將要輸入的二叉樹(shù)B的節(jié)點(diǎn)個(gè)數(shù)（節(jié)點(diǎn)從1開(kāi)始計(jì)數(shù)）。接下來(lái)一行有n個(gè)數(shù)，每個(gè)數(shù)代表A樹(shù)中第i個(gè)元素的數(shù)值，接下來(lái)有n行，第一個(gè)數(shù)Ki代表第i個(gè)節(jié)點(diǎn)的子孩子個(gè)數(shù)，接下來(lái)有Ki個(gè)樹(shù)，代表節(jié)點(diǎn)i子孩子節(jié)點(diǎn)標(biāo)號(hào)。接下來(lái)m+1行，與樹(shù)A描述相同。 
    輸出： 
    對(duì)應(yīng)每個(gè)測(cè)試案例， 
    若B是A的子樹(shù)輸出”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樹(shù)中查找和B樹(shù)根節(jié)點(diǎn)一樣的值，其實(shí)就是樹(shù)的前序遍歷，建議遞歸，方便（ps：非遞歸無(wú)非就是用個(gè)棧存儲(chǔ)結(jié)點(diǎn)而已，沒(méi)什么技術(shù)含量）

  

 /** 
   * 第一步判斷，遍歷A樹(shù)查找是否有等于B樹(shù)根結(jié)點(diǎn)的子樹(shù) 
   */ 
  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)的子樹(shù)是不是與B樹(shù)具有相同的結(jié)點(diǎn)

  /** 
   * 第二步判斷，判斷A樹(shù)是否有B樹(shù)的子結(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> 
   
  // 二叉樹(shù)結(jié)點(diǎn)定義 
  struct btree 
  { 
    int value; 
    int lchild, rchild; 
  }; 
   
  // A樹(shù)和B樹(shù)的最多結(jié)點(diǎn)數(shù) 
  int n, m; 
   
  /** 
   * 第二步判斷，判斷A樹(shù)是否有B樹(shù)的子結(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樹(shù)查找是否有等于B樹(shù)根結(jié)點(diǎn)的子樹(shù) 
   */ 
  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樹(shù)的節(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樹(shù)的節(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樹(shù)是否為A的子樹(shù) 
      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; 
  }

相關(guān)文章

最新評(píng)論