熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第六章 答案 (五)[26]

2013-11-15 15:37:39  來源: 數據結構 

  [題目分析]森林在先根次序遍歷時首先遍歷第一棵子樹的根接著是第一棵子樹的結點之後是第二棵樹……最後一棵樹本題中E[i]是H[i]所指結點的次數次數就是結點的分支個數B而分支數B與樹的結點數N的關系是N=B+(除根結點外任何一個結點都有一個分支所指)所以從E[i]的第一個單元開始將值累加當累加到第i個單元其值正好等於i就是第一棵樹接著用相同方法將其它樹分開進行到第n個單元將所有樹分開例如上面應用題第題()的森林可按本題圖示如下從左往右將次數加到下標(=B+)時正好結束第一棵樹

  void Forest(ElemType H[]int E[]intn)
  // H[i]是森林F在先根次序下結點的地址排列E[i]是H[i]所指結點的次數本算法計算森林
  //F的樹形個數並計算森林F的最後一個樹形的根結點地址
  {int i=sum=j=m=; //sum記一棵樹的分支數j記樹的棵數m記一棵樹的結點數
  int tree[];   //tree記每棵樹先序遍歷最後一個結點在H[i]中的地址
  while (i<=n)  //n是森林中結點個數題目已給出
  {sum+=E[i]; m++;
  if (sum+==m && i<=n) //記樹先序最後結點的地址為下步初始化
  {sum=; m=; tree[++j]=i;}
  i++;
  }//while
  if (j==)return ();    //只有一棵樹時第一個結點是根
  else return(tree[j]+)
  }//forest

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23704.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.