西安建筑科技大学：《数据结构基础（选修）》课程PPT电子教案_第四部分 树与二叉树（中文）

第6章树与二叉树 6.1树的概念和运算 6,2二叉树 6.3和林 6.4树的典型应用 65本章小结

第6章 树与二叉树 6.1 树的概念和运算 6.2 二叉树 6.3 树和森林 6.4 树的典型应用 6.5 本章小结

6.1树的概念和运算 树形结构是线性结构的拓广。 除了首元(唯一存在,在树形结构中称 为“根”节点)没有前驱元素以外,树中其 他所有元素(节点)都有且只有一个直接前 驱元素(父节点);直接后继元素则没有限 制:没有直接后继元素的节点(叶节点)可 以有多个;存在直接后继元素的节点,其直 接后继元素的个数也可以有多个

6.1 树的概念和运算 树形结构是线性结构的拓广。 除了首元（唯一存在，在树形结构中称 为“根”节点）没有前驱元素以外，树中其 他所有元素（节点）都有且只有一个直接前 驱元素（父节点）；直接后继元素则没有限 制：没有直接后继元素的节点（叶节点）可 以有多个；存在直接后继元素的节点，其直 接后继元素的个数也可以有多个

61.1树的定义与表示 树的定义: 树的逻辑结构可以这样描述: 树是包含N(N>0)个节点的有穷集合D 且在D上定义了一个关系R,关系R满足以 下条件:

6.1.1 树的定义与表示 • 树的定义： 树的逻辑结构可以这样描述： 树是包含N(N>0)个节点的有穷集合D， 且在D上定义了一个关系R，关系R满足以 下条件：

(1)有且仅有一个节点e∈D,它对于关系 R来说没有前驱,节点e称作树的根。 (2)除节点e外,D中的每个节点对于关系 R来说都有且仅有一个前驱。 (3)除节点e0外的任何节点eS,都存在 个节点序列(eo2e1,en),其中e就是树根 且en=e,有序对∈R(l≤i≤m)。这 样的节点序列称为从根到节点e的一条路径

(1) 有且仅有一个节点e0D，它对于关系 R来说没有前驱，节点e0称作树的根。 (2) 除节点e0外，D中的每个节点对于关系 R来说都有且仅有一个前驱。 (3) 除节点e0外的任何节点eS，都存在一 个节点序列(e0 ,e1 ,…,em )，其中e0就是树根， 且em=e，有序对R（1≤i≤m）。这 样的节点序列称为从根到节点e的一条路径

递归是树的固有属性 树的递归定义: 树是由一个或多个节点组成的有限集T, 它满足下面两个条件: (1)有一个特定的节点称之为根; (2)其余的节点分成m(m≥0)个互不相 交的有限集里1,里2,…,里n,其中每个集 合本身又是一棵树,称里1,里2,…,T为 根的子树

树的递归定义： 树是由一个或多个节点组成的有限集T， 它满足下面两个条件： (1)有一个特定的节点称之为根; (2)其余的节点分成m(m≥0)个互不相 交的有限集T1，T2，…，Tm，其中每个集 合本身又是一棵树，称T1，T2，…，Tm为 根的子树。 递归是树的固有属性

树的表示: 体现树形结构中分支和层次的特性 A A C H a)倒置的树形图表示方法 (b)文式图表示方法 (c)凹入表的表示方法 图6.2树形结构中分支与层次特性的表示 本书中描述树形结构的方式

树的表示： 体现树形结构中分支和层次的特性。 A B C D E F G H B G F H D E C A A B C D E F H G (a)倒置的树形图表示方法 (b)文式图表示方法 (c)凹入表的表示方法 图6.2树形结构中分支与层次特性的表示 本书中描述树形结构 的方式

6.1.2树的基本术语 节点 ·节点的度 叶子或终端节点 非终端节点或分支节点 内部节点 树的度

6.1.2 树的基本术语 • 节点 • 节点的度 • 叶子或终端节点 • 非终端节点或分支节点 • 内部节点 • 树的度

孩子 双亲 兄弟 祖先 子孜 节点的层次 树的深度或高度 有序树 无序树 森林

•孩子 •双亲 •兄弟 •祖先 •子孙 •节点的层次 •树的深度或高度 •有序树 •无序树 •森林

613树的ADT允许空树(即树中 没有一个节点的树) 存在 AdT Tree 数据对象为D: D是具有相同特性的数据元素的集 合 数据间的关系R: (1)若D为空集,则称为空树; (2)若D为非空集且仅含有一个数 据元素,则R为空集,树只包含一个根节点;

6.1.3 树的ADT ADT Tree { 数据对象为D: D是具有相同特性的数据元素的集 合 数据间的关系R: (1) 若D为空集,则称为空树; (2) 若D为非空集且仅含有一个数 据元素,则R为空集,树只包含一个根节点; 允许空树（即树中 没有一个节点的树） 存在

(3)若D为非空集且含有不止一个数据元素,则 R=(H},H是同时满足如下条目的二元关系 (3.1)D中存在唯一的一个称为根的数据元素r, 它在关系H下无前驱; (3.2)D-{x}≠Φ,存在D-{x}的一个划分 D1,D2r…,Dn(m>0),对任意j水k(1≤j,k≤m)有 D1∩D=,且对任意的(1≤i≤m),惟一存在数据元 素x1∈D1有∈H; 3.3)对应于D-{x}的划分,H ,…,)有惟一的一个划分 H1,H2x…,Hn(m>0),对任意j大(1≤k≤m)有 H2∩H=Φ,且对任意的(1≤i≤m),H是D,上的二元 关系,(D,(H,})是一棵符合本定义的树,称为根的 子树

(3) 若D为非空集且含有不止一个数据元素,则 R={H},H是同时满足如下条目的二元关系: (3.1) D中存在唯一的一个称为根的数据元素r, 它在关系H下无前驱; (3.2) D-{r}Ф, 存 在 D-{r} 的 一 个 划 分 D1,D2,…,Dm(m>0), 对任意 jk(1≤j,k≤m) 有 Dj∩Dk =Ф,且对任意的i(1≤i≤m),惟一存在数据元 素xi∈Di有∈H; (3.3) 对应于D-{r}的划分,H- {,,…,}有惟一的一个划分 H1,H2,…,Hm(m>0),对任意jk(1≤j,k≤m)有 Hj∩Hk =Ф,且对任意的i(1≤i≤m),Hi是Di上的二元 关系,(Di,{Hi})是一棵符合本定义的树,称为根r的 子树