5.1.1 树的定义和基本术语

树是 $n$ 个结点的有限集合。非空树有且仅有一个根，其余结点被划分成根的若干互不相交子树。结点的度是孩子数，树的度是所有结点度的最大值；叶结点度为 0。祖先/后代描述路径上的传递关系，双亲/孩子只描述相邻一层。深度从根向下计，常约定根在第 1 层；高度从结点向叶计。考试必须先确认空树高度及根层数约定。

手工推演

树 A 的孩子为 B、C，B 的孩子为 D、E。A 深度 1、高度 3；B 深度 2、高度 2；D、E、C 是叶。D 与 E 是兄弟，A 是 D 的祖先但不是双亲。树中任意两个结点间只有一条简单路径。

结构与代码

可用括号表示 A(B(D,E),C)。递归定义让许多算法写成“处理根，再递归处理每棵子树”；边数则等于除根外每个结点贡献的一条双亲边，所以非空树有 $n-1$ 条边。

错解反馈

把树的度说成层数；把叶结点定义成“没有后继”；把堂兄弟也称兄弟；把高度和深度方向混用，都会导致性质题连锁出错。

迁移练习

画一棵 8 结点、树度为 3、高度为 4 的树，标出每个结点的度、深度和高度。独立验收：能由任意树图准确回答根、叶、兄弟、祖先、路径与边数。