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

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

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

  .[題目分析]當森林(樹)以孩子兄弟表示法存儲時若結點沒有孩子(fch=null)則它必是葉子總的葉子結點個數是孩子子樹(fch)上的葉子數和兄弟(nsib)子樹上葉結點個數之和

  typedef  struct  node
  {ElemType  data;//數據域
  struct  node *fch *nsib;//孩子與兄弟域 }*Tree;
  int Leaves (Tree t)
  //計算以孩子兄弟表示法存儲的森林的葉子數
  {if(t)
  if(t>fch==null)               //若結點無孩子則該結點必是葉子
  return(+Leaves(t>nsib));  //返回葉子結點和其兄弟子樹中的葉子結點數
  else return (Leaves(t>fch)+Leaves(t>nsib)); //孩子子樹和兄弟子樹中葉子數之和
  }//結束Leaves

  .[題目分析]由指示結點i 左兒子和右兒子的兩個一維數組L[i]和R[i]很容易建立指示結點i 的雙親的一維數組T[i]根據T數組判斷結點U是否是結點V後代的算法轉為判斷結點V是否是結點U的祖先的問題

  int Generation (int UVNL[]R[]T[])
  //L[]和R[]是含有N個元素且指示二叉樹結點i左兒子和右兒子的一維數組
  //本算法據此建立結點i的雙親數組T並判斷結點U是否是結點V的後代
  {for(i=;i<=N;i++)  T[i]=;  //T數組初始化
  for (i=;i<=N;i++)          //根據L和R填寫T
  if(L[i]!=) T[L[i]]=i;     //若結點i的左子女是L則結點L的雙親是結點i
  for(i=;i<=N;i++)
  if (R[i]!=) T[R[i]]=i;   //i的右子女是r則r的雙親是i
  int parent=U;               //判斷U是否是V的後代
  while (parent!=V && parent!=) parent=T[parent];
  if (parent==V){printf(結點U是結點V的後代);return();}
  else{ printf(結點U不是結點V 的後代);return();}
  }結束Generation

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


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