数据结构学习C++——树（总结）

核心提示： 要害字 数据结构 C++ 树 才刚开了个头，就要说再见了——在树这里，数据结构学习C++——树（总结），除了二叉树，别的都还没有讲，最后，附带一个求N皇后的全部解的程序，为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而假如再讲B＋、B－

　　　 
要害字　　 数据结构 C++ 树 
　
　　　才刚开了个头，就要说再见了——在树这里，除了二叉树，别的都还没有讲。为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而假如再讲B＋、B－，就不能不提到搜索，假如是胜者树就不能不提到排序。为此，把这部分放到后面。我前面所做的努力，只是让你有个基本概念，什么时候记得用树。

树的两个基本用途，可以用物质和精神来比喻。

　　　一个用途是做为数据储存，储存具有树结构的数据——目录、族谱等等。为了在实际上是线性的储存载体上（内存、磁盘）储存非线性的树结构，必须有标志指示出树的结构。因此，只要能区分根和子树，树可以采取各种方法来储存——多叉链表、左子女－右兄弟二叉链表、广义表、多维数组。由于操作的需求，储存方法并不是随意选取的。比如，在并查集的实现上，选取的是双亲链表。

　　　一个用途是做为逻辑判定，此时会经常听到一个名词——判定树。最常用的结构是二叉树，一个孩子代表true，一个孩子代表false。关于多叉判定树，有个例子是求8皇后的全部解——这个连高斯都算错了（一共是92组解，高斯最开始说76组解），我们比不上高斯，但是我们会让computer代劳。

　　　就像哲学界到现在还纠缠于物质和精神本源问题，实际上在树这里也是如此。有些情况下，并不能区分是做为储存来用还是做为判定来用，比如搜索树，既储存了数据，还蕴涵着判定。

　　　和后面的图相比，树更基本，也更常用。你可以不知道最短路径怎么求，却每时每刻都在和树打交道——看看你电脑里的文件夹吧。

　　　最后，附带一个求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输出布局
　　　 {
　　　　　　　PRintf(" %02d ", ++key);
　　　　　　　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;
}