树的概念¶

引入¶

图论中的树跟在现实生活中的树长得很像，不过我们平常一般习惯处理问题的时候把树根放到最上面。树也跟图一样，是由若干个节点和边所组成的。

树是一种特殊的图，是一个拥有 \(n\) 个节点和 \(n-1\) 条边的无向无环连通图。与普通的图不同，树的每一个节点最多只能有一个前继节点。如果制定了一个“根”，就是一棵有根树；若没有指定固定的根，那么就是一颗无根树。

森林：每一个联通块 / 联通分量都是树的图就叫做森林。虽然有点离谱，但是一棵树其实也是森林。
父结点 / 父亲：一个结点上面的最近的结点，并且和这个结点连上了一条边。
祖先：一个结点到根结点的路径上面，除了他自己，其他的结点都是他的祖先。
子结点 / 儿子：如果 \(a\) 是 \(b\) 的父亲，那么 \(b\) 是 \(a\) 的子结点。每一个结点最多只能有一个父亲，但是可以有多个儿子。
兄弟：一个结点的多个儿子之间互相为兄弟。
后代：与祖先正好相反，若 \(a\) 是 \(b\) 的祖先，那么 \(b\) 是 \(a\) 的后代。
叶子结点：当一个结点没有任何儿子的时候，这个结点就是一个叶子结点。
结点深度：根结点到当前结点的路径经过的边的数量。
树的高度：在树当中所有结点的深度最大值。

二叉树是一种特殊的树，对于任意一个结点，最多只有两个儿子。二叉树当中结点的儿子是区分顺序的，分为左儿子和右儿子。