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

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

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

  [題目分析]二叉樹采用順序存儲結構(一維數組)是按完全二叉樹的形狀存儲的不是完全二叉樹的二叉樹順序存儲時要加虛結點數組中的第一個元素是根結點本題中采用隊列結構

  typedef struct
  {BiTree bt;        //二叉樹結點指針
  int num; }tnode   // num是結點在一維數組中的編號
  tnode  Q[maxsize];   //循環隊列容量足夠大
  void  creat(BiTree TElemType BT[ ])
  //深度h的二叉樹存於一維數組BT[:h]中本算法生成該二叉樹的二叉鏈表存儲結構
  {tnode tq;        //tq是隊列元素
  int len=h;    //數組長度
  T=(BiTree)malloc(sizeof(BiNode)); //申請結點
  T>data=BT[];                    //根結點數據
  tqbt=T; tqnum=;
  Q[]=tq;                 //根入隊列
  front=;rear=;          //循環隊列頭尾指針
  while(front!=rear)       //當隊列不空時循環
  {front=(front+) % maxsize ;
  tq=Q[front] ; p=tqbt; i=tqnum ;             //出隊取出結點及編號
  if (BT[*i]==#||*i>len) p>lchild=null;  //左子樹為空#表示虛結點
  else   //建立左子女結點並入隊列
  {p>lchild=(BiTree) malloc(sizeof(BiNode)); //申請結點空間
  p>lchilddata=BT[*i];                    // 左子女數據
  tqbt=p>lchild; tqnum=*i; rear=(rear+) % maxsize ;//計算隊尾位置
  Q[rear]=tq;            //左子女結點及其編號入隊
  }
  if(BT[*i+]==#|| *i+>len) p>rchild=null; //右子樹為空
  else    //建立右子女結點並入隊列
  {p>rchild=(BiTree)malloc(sizeof (BiNode); //申請結點空間
  p>rchild>data=BT[*i+]; tqbt=p>rchild; tqnum=*i+;
  rear=(rear+)%maxsize; Q[rear]=tq;  //計算隊尾位置右子女及其編號入隊
  }
  } //while
  }//結束creat

  [算法討論] 本題中的虛結點用#表示應根據二叉樹的結點數據的類型而定

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


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