电子科技大学：《软件技术基础 Fundamental of Software Technology》课程教学资源（课件讲稿）第三章 数据结构 3.5.1 树的基本概念

电子斜技大学 软件技术基础 3.5.1树的基本概念 主讲教师：刘民岷 航空航天学院 a口2 软件技术基础课程组

软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组

1、非线性结构 非线性结构的逻辑特征，一个节点元素可能有多个直接 前趋多个直接后趋。 ● 最主要和典型的非线性结构：树结构和图结构。 A B 电子科技大学刘民岷 树和二叉树 2

电子科技大学 刘民岷 树和二叉树 2 • 非线性结构的逻辑特征，一个节点元素可能有多个直接 前趋多个直接后趋。 • 最主要和典型的非线性结构：树结构和图结构

2、树结构及其基本概念 电子科技大学 树形结构是以分支关系来定义 的层次结构。在客观世界中树 形结构广泛存在，并应用于： 人类社会的族谱、家谱、行政 机械 计算 电 电子 工程 信材 区域划分管理； 学院 学院 一各种社会组织机构； 学院 在计算机领域中，用树表示源 程序的语法结构； 在OS中，文件系统、目录等组 织结构也是用树来表示的。 机械 电力 工业 了 工程 工程 电子科技大学刘民岷 树和二叉树 3

电子科技大学 刘民岷 树和二叉树 3 • 树形结构是以分支关系来定义 的层次结构。在客观世界中树 形结构广泛存在，并应用于： – 人类社会的族谱、家谱、行政 区域划分管理； – 各种社会组织机构； – 在计算机领域中，用树表示源 程序的语法结构； – 在OS中，文件系统、目录等组 织结构也是用树来表示的。 电子科技大学 机械 电子 工程 学院 计算 机学 院 电工 工程 学院 信材 … 学院 机械 电子 工程 系 电力 电子 系 工业 工程 系 ……

2、树结构及其基本概念 (续) 可以用递归的方式把树定义如下： 树是一个或多个结点元素组成的有限 集合T,且满足如下条件： A (1)有一个特定的结点元素，称为根结点 (Root); B (2)其余结点元素分成m个（≥0）互不相交的 有限集T1,T2,,Tm,其中每个集又都是 一棵树，这些树称为Root的子树。 G 电子科技大学刘民岷 树和二叉树 4

电子科技大学 刘民岷 树和二叉树 4 • 可以用递归的方式把树定义如下： 树是一个或多个结点元素组成的有限 集合T，且满足如下条件： （1）有一个特定的结点元素，称为根结点 （Root）； （2）其余结点元素分成m个(m≥0)互不相交的 有限集T1，T2，…，Tm，其中每个集又都是 一棵树，这些树称为Root的子树

2 、树结构及其基本概念（续） 有关树的重要术语与概念 (1)叶子没有后继的结点称为叶子 (或终端结 点)如右图中的结点D、G、H、I。 (2)分支结点 非叶子结点称为分支结点（或非终 端结点)。 (3)结点的度 一个结点的子树数目就称为该结 点的度，如图中的结点B的度为1；结点C的度为 2;结点D,I的度为0。 (4)树的度树中各结点的度的最大值称为该树 的度，右图所示的树的度为2。 (5)子结点某结点子树的根称为该结点的子结 点。 (6)父结点相对于某结点子树的根，称该结点 为子树根的父结点。 电子科技大学刘民岷 树和二叉树 5

电子科技大学 刘民岷 树和二叉树 5 • 有关树的重要术语与概念 （1） 叶子 没有后继的结点称为叶子（或终端结 点）如右图中的结点D、G、H、I。 （2）分支结点 非叶子结点称为分支结点(或非终 端结点)。 （3）结点的度 一个结点的子树数目就称为该结 点的度，如图中的结点B的度为1；结点C的度为 2；结点D，I的度为0。 （4）树的度 树中各结点的度的最大值称为该树 的度，右图所示的树的度为2。 （5）子结点 某结点子树的根称为该结点的子结 点。 （6）父结点 相对于某结点子树的根，称该结点 为子树根的父结点

2、树结构及其基本概念（续） 有关树的重要术语与概念 (7)兄弟具有同一父结点的子结点称为兄弟。 A (8)结点的层次根结点的层次为1，其他任何的 层数等于它的父结点的层数加1。 (9)树的深度一棵树中，结点的最大层次值就 是树的深度。右图所示的树的深度为4。 (10)有序树和无序树如果一棵树中结点的各 子树从左到右是有序的，即若交换了某结点各 子树的相对位置，则构成了不同的树，称这棵 树为有序树，反之，则称之为无序树。 (11)森林森林是n棵树的集合n心0)。任何一棵 树，删去根结点，树就变成了森林。 电子科技大学刘民岷 树和二叉树 6

电子科技大学 刘民岷 树和二叉树 6 • 有关树的重要术语与概念 （7）兄弟 具有同一父结点的子结点称为兄弟。 （8）结点的层次 根结点的层次为1，其他任何的 层数等于它的父结点的层数加1。 （9）树的深度 一棵树中，结点的最大层次值就 是树的深度。右图所示的树的深度为4。 （10）有序树和无序树 如果一棵树中结点的各 子树从左到右是有序的，即若交换了某结点各 子树的相对位置，则构成了不同的树，称这棵 树为有序树，反之，则称之为无序树。 （11）森林 森林是n棵树的集合(n≥0)。任何一棵 树，删去根结点，树就变成了森林