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

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

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

   void InOrder(BiTree bt)
  {BiTree s[]p=bt;  //s是元素為二叉樹結點指針的棧容量足夠大
  int top=;
  while(p || top>)
  {while(p) {s[++top]=p; bt=p>lchild;}              //中序遍歷左子樹
  if(top>){p=s[top]; printf(p>data); p=p>rchild;} //退棧訪問轉右子樹
  }   }

  [題目分析] 二叉樹用順序方式存儲其遍歷方法與用二叉鏈表方式存儲類似判空時在二叉鏈表方式下用結點指針是否等於null在順序存儲方式下 一是下標是否是虛結點二是下標值是否超過最大值(高為H的二叉樹要有H個存儲單元與實際結點個數關系不大)當然順序存儲方式下要告訴根結點的下標

  void InOrder(int i) //對順序存儲的二叉樹進行中序遍歷i是根結點的下標
  {if(i!=)
  {InOrder(ar[i]Lc);   //中序遍歷左子樹
  printf(ar[i]data);  //訪問根結點
  InOrder(ar[i]Rc);   //中序遍歷左子樹
  }  } // 結束InOrder

  [題目分析] 借助隊列和棧最後彈出棧中元素實現對二叉樹按自下至上自右至左的層次遍歷

  void InvertLevel(biTree bt)  // 對二叉樹按自下至上自右至左的進行層次遍歷
  {if(bt!=null)
  {StackInit(s); //棧初始化棧中存放二叉樹結點的指針
  QueueInit(Q); //隊列初始化隊列中存放二叉樹結點的指針
  QueueIn(Qbt);
  while(!QueueEmpty(Q))                  //從上而下層次遍歷
  {p=QueueOut(Q); push(sp);           //出隊 入棧
  if(p>lchild) QueueIn(Qp>lchild);  //若左子女不空則入隊列
  if(p>rchild) QueueIn(Qp>rchild);} //若右子女不空則入隊列
  while(!StackEmpty(s)) {p=pop(s); printf(p>data);} //自下而上從右到左的層次遍歷
  }//if(bt!=null)
  } //結束InvertLevel

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


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