5.1.2 树的相关概念

学习编程的一大秘诀是：永远不要打无把握之仗。例如在学习C语言算法时，必须先学好C语言的基本用法，包括基本语法、指针、结构体等知识。这一秘诀同样适用于学习“树”这一数据结构，在学习之前需要先了解与“树”相关的几个概念。

· 节点的度：指一个节点的子树个数。

· 树的度：一棵树中节点的度的最大值。

· 叶子（终端节点）：度为0的节点。

· 分支节点（非终端节点）：度不为0的节点。

· 内部节点：除根节点之外的分支节点。

· 孩子：将树中某个节点的子树的根称为这个节点的孩子。

· 双亲：将某个节点的上层节点称为该节点的双亲。

· 兄弟：同一个双亲的孩子。

· 路径：如果在树中存在一个节点序列k1，k2，…，kj，使得ki是ki+1的双亲（1≤i＜j），则称该节点序列是从k1到kj的一条路径。

· 祖先：如果树中节点k到ks之间存在一条路径，则称k是ks的祖先。

· 子孙：ks是k的子孙。

· 层次：节点的层次从根开始算起，第1层为根。

· 高度：树中节点的最大层次称为树的高度或深度。

· 有序树：将树中每个节点的各个子树看成从左到右的有序树。

· 无序树：有序树之外的称为无序树。

· 森林：指n(n≥0)棵互不相交的树的集合。

注意：可以使用树中节点之间的父子关系来描述树形结构的逻辑特征。

图5-3展示了一张完整的树形结构图。