[概念辨析 系列 之四] 树的概念

刚做老师的时候，在考试、面试等场合发现大家对计算机科学中"树"的概念理解地非常不好，各种逻辑混乱的答案频繁出现。当时还不太理解，过了一段时间之后，对这个问题有了更全面的认识。"树"在不同场合有不同含义，这些含义之间是有关联的，还经常混合着使用，因而也是易混淆的。更重要的是，在目前的教学中，不同课程对“树”有不同的定义与解读，而这些不同场合的解读，是互相割裂的，缺乏全面、综合的讨论。因而打算在这里系统地讨论一下"树"的概念，包括树的基本定义，以及多种概念混合的树。

1. 两种基本的"树"

树的含义有不止一种，但是对于《算法设计与分析》课程而言，我认为最重要的含义是图论中树的概念：

给定一个无向图G，如果：i）G是连通的；ii）G是无环的，则G是一棵树。

这一定义简单明了，看起来不会弄错的样子。但是问题恰恰出在这里：这一树的概念非常有用，有用到我们经常把它跟其它概念混在一起使用，因而很容易导致混淆。

大家同样比较熟悉的可能是数据结构中的二叉树，以及其它类似的各种树。这里不在作详细定义，可以参见以前文章中讨论过的二叉树中的一些概念。

参见"二叉树相关的一些定义"中的讨论

2. "树"中到底有没有根、父子、高度、深度等概念？

很多同学被问到什么是树的时候，第一反应是，有一个根，长出来，因而有父节点、子节点、左右兄弟节点、叶节点，有高度、深度等等。

对于图论中的树而言，最重要的defining characteristic是“无环”。连不连通（也就是说是一棵树，还是一个森林）经常差别不大。例如我们算法课中的很多问题，都是针对图的一个连通片来考虑的，不同连通片分别作类似地处理即可。

图论中树是没有根的概念的，也就无所谓父子、兄弟、左右子节点、高度、深度等等（图论中的树，有叶的概念，指度为1的节点）。

根节点、父/子节点、左/右子节点、兄弟节点、叶节点、高度、深度等都是数据据结构中二叉树（以及其它类似的树）中的概念。另外需要注意的是，有了根之后，树中的边就天然地有了方向的概念（不管你用不用它），我们可以自然地定义树中的边的方向是父指向子（或者反之）。

所以谈到“树”，大家脑子里首先要弄清楚上述不同的定义，其次根据上下文判断具体所谈的是哪一种树。

3. 很多大家熟知的树，其实多种概念的混合体

大家混淆树的各种概念，一个很可能的原因是很多重要的树，其实是上述两种概念的混合体。最典型的例子就是DFS/BFS遍历树。

我们讨论图遍历的时候，所有tree edge组成了图的遍历树（只考虑连通的情况。另外，如果对tree edge的概念不熟悉，可以翻书仔细回顾一下tree edge，forward edge，back edge，cross edge的概念）。我们之所以称它为树，主要是取了树在图论中的含义，即连通，无环。图论中树的概念，很好地概括了图遍历的一个重要属性：走遍所有节点，且发现新节点的过程是反对称的（无环的）。

但是遍历树的概念又显然超出了图论中树的概念。

• 首先，遍历树它有天然的根节点，就是遍历的起始节点，因而也就有父子节点、兄弟节点、叶节点、高度、深度等概念；
• 另外别忘了，虽然图论中的树是限于无向图的，但是遍历树天然有方向。对于无向图而言，虽然边上本来没有方向，但是遍历中逐步发现新节点的过程，为每一条tree edge定义了一个方向，以tree edge的方向为基础，forward edge，back edge，cross edge也就可以自然地定义方向。
• 最后，对于有向图，讲起来还更啰嗦一点。图论中的树都是针对无向图的。对于有向图，"连通"这一在无向图中很简单的概念，就需要更精细的讨论，由此引申出强连通，弱连通等概念。对于有向图，严格来说我们应该这么讲：如果对于有向图的遍历能够走遍图中所有的点，那么我们取所有tree edge，并且忽略所有边的方向，我们总会得到一棵生成树（连通、无环）。正是在这个意义上，我们对有向图，也同样称之为遍历树。有向图的遍历树中的边，以及其它各种边当然有方向，就是它本来的方向。有向图的遍历树同样也有根、父子、高度、深度等概念。

最后，Prim算法和Dijkstra算法本质也是一种遍历，只不过多了贪心选择的过程，在我们的课本（《算法设计与分析》）中把它们称为Best First Search (BestFS)。因而Prim和Dijkstra算法同样有遍历树，它也同样是上述多种树的概念的混合体。大家可以结合上面的讨论，来体会这两个算法执行过程中的连通性、无环性、方向性，以及根的概念、父子的概念等。