713树的基本术语 B D 结点的度 结点拥有的子树数 FG①H 树的度 K 树内各结点的度的最大值。m次树或m叉树 子(终端结点):度为0的结点 非终端结点(分支结点):度不为0的结点 路经:从树中一个结点自上而下到另一个结点之间的 分支构成一条路径。 路径长度:路径上的分支数目称作路径长度。 孩子:结点的子树的根称为该结点的孩子。相应地 该结点称为孩子的双亲。兄弟:同一双亲的孩子互为 兄弟
➢ 结点的度: 结点拥有的子树数. ➢ 树的度： 树内各结点的度的最大值。m次树或m叉树. ➢ 叶子（终端结点）：度为0的结点。 ➢ 非终端结点（分支结点）：度不为0的结点。 ➢ 路径：从树中一个结点自上而下到另一个结点之间的 分支构成一条路径。 ➢ 路径长度：路径上的分支数目称作路径长度。 ➢ 孩子：结点的子树的根称为该结点的孩子。相应地， 该结点称为孩子的双亲。兄弟：同一双亲的孩子互为 兄弟。 A B C D E F G H I J K L M 7.1.3 树的基本术语
层次:1 APC工 D E)(G(①D③3 结点的先从根到该结点所经分支上的所有结点。 结点的子孙其子树中的任意结点 结点的层次:从根开始定义起,根为第一层,根的孩 为第二层,以此类推,可得各结点的层次。 >堂兄弟其双亲在同一层的非兄弟结点互为堂兄弟 深度:树中结点的最大层次 有序树:如果树中结点的各子树看成从左到右是有序 的,则称为有序树;否则称为无序树
7 ➢ 结点的祖先：从根到该结点所经分支上的所有结点。 ➢ 结点的子孙：其子树中的任意结点 ➢ 结点的层次：从根开始定义起，根为第一层，根的孩子 为第二层，以此类推，可得各结点的层次。 层次：1 2 3 4 ➢堂兄弟：其双亲在同一层的非兄弟结点互为堂兄弟。 ➢深度：树中结点的最大层次。 ➢有序树：如果树中结点的各子树看成从左到右是有序 的，则称为有序树；否则称为无序树。 A B C D E F G H I J K L M
林:是m(m≥0)颗互不相交的树的集合 对于树而言,其子树的集合即为森林。 A B D E)(F)(G)(H J KL 故森林和树可以相互递归定义。 8
8 ➢森林：是m（m≥0)颗互不相交的树的集合。 对于树而言，其子树的集合即为森林。 A B C D E F G H I J K L M 故森林和树可以相互递归定义
714树的性质 性质1:树中的结点数等于所有结点的度数加1。 证明: 在一棵树中除树根结点外每个结 点有且仅有一个前驱结点。也就是说, 每个非根结点与指向它的一个分支 对应所以除树根之外的结点数等 于所有结点的分支数(度数)从而可得 树中的结点数等于所有结点的度数加 9
9 7.1.4 树的性质 性质1: 树中的结点数等于所有结点的度数加1。 证明： 在一棵树中,除树根结点外,每个结 点有且仅有一个前驱结点。也就是说, 每个非根结点与指向它的一个分支一 一对应,所以除树根之外的结点数等 于所有结点的分支数(度数),从而可得 树中的结点数等于所有结点的度数加 1。 1 2 3 4 5 6 7
性质度为m的树中第层上至多有m个 结点(1)。 证明(采用数学归纳法) 当i时炽有一个根结点,m1显然成立。 假设第z层上至多有结点,由于m叉树 的每个结点的度至多为m,故在第层上的最大 结点数为上一层第层的最大结点数的m倍。 故有 成立。 ×m=m 10
10 性质2 度为m的树中第i层上至多有mi-1个 结点（i≥1）。 证明(采用数学归纳法) 当 i = 时 1 ,只有一个根结点, 显然成立。 1 1 0 = = − m m i 假设第 层上至多有 个结点，由于m叉树 的每个结点的度至多为m，故在第 层上的最大 结点数为上一层第 层的最大结点数的m倍。 故有 成立。 i −1 i−2 m i i −1 −2 −1 = i i m m m