----------------siwuxie095
树形问题
在处理计算机中遇到的很多问题时，虽然没有创建出具体的树，但是
整个是以一棵树的形状进行求解的，通常称这类问题为 树形问题
递归法 - 天然的树形性质
由于树这种结构，它的定义具有天然的递归性质，因此，当求解计算
机问题时，如果使用的是递归的方法，那么这些问题也就天然的具有
树形问题的性质
最典型的，比如：归并排序 和 快速排序
整个过程可以看做是对一棵排序树的遍历，用这种观点再去看归并排序
和快速排序的代码，就会发现，它们像极了是对一棵树进行后续遍历 或
前序遍历 这样的代码模式
使用递归的方式来求解问题，在计算机领域一类最常见的求解问题，
就是搜索问题
事实上，绝大多数计算机问题都可以使用搜索的方式来解决
（1）一条龙游戏
在与电脑博弈的过程中，每一次在 9 个格子里走哪个点，就可以枚举，
每一次枚举产生出一个新棋局，那么对于这个新棋局，实际上就相当于
是从上一个棋局开始，派生下来的子节点 … 依此类推，直至整个游戏
完结
即 通过搜索的一个称之为决策树的树，来遍历所有的决策，以选出最
优的决策
（2）8 数码
对于这个游戏，可以用搜索树来进行解决。通过初始的棋局，
一共可能有 4 种走法，派生出初始棋局的 4 个子节点，对于
每一个子节点，相应的又有若干种走法 … 依此类推
（3）八皇后
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋
棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了
达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上
采用树形搜索的方式，可以很容易地生成八皇后的所有的解
当然，搜索问题，也并不像想象的那么容易。实际上，之前提过的所有问题，
在搜索的同时，对应的都还可以优化
不然的话，相应的状态数量太多，更重要的是，有可能对重复的状态进行了
访问
（4）数独
数独，这类更难的问题也可以使用树的方式解决
（5）搬运工
甚至像搬运工这样的小游戏：怎么把砖块搬运到指定的地点，
都可以使用树的方式来解决
而类似于自动求解搬运工，也是一个典型的人工智能的任务
在早期，搜索过程近乎就是人工智能的核心
如：为 IBM 赢得国际象棋冠军的深蓝，它的核心其实就是搜索
当然这个搜索不是简单的仅仅做搜索，这里面涉及到很多的优化，
很多的技巧，包括对要搜索的问题本身的深入分析
而像 AlphaGo 这样的人工智能和搜索还是略有不同的，AlphaGo
使用的是机器学习相关的技术
更多树
在计算机科学领域随着求解问题的不同，针对不同的问题种类，
计算机科学家还发明了更多的树，最典型的，如下：
KD 树、区间树、哈夫曼树 …
树这个话题在计算机科学中，占据着举足轻重的地位
【made by siwuxie095】