树的表示: 体现树形结构中分支和层次的特性 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有<r,x1>∈H; 3.3)对应于D-{x}的划分,H <r,x1>,<r,x2>…,<r,xm>)有惟一的一个划分 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), 对任意 jk(1≤j,k≤m) 有 Dj∩Dk =Ф,且对任意的i(1≤i≤m),惟一存在数据元 素xi∈Di有<r,xi>∈H; (3.3) 对应于D-{r}的划分,H- {<r,x1>,<r,x2>,…,<r,xm>}有惟一的一个划分 H1,H2,…,Hm(m>0),对任意jk(1≤j,k≤m)有 Hj∩Hk =Ф,且对任意的i(1≤i≤m),Hi是Di上的二元 关系,(Di,{Hi})是一棵符合本定义的树,称为根r的 子树