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

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

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

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

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

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

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

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

更多內容請看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/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/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++技術專題 數據結構 數據結構教程專題，或