第七章树和二义树 数据结构 ●线性结构(线性表,栈,队列,串等) 非线性结构:至少存在一个数据元素有不 止一个直接前驱或后继(树,图等)
1 第七章 树和二叉树 数据结构 ⚫ 线性结构（线性表，栈，队列，串等） ⚫ 非线性结构：至少存在一个数据元素有不 止一个直接前驱或后继（树，图等）
7.1树的概念 711树的定义形式化定y) 树:T={KR}。K是包含n个结点的有穷集合 (m>0)关系R满足以下条件: (1)有且仅有一个结点k∈K,它对于关系R来说 没有前驱结点结点k称作树的。 (2)除结点k外K中的每个结点对于关系R来说 都有且仅有一个前驱结点。 (3)K中每个结点对于关系R来说可以有多个后 结点
2 7.1.1 树的定义(形式化定义)： 树：T＝{K,R}。K是包含n个结点的有穷集合 (n>0),关系R满足以下条件: (1)有且仅有一个结点k0∈K,它对于关系R来说 没有前驱结点,结点k0称作树的根。 (2)除结点k0外,K中的每个结点对于关系R来说 都有且仅有一个前驱结点。 (3)K中每个结点对于关系R来说可以有多个后 继结点。 7.1 树的概念
7.1树的概念 711树的定义递归定义) 树(Tree是由n(n>=0)个结点组成的有限集 (记为T),对任意一颗树T有 (1)存在唯一一个称为报(Root)的结点; (2)当n>1时,其余的结点可分为m(m>0)个 互不相交的子集T1T2T3Tm,其中每个子集 又是一棵树,并称其为根的子树 Subtree)。 3
3 7.1 树的概念 7.1.1 树的定义(递归定义） 树(Tree)是由n(n>=0)个结点组成的有限集 （记为T），对任意一颗树T有： （1）存在唯一一个称为根(Root)的结点； （2）当n>1时，其余的结点可分为m(m>0)个 互不相交的子集T1,T2,T3…Tm，其中每个子集 又是一棵树，并称其为根的子树(Subtree)
n=1只有根结点的树 N=0,空树 A n>1有子树的树 根 A B D E( FDIGH(I( K M 子树
4 A n=1,只有根结点的树 A B C D E F G H I J K L M n>1有子树的树 根 子树 N=0,空树
72树的逻辑表示方法 2 3 4 6 7 凹入表表示法 3 1(2(4,5(6,7)),3) 文氏图表示法 括号表示法
7.1.2 树的逻辑表示方法 1 2 3 4 5 6 7 1 2 4 5 6 7 3 凹入表表示法 1 2 4 5 3 6 7 文氏图表示法 1（2（4，5（6，7）），3） 括号表示法
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