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

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

2013-11-15 15:38:11  來源: 數據結構 

  .int Count (BiTree  bt) // 非遞歸遍歷求二叉樹上的葉子結點個數
  {int num=;
  BiTree s[]; //s是棧棧中元素是二叉樹結點指針棧容量足夠大
  whlie(bt!=null || top>)
  {while(bt!=null) {push(sbt)bt=bt>lchild}  //沿左分支向下
  if(!StackEmpty(s))
  {bt=pop(s)if(bt>lchild==null && bt>rchild==null) num++//葉子結點
  bt=bt>rchild
  }
  } return(num);
  }//結束Count

  [題目分析]對二叉樹的某層上的結點進行運算采用隊列結構按層次遍歷最適宜

  int LeafKlevel(BiTree bt int k) //求二叉樹bt 的第k(k>) 層上葉子結點個數
  {if(bt==null || k<) return();
  BiTree p=btQ[];            //Q是隊列元素是二叉樹結點指針容量足夠大
  int front=rear=leaf=;  //front 和rear是隊頭和隊尾指針 leaf是葉子結點數
  int last=level=; Q[]=p; //last是二叉樹同層最右結點的指針level 是二叉樹的層數
  while(front<=rear)
  {p=Q[++front];
  if(level==k && !p>lchild && !p>rchild) leaf++; //葉子結點
  if(p>lchild) Q[++rear]=p>lchild;                //左子女入隊
  if(p>rchild) Q[++rear]=p>rchild;               //右子女入隊
  if(front==last) {level++;       //二叉樹同層最右結點已處理層數增
  last=rear; }   //last移到指向下層最右一元素
  if(level>k) return (leaf);               //層數大於k 後退出運行
  }//while  }//結束LeafKLevel

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


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