第六章树和二叉树 第一节树的类型定义 为“根 °T1、12和T3都是一棵树,称为A的子树。 称根和子树根之间的连线为“分支 结点分支的个数定义为“结点的度”,如结点B的度为2,D的度为3。 树中所有结点度的最大值定义为树的度”。 称度为零的结点为“叶子” 或“终端结点 所有度不为零的结点 被称作”分支结点 基本定义 森林为m(m≥0)棵互不相交的树的集合。 树的深度定义为树中叶子结点所在最大层次数。 称根结点为子树根的”双亲”。 称子树根为根结点的孩子“ 根的所有子树根互为“兄弟”。 °有序树、无序树如果树中 每棵子树从左向右的排列拥有 定的顺序,不得互换,则称 为有序树,否则称为无序树。 树的抽象数据类型: .ADT Tree i 数据对象:D是具有相同特性的数据元素的集合 数据关系 若D为空集,则称为空树 若D中仅含一个数据元素,则关系R为空集; 否则R={H} (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)当n>1时,其余数据元素可分为m(m>0)个互不相交的非空有限集T1,T2,,Tm 其中每一个子集本身又是一棵符合本定义的树,称为根root的子树,每一棵子树的根xi都 是根root的后继,即<rot,r>H,=1,2,,m。 基本操作: {结构初始化} 操作结果:构造空树T CreateTree(&T, definition) 初始条件: definition给出树T的定义。 操作结果:按 definition构造树T第六章 树和二叉树 第一节 树的类型定义 •A 为“根” •T1、T2 和 T3 都是一棵树，称为 A 的子树。 •称根和子树根之间的连线为“分支” •结点分支的个数定义为“结点的度”，如结点 B 的度为 2，D 的度为 3。 •树中所有结点度的最大值定义为“树的度”。 •称度为零的结点为“叶子” 或“终端结点” •所有度不为零的结点 被称作"分支结点" 基本定义 •森林为 m(m≥0) 棵互不相交的树的集合。 •树的深度定义为树中叶子结点所在最大层次数。 •称根结点为子树根的"双亲"。 •称子树根为根结点的"孩子“ •根的所有子树根互为“兄弟”。 •有序树、无序树 如果树中 每棵子树从左向右的排列拥有 一定的顺序，不得互换，则称 为有序树，否则称为无序树。 树的抽象数据类型： •ADT Tree { 数据对象：D 是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，则称为空树； 若 D 中仅含一个数据元素，则关系 R 为空集； 否则 R={H}， (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) 当 n>1 时，其余数据元素可分为 m(m>0) 个互不相交的(非空)有限集 T1,T2,…,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都 是根 root 的后继，即 <root,xi> H,i=1,2,…,m。 •基本操作： {结构初始化} InitTree(&T); 操作结果：构造空树 T。 CreateTree(&T,definition); 初始条件：definition 给出树 T 的定义。 操作结果：按 definition 构造树 T