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

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

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

  [題目分析]二叉樹順序存儲是按完全二叉樹的格式存儲利用完全二叉樹雙親結點與子女結點編號間的關系求下標為i和j的兩結點的雙親雙親的雙親等等直至找到最近的公共祖先

  void Ancestor(ElemType A[]int nij)
  //二叉樹順序存儲在數組A[n]中本算法求下標分別為i和j的結點的最近公共祖先結點的值
  {while(i!=j)
  if(i>j) i=i/;      //下標為i的結點的雙親結點的下標
  else j=j/;         //下標為j的結點的雙親結點的下標
  printf(所查結點的最近公共祖先的下標是%d值是%diA[i]);//設元素類型整型
  }// Ancestor

  [題目分析]用二叉樹表示出父子夫妻和兄弟三種關系可以用根結點表示父(祖先)根結點的左子女表示妻妻的右子女表示子這種二叉樹可以看成類似樹的孩子兄弟鏈表表示法根結點是父根無右子女左子女表示妻妻的右子女(右子女的右子女等)均可看成兄弟(即父的所有兒子)兄弟結點又成為新的父其左子女是兄弟(父的兒子)妻妻的右子女(右子女的右子女等)又為兒子的兒子等等首先遞歸查找某父親結點若查找成功則其左子女是妻妻的右子女及右子女的右子女等均為父親的兒子

  BiTree Search(BiTree tElemType father)//在二叉樹上查找值為father的結點
  {if(t==null) return (null);            //二叉樹上無father結點
  else if(t>data==father) return(t);   //查找成功
  p=Search(t>lchildfather); p=Search(t>rchildfather); }
  }//結束Search
  void PrintSons(BiTree tElemType p)  //在二叉樹上查找結點值為p的所有的兒子
  {p=Serach(tp);                     //在二叉樹t上查找父結點p
  if(p!=null)                        //存在父結點
  {q=p>lchild; q=q>rchild;       //先指向其妻結點再找到第一個兒子
  while(q!=null) {printf(q>data); q=q>rchild;} //輸出父的所有兒子
  }
  }//結束PrintSons

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


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