一、排列树的定义

排列树就是一个能表示全排列的树形结构。全排列咱们都学过，就是所有可能的排列。

当问题的解是n个元素的某个排列时，其解空间（全部可能解构成的集合）就是n个元素的全排列，称为排列树。

以3个元素{1、2、3}的全排列为例，排列树如下：

（排列树图）

二、排列树的性质

1．节点表示：排列树的每个节点都表示一个部分排列，即n个元素中的某些元素按一定顺序排列的结果。根节点通常表示空排列或初始状态，叶节点表示完整的排列。

2．子节点生成：通过在节点后添加剩余元素中的一个来生成其子节点。也就是说，子节点和前面已生成了节点不能重复。正是这一要求使其体现出排列特征。

3．遍历方式：排列树可以通过深度优先搜索（DFS）等算法进行遍历。

4．排列数量：n个元素的全排列共有n!种（n的阶乘），意味着其叶节点数量也是n!。

三、排列树的经典应用

排列树常用于解决需要生成所有可能排列的问题，如八皇后问题、旅行商问题等。

解决此类问题时一般都需要遍历整个排列数，需用到回溯算法（其实就是深度优先搜索）。