数据结构与算法分析 —— C 语言描述：树的基础知识

树（tree）可以用几种方式定义。定义树的一种自然的方式是递归方法。一棵树是一些节点的集合。这个集合可以是空集；若非空，则一棵树由称作根（root）的节点 r 以及 0 个或多个非空的（子）树 组成，这些子树中每一棵的根都被来自根 r 的一条有向的边（edge）所连接。

每一棵子树的根叫做根 r 的儿子（child），而 r 是每一棵子树的根的父亲（parent）。

从递归定义中我们发现，一颗树是 N 个节点和 N-1 条边的结合，其中的一个节点叫作根。存在 N-1 条边的结论是由下面的事实得出的，每条边都将某个点连接到它的父亲，而除去根节点外每一个节点都有一个父亲。

没有儿子的节点称为树叶（leaf）；具有相同父亲的节点为兄弟（sibling）；用类似的方法可以定义祖父（grandparent）和孙子（grandchild）关系。

从节点 到 的路径（path）定义为节点 的一个序列，使得对于 1 ≤ i < k，节点 是 的父亲。这个路径的长（length）为该路径上边的条数，即 k-1.从每一个节点到它自己有一条长为 0 的路径。注意，在一棵树中从根到每个节点恰好存在一条路径。

对任意节点 的深度（depth）为从根到 的唯一路径的长。因此，根的深度为 0。 的高（height）是从 到一片树叶的最长路径的长。因此所有的树叶的高都是 0。一棵树的高等于它的根的高。一棵树的深度等于它的最深的树叶的深度；该深度总是等于这棵树的高。

如果存在从 到 的一条路径，那么 是 的一位祖先（ancestor）而 是 的一个后裔（descendant）。如果 ≠ ，那么 是 的一位真祖先（proper ancestor）而 是 的一个真后裔（proper descendant）。