树的定义和基本术语.ppt

第六章树和二叉树 树型结构是一类重要的非线性数据结构 其中以树和二叉树最为常用 直观来说 树是以分支关系定义的层次结构 树结构在客观世界中广泛存在 如人类社会的族谱和各种社会组织机构都可用树来形象表示 树在计算机领域中也得到广泛应用 如在编译程序中 可用树来表示源程序的语法结构 又如在数据库系统中 树形结构也是信息的重要组织形式之一 6 1树的定义和基本术语 6 2二叉树 6 3遍历二叉树和线索二叉树 6 4树和森林 6 6哈夫曼树及其应用 6 1树的定义和基本术语 1 定义树 Tree 是n n 0 个结点的有限集 定义一 递归定义 在任意一棵非空树中 有且仅有一个特定的称为根 root 的结点 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一棵树 并且T1 T2 Tm 称为根的子树 SubTree 定义二 形式定义 任何一棵树是一个二元组Tree root F 其中 root是数据元素 称做树的根结点 F是m m 0 棵树的森林 F T1 T2 Tm 其中Ti ri Fi 称做根root的第i棵子树 当m 0时 在树根和其子树森林之间存在下列关系 RF i 1 2 m m 0 2 表示形式 该树有13个结点 其中 A是树根 其余结点分成3个互不相交的子集 T1 B E F K L T2 C G T3 D H I J M T1 T2和T3都是A的子树 其本身也是一棵树 图6 1一般的树 A 该树又可表示为如下三种形式 a 嵌套集合表示 c 凹入表示法 A B E K L F C G D H M I J b 广义表表示 图6 2树的其他3种表示法 3 树的抽象数据类型定义 CreateTree 初始条件 树T存在 cur e是T中某个结点 操作结果 结点cur e赋值为value Parent T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 若cur e是T的非根结点 则返回它的双亲 否则函数值为 空 LeftChild T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 若cur e是T的非叶子结点 则返回它的最左孩子 否则返回 空 RightSibling T cur e 初始条件 树T存在 cur e是T中某个结点 操作结果 若cur e有右兄弟 则返回它的右兄弟 否则函数值为 空 InsertChild 初始条件 树T存在 visit是对结点操作的应用函数 操作结果 按某种次序对T的每个结点调用函数visit 一次且至多一次 一旦visit 失败 则操作失败 ADTTree 6 1 2基本术语 结点 包含一个数据元素及若干指向其子树的分支 在树的图形表示中为一个圆圈 结点的度 Degree 结点拥有的子树数 叶子 或终端结点 Leaf 度为0的结点 即没有子树的结点 分支结点 或非终端结点 度不为0的结点 内部结点 除根结点之外的分支结点 树的度 树内各结点的度的最大值 孩子 Child 结点的子树的根 称为该结点的孩子 双亲 Parent 结点的子树的根 称为该结点的孩子 该结点称为孩子的双亲 兄弟 Sibling 同一个双亲的孩子之间互称为兄弟 子孙 以某结点为根的子树中的任一结点都称为该结点的子孙 祖先 从根到某结点所经分支上的所有结点 称为该结点的祖先 森林 Forest 是m m 0 棵互不相交的树的集合 对树中每个结点而言 其子树的集合即为森林 层次 Level 从根开始定义起 根为第一层 根的孩子为第二层 若某结点在第k层 则其子树的根就在第k 1层 堂兄弟 其双亲在同一层的结点互为堂兄弟 深度 高度 Depth 树中结点的最大层次 有序树 若将树中结点的各子树看成从左至右是有次序的 即不能互换 则称该树为有序树 否则称为无序树 在有序树中最左边的子树的根称为第一个孩子 最右边的称为最后一个孩子 结点 包含一个数据元素及若干指向其子树的分支 结点的度 结点拥有的子树数称为结点的度 如图 A的度为3 C的度为1 E的度为0 树的度 叶子 或终端 结点 分支 或非终端 结点 树中所有结点的度的最大值 度为零的结点 度大于零的结点 除根结点外 分支结点也称为内部结点 如图所示的树的度为3 结点的子树的根称为该结点的孩子 child 相应的 该结点的称为孩子的双亲 parent 如图所示中 D为A的子树T3的根 则D是A的孩子 而A则是D的双亲 同一个双亲的孩子之间互称兄弟 sibling 如图所示中 H I J互称为兄弟 将这些关系进一步推广 可认为D是M的祖父 结点的祖先是从根到该结点所经分支的所有结点 如图所示中 M的祖先为A D和J 反之 以某结点为根的子树中的任一结点都称为该结点的子孙 如B的子孙为E F K L 结点的层次 树的深度 结点的层次从根开始定义起 根为第一层 根的孩子为第二层 假设根结点的层次为1 第l层的结点的子树根结点的层次为l 1 树中叶子结点所在的最大层次 图示的树的深度为4 结点双亲在同一层的结点互为堂兄弟 例如 结点G与E F H I J互为堂兄弟 有序树 子树之间存在确定的次序关系 树中结点的各子树从左到右是有次序的 即不能互换 在有序树中最左边的子树的根称为第一个孩子 最右边的称为最后一个孩子 无序树 子树之间不存在确定的次序关系 森林 是m m 0 棵互不相交的树的集合 对树中每个结点而言 其子树的集合即为森林 由此 也可以森林和树相互递归的定义来描述树 A root F 就逻辑结构而言 任何一棵非空树是一个二元组Tree root F 其中 root是数据元素 被称为根结点 F是m m 0 棵树的森林 被称为子树森林 F T1 T2 Tm 其中Ti ri Fi 称做根为root的第i棵子树 当m0时 在树根和其子树森林之间存在下列关系 RF i 1 2 m m 0 这个定义将有助于得到森林和树与二叉树之间转换的递归定义 对比树型结构和线性结构的结构特点 线性结构 树型结构 第一个数据元素 无前驱 根结点 无前驱 最后一个数据元素 无后继 多个叶子结点 无后继 其它数据元素 一个前驱 一个后继 其它数据元素 一个前驱 多个后继