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

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

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

  .[題目分析]二叉樹是遞歸定義的以遞歸方式建立最簡單判定是否是完全二叉樹可以使用隊列在遍歷中利用完全二叉樹若某結點無左子女就不應有右子女的原則進行判斷

  BiTree Creat()       //建立二叉樹的二叉鏈表形式的存儲結構
  {ElemType xBiTree bt;
  scanf(%d&x);  //本題假定結點數據域為整型
  if(x==) bt=null;
  else if(x>)
  {bt=(BiNode *)malloc(sizeof(BiNode));
  bt>data=x; bt>lchild=creat(); bt>rchild=creat();
  }
  else error(輸入錯誤)
  return(bt);
  }//結束 BiTree
  int JudgeComplete(BiTree bt)  //判斷二叉樹是否是完全二叉樹如是返回否則返回
  {int tag=; BiTree p=bt Q[]; // Q是隊列元素是二叉樹結點指針容量足夠大
  if(p==null) return ();
  QueueInit(Q); QueueIn(Qp);  //初始化隊列根結點指針入隊
  while (!QueueEmpty(Q))
  {p=QueueOut(Q);                                //出隊
  if (p>lchild && !tag) QueueIn(Qp>lchild);  //左子女入隊
  else {if (p>lchild) return ;                //前邊已有結點為空本結點不空
  else tag=;                             //首次出現結點為空
  if (p>rchild && !tag) QueueIn(Qp>rchild);  //右子女入隊
  else if (p>rchild) return ; else tag=;
  } //while
  return ;  } //JudgeComplete

  [算法討論]完全二叉樹證明還有其它方法判斷時易犯的錯誤是證明其左子樹和右子數都是完全二叉樹由此推出整棵二叉樹必是完全二叉樹的錯誤結論

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


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