| 導購 | 订阅 | 在线投稿
分享
 
 
 

C++數據結構學習:二叉樹(4)

來源:互聯網  2008-06-01 02:05:23  評論

才剛開了個頭,就要說再見了——在樹這裏,除了二叉樹,別的都還沒有講。爲什麽可以總結了呢?因爲前面已經涉及到了樹的兩個基本用途,而假如再講B+、B-,就不能不提到搜索,假如是勝者樹就不能不提到排序。爲此,把這部分放到後面。

我前面所做的努力,只是讓你有個基本概念,什麽時候記得用樹。

樹的兩個基本用途,可以用物質和精神來比喻。

一個用途是做爲數據儲存,儲存具有樹結構的數據——目錄、族譜等等。爲了在實際上是線性的儲存載體上(內存、磁盤)儲存非線性的樹結構,必須有標志指示出樹的結構。因此,只要能區分根和子樹,樹可以采取各種方法來儲存——多叉鏈表、左子女-右兄弟二叉鏈表、廣義表、多維數組。由于操作的需求,儲存方法並不是隨意選取的。比如,在並查集的實現上,選取的是雙親鏈表。

一個用途是做爲邏輯判定,此時會經常聽到一個名詞——判定樹。最常用的結構是二叉樹,一個孩子代表true,一個孩子代表false。關于多叉判定樹,有個例子是求8皇後的全部解——這個連高斯都算錯了(一共是92組解,高斯最開始說76組解),我們比不上高斯,但是我們會讓computer代勞。

就像哲學界到現在還糾纏于物質和精神本源問題,實際上在樹這裏也是如此。有些情況下,並不能區分是做爲儲存來用還是做爲判定來用,比如搜索樹,既儲存了數據,還蘊涵著判定。

和後面的圖相比,樹更基本,也更常用。你可以不知道最短路徑怎麽求,卻每時每刻都在和樹打交道——看看你電腦裏的文件夾吧。

C++數據結構學習:二叉樹(4)
更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或

最後,附帶一個求N皇後的全部解的程序。

#include

#defineN8

intlayout[N];//布局

intkey=0;

intjudge(introw,intcol)//判定能否在(row,col)放下

{

inti;

for(i=0;i

{

if(layout[i]==col)return0;//同一列

if(i-layout[i]==row-col)return0;//同一條主對角線

if(i+layout[i]==row+col)return0;//同一條副對角線

}

C++數據結構學習:二叉樹(4)
更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或 return1;

}

voidlay(introw)//在row行上放Queen

{

inti;

if(row==N)//放完N個Queen輸出布局

{

PRintf("\n%02d",++key);

for(i=0;i

}

else

{

for(i=0;i

{

layout[row]=i;

if(judge(row,i))lay(row+1);

}

}

}

intmain()

{

lay(0);

return0;

}


C++數據結構學習:二叉樹(4)
更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或

  才剛開了個頭,就要說再見了——在樹這裏,除了二叉樹,別的都還沒有講。爲什麽可以總結了呢?因爲前面已經涉及到了樹的兩個基本用途,而假如再講B+、B-,就不能不提到搜索,假如是勝者樹就不能不提到排序。爲此,把這部分放到後面。 我前面所做的努力,只是讓你有個基本概念,什麽時候記得用樹。   樹的兩個基本用途,可以用物質和精神來比喻。      一個用途是做爲數據儲存,儲存具有樹結構的數據——目錄、族譜等等。爲了在實際上是線性的儲存載體上(內存、磁盤)儲存非線性的樹結構,必須有標志指示出樹的結構。因此,只要能區分根和子樹,樹可以采取各種方法來儲存——多叉鏈表、左子女-右兄弟二叉鏈表、廣義表、多維數組。由于操作的需求,儲存方法並不是隨意選取的。比如,在並查集的實現上,選取的是雙親鏈表。      一個用途是做爲邏輯判定,此時會經常聽到一個名詞——判定樹。最常用的結構是二叉樹,一個孩子代表true,一個孩子代表false。關于多叉判定樹,有個例子是求8皇後的全部解——這個連高斯都算錯了(一共是92組解,高斯最開始說76組解),我們比不上高斯,但是我們會讓computer代勞。      就像哲學界到現在還糾纏于物質和精神本源問題,實際上在樹這裏也是如此。有些情況下,並不能區分是做爲儲存來用還是做爲判定來用,比如搜索樹,既儲存了數據,還蘊涵著判定。      和後面的圖相比,樹更基本,也更常用。你可以不知道最短路徑怎麽求,卻每時每刻都在和樹打交道——看看你電腦裏的文件夾吧。 [url=/bbs/detail_1785350.html][img]http://image.wangchao.net.cn/it/1323423807411.gif[/img][/url] 更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或   最後,附帶一個求N皇後的全部解的程序。      #include      #defineN8      intlayout[N];//布局      intkey=0;      intjudge(introw,intcol)//判定能否在(row,col)放下   {      inti;      for(i=0;i      {   if(layout[i]==col)return0;//同一列        if(i-layout[i]==row-col)return0;//同一條主對角線      if(i+layout[i]==row+col)return0;//同一條副對角線      }              [url=/bbs/detail_1785350.html][img]http://image.wangchao.net.cn/it/1323423807432.gif[/img][/url] 更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或   return1;      }      voidlay(introw)//在row行上放Queen      {      inti;        if(row==N)//放完N個Queen輸出布局        {        PRintf("\n%02d",++key);      for(i=0;i      }      else      {      for(i=0;i      {      layout[row]=i;      if(judge(row,i))lay(row+1);      }      }      }      intmain()        {      lay(0);   return0;      }              [url=/bbs/detail_1785350.html][img]http://image.wangchao.net.cn/it/1323423807458.gif[/img][/url] 更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有