亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

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

1、問題描述：

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

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

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

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

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

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

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

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

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

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

3、習(xí)題實例

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

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

  

 /** 
   * 第一步判斷，遍歷A樹查找是否有等于B樹根結(jié)點的子樹 
   */ 
  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; 
  }

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

  /** 
   * 第二步判斷，判斷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é)點定義 
  struct btree 
  { 
    int value; 
    int lchild, rchild; 
  }; 
   
  // A樹和B樹的最多結(jié)點數(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é)點的子樹 
   */ 
  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é)點值 
      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é)點值 
      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; 
  }

相關(guān)文章

最新評論