數(shù)據(jù)結(jié)構(gòu)學習C++——樹（總結(jié)）

2019-11-17 05:47:57

字體：大中小

供稿：網(wǎng)友

要害字     數(shù)據(jù)結(jié)構(gòu) C++ 樹

      才剛開了個頭，就要說再見了——在樹這里，除了二叉樹，別的都還沒有講。為什么可以總結(jié)了呢？因為前面已經(jīng)涉及到了樹的兩個基本用途，而假如再講B＋、B－，就不能不提到搜索，假如是勝者樹就不能不提到排序。為此，把這部分放到后面。我前面所做的努力，只是讓你有個基本概念，什么時候記得用樹。

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

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

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

      就像哲學界到現(xiàn)在還糾纏于物質(zhì)和精神本源問題，實際上在樹這里也是如此。有些情況下，并不能區(qū)分是做為儲存來用還是做為判定來用，比如搜索樹，既儲存了數(shù)據(jù)，還蘊涵著判定。

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

      最后，附帶一個求N皇后的全部解的程序。
#include
#define N 8
int layout[N];//布局
int key = 0;
int judge(int row, int col)//判定能否在（row，col）放下
{
       int i;
       for (i = 0; i < row; i++)
       {
              if (layout[i] == col) return 0;//同一列
              if (i - layout[i] == row - col) return 0;//同一條主對角線
              if (i + layout[i] == row + col) return 0;//同一條副對角線
       }
       return 1;
}

void lay(int row)//在row行上放Queen
{
       int i;
       if (row == N)//放完N個Queen輸出布局
       {
                            for (i = 0; i < N; i++) printf("%c%d ", layout[i] + 'a', i + 1);
       }
       else
       {
              for (i = 0; i < N; i++)//在i列上放Queen
              {
                     layout[row] = i;
                     if (judge(row, i)) lay(row + 1);
              }
       }
}

int main()
{
       lay(0);
       return 0;
}